Missing Clues - codepath/compsci_guides GitHub Wiki

TIP102 Unit 1 Session 1 Advanced (Click for link to problem statements)

Problem Highlights

• 💡 Difficulty: Easy
• ⏰ Time to complete: 10 mins
• 🛠️ Topics: Arrays, Sorting, Ranges

U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

• Q: What is the input to the function?

  • A: The input consists of two integers lower and upper, and an array clues of unique integers that are within the range [lower, upper].

• Q: What is the expected output of the function?

  • A: The function should return a list of ranges that represent the missing numbers within the range [lower, upper] that are not present in clues.

• Q: How should the ranges be represented?

  • A: Each range should be represented as a list of two elements [start, end], where start and end are inclusive.

• Q: What if no numbers are missing?

  • A: If no numbers are missing, the function should return an empty list.

• Q: How should the function handle cases where all numbers within the range [lower, upper] are missing?

  • A: If all numbers are missing, the function should return a single range that covers [lower, upper].

P-lan

• The function find_missing_clues() should take an array clues, and two integers lower and upper, and return a list of ranges that cover all the missing numbers in the range [lower, upper] that are not in clues.

HAPPY CASE
Input: clues = [0, 1, 3, 50, 75], lower = 0, upper = 99
Expected Output: [2, 2], [4, 49], [51, 74], [76, 99](/codepath/compsci_guides/wiki/2,-2],-[4,-49],-[51,-74],-[76,-99)
Explanation: The missing ranges cover all numbers from 0 to 99 that are not in the clues.

Input: clues = [2, 5, 9], lower = 1, upper = 10
Expected Output: [1, 1], [3, 4], [6, 8], [10, 10](/codepath/compsci_guides/wiki/1,-1],-[3,-4],-[6,-8],-[10,-10)
Explanation: The missing ranges cover all numbers from 1 to 10 that are not in the clues.

EDGE CASE
Input: clues = [-1], lower = -1, upper = -1
Expected Output: []
Explanation: No missing ranges as there are no numbers missing between -1 and -1.

P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Sort the clues array and then identify the gaps between consecutive elements, as well as the gaps between the lower bound and the first element, and the last element and the upper bound.

1. Define the function `find_missing_clues(clues, lower, upper)`.
2. Sort the `clues` array.
3. Initialize an empty list `missing_ranges`.
4. Check for missing range before the first element in `clues`.
5. Iterate through the sorted `clues` array and find gaps between consecutive elements.
6. Check for missing range after the last element in `clues`.
7. Return the `missing_ranges` list.

⚠️ Common Mistakes

• Not sorting the clues array. Incorrectly handling the edge cases where lower or upper are within the clues array.

I-mplement

Implement the code to solve the algorithm.

def find_missing_clues(clues, lower, upper):
    missing_ranges = []
    clues.sort()
    
    # Check the gap between lower and the first clue
    if lower < clues[0]:
        missing_ranges.append([lower, clues[0] - 1])
    
    # Check gaps between consecutive clues
    for i in range(1, len(clues)):
        if clues[i - 1] + 1 < clues[i]:
            missing_ranges.append([clues[i - 1] + 1, clues[i] - 1])
    
    # Check the gap between the last clue and upper
    if clues[-1] < upper:
        missing_ranges.append([clues[-1] + 1, upper])
    
    return missing_ranges