Missing Ranges

▶

Steps

setup

Initialize pointer and missing list

We start by setting the pointer to the lower bound (0) and initializing an empty list to store missing ranges.

💡 Setting the pointer to lower ensures we check the entire range from the start. The missing list will collect all missing ranges found.

Line:

missing = []
pointer = lower

💡 The pointer marks where we begin scanning for missing numbers.

compare

Binary search for pointer=0

We perform binary search to find the smallest number in nums greater than or equal to pointer (0). The result index is 0, pointing to nums[0] = 0.

💡 Binary search quickly finds where pointer fits in nums, allowing us to detect missing ranges efficiently.

Line:

idx = bisect.bisect_left(nums, pointer)

💡 Binary search locates the current pointer or next larger number in nums.

compare

Compare pointer and found number (0 and 0)

Pointer (0) equals the found number (0), so no missing range before it. We update pointer to found number + 1 = 1.

💡 If pointer equals the found number, no gap exists here, so we move pointer forward.

Line:

if pointer < curr:
    ...
pointer = curr + 1

💡 Pointer moves past the current number to check next possible missing numbers.

compare

Binary search for pointer=1

Binary search finds index 1 where nums[1] = 1, which equals pointer 1.

💡 We locate the next number in nums at or after pointer to check for missing ranges.

Line:

idx = bisect.bisect_left(nums, pointer)

💡 Binary search confirms pointer is present in nums, so no missing range here.

compare

Compare pointer and found number (1 and 1)

Pointer equals found number, so no missing range. Update pointer to 2 (1 + 1).

💡 No gap before 1, so pointer moves forward to check next number.

Line:

if pointer < curr:
    ...
pointer = curr + 1

💡 Pointer advances to next candidate missing number.

compare

Binary search for pointer=2

Binary search finds index 2 where nums[2] = 3, which is greater than pointer 2.

💡 We found the next number after pointer, indicating a missing range before it.

Line:

idx = bisect.bisect_left(nums, pointer)

💡 Pointer 2 is missing since nums[idx] > pointer.

insert

Record missing range 2

Pointer (2) is less than found number (3), so missing range is from 2 to 2 (single number). We add '2' to missing.

💡 When pointer and found number differ by 1, the missing range is a single number.

Line:

if pointer < curr:
    end = curr - 1
    if pointer == end:
        missing.append(str(pointer))

💡 We detect and record single missing numbers correctly.

move_right

Update pointer to 4

After recording missing range, pointer moves to curr + 1 = 4 to continue scanning.

💡 Moving pointer past the found number ensures we don't re-check the same number.

Line:

pointer = curr + 1

💡 Pointer advances to next candidate missing number.

compare

Binary search for pointer=4

Binary search finds index 3 where nums[3] = 50, which is greater than pointer 4.

💡 Next number after pointer is 50, indicating a large missing range.

Line:

idx = bisect.bisect_left(nums, pointer)

💡 We will record missing range from 4 to 49 next.

insert

Record missing range 4->49

Pointer (4) is less than found number (50), so missing range is from 4 to 49. We add '4->49' to missing.

💡 Ranges longer than one number are recorded with 'start->end' format.

Line:

if pointer < curr:
    end = curr - 1
    if pointer != end:
        missing.append(f"{pointer}->{end}")

💡 The algorithm correctly records large missing ranges.

move_right

Update pointer to 51

Pointer moves to curr + 1 = 51 to continue scanning after found number 50.

💡 Advancing pointer ensures we check numbers after the current found number.

Line:

pointer = curr + 1

💡 Pointer progresses through the range.

compare

Binary search for pointer=51

Binary search finds index 4 where nums[4] = 75, which is greater than pointer 51.

💡 Next number after pointer is 75, indicating another missing range.

Line:

idx = bisect.bisect_left(nums, pointer)

💡 We will record missing range from 51 to 74 next.

insert

Record missing range 51->74

Pointer (51) is less than found number (75), so missing range is from 51 to 74. We add '51->74' to missing.

💡 We continue recording missing ranges as we find gaps.

Line:

if pointer < curr:
    end = curr - 1
    if pointer != end:
        missing.append(f"{pointer}->{end}")

💡 The algorithm handles multiple missing ranges correctly.

move_right

Update pointer to 76

Pointer moves to curr + 1 = 76 to continue scanning after found number 75.

💡 Pointer moves forward to check for missing numbers after 75.

Line:

pointer = curr + 1

💡 Pointer advances through the range.

compare

Binary search for pointer=76

Binary search returns idx=5 which is equal to len(nums), meaning no number ≥ pointer in nums.

💡 No more numbers in nums after pointer means remaining range is missing.

Line:

idx = bisect.bisect_left(nums, pointer)

💡 We must record the final missing range from pointer to upper.

insert

Record final missing range 76->99

Since no number ≥ pointer, and pointer (76) ≤ upper (99), we record missing range from 76 to 99.

💡 The last missing range covers all numbers from pointer to upper.

Line:

if idx == len(nums):
    if pointer <= upper:
        if pointer == upper:
            missing.append(str(pointer))
        else:
            missing.append(f"{pointer}->{upper}")

💡 Algorithm correctly handles missing ranges at the end of the range.

prune

End loop and return missing ranges

No more numbers to check, so the algorithm ends and returns the missing ranges found.

💡 The loop terminates when pointer passes upper or no more numbers in nums.

Line:

break
return missing

💡 The final answer contains all missing ranges in the given bounds.

import bisect

def find_missing_ranges(nums, lower, upper):
    missing = []  # STEP 1
    pointer = lower  # STEP 1
    while pointer <= upper:  # STEP 2 loop start
        idx = bisect.bisect_left(nums, pointer)  # STEP 2,6,9,12,15
        if idx == len(nums):  # STEP 15
            if pointer <= upper:  # STEP 16
                if pointer == upper:
                    missing.append(str(pointer))
                else:
                    missing.append(f"{pointer}->{upper}")
            break  # STEP 17
        curr = nums[idx]  # STEP 3
        if pointer < curr:  # STEP 7,10,13
            end = curr - 1
            if pointer == end:
                missing.append(str(pointer))
            else:
                missing.append(f"{pointer}->{end}")
        pointer = curr + 1  # STEP 4,8,11,14
    return missing  # STEP 17

if __name__ == "__main__":
    nums = [0, 1, 3, 50, 75]
    lower = 0
    upper = 99
    print(find_missing_ranges(nums, lower, upper))

📊

Missing Ranges - Watch the Algorithm Execute, Step by Step

Watching this step-by-step helps you understand how binary search efficiently finds missing ranges without scanning every number, revealing the power of combining sorting and searching.

setup

pointer

0

0

1

1

3

2

50

3

75

4

Result: []

compare

idx

0

0

1

1

3

2

50

3

75

4

Result: []

move_right

idx

0

0

pointer

1

1

3

2

50

3

75

4

Result: []

compare

0

0

idx

1

1

3

2

50

3

75

4

Result: []

move_right

0

0

idx

1

1

pointer

3

2

50

3

75

4

Result: []

compare

0

0

1

1

idx

3

2

50

3

75

4

Result: []

record

0

0

1

1

idx

3

2

50

3

75

4

Result: ["2"]

move_right

0

0

1

1

3

2

50

3

pointer

75

4

Result: ["2"]

compare

0

0

1

1

3

2

idx

50

3

pointer

75

4

Result: ["2"]

record

0

0

1

1

3

2

idx

50

3

pointer

75

4

Result: ["2","4->49"]

move_right

0

0

1

1

3

2

50

3

75

4

Result: ["2","4->49"]

compare

0

0

1

1

3

2

50

3

idx

75

4

Result: ["2","4->49"]

record

0

0

1

1

3

2

50

3

idx

75

4

Result: ["2","4->49","51->74"]

move_right

0

0

1

1

3

2

50

3

75

4

Result: ["2","4->49","51->74"]

compare

0

0

1

1

3

2

50

3

75

4

Result: ["2","4->49","51->74"]

record

0

0

1

1

3

2

50

3

75

4

Result: ["2","4->49","51->74","76->99"]

prune

0

0

1

1

3

2

50

3

75

4

Result: ["2","4->49","51->74","76->99"]

Key Takeaways

✓ Binary search efficiently finds the next number in the array greater or equal to the current pointer, avoiding scanning every number.

This efficiency is hard to see from code alone but becomes clear when watching pointer and idx move step-by-step.

✓ The pointer moves forward after processing each found number or missing range, ensuring the entire range from lower to upper is covered without overlap.

Seeing pointer updates visually helps understand how the algorithm progresses through the range.

✓ Missing ranges are recorded differently for single missing numbers and ranges, showing careful handling of edge cases.

The visualization clarifies when to record 'x' versus 'x->y', which can be confusing reading code alone.

Practice

1. You are given a list of non-negative integers and need to arrange them such that they form the largest possible number when concatenated. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Sort the numbers as strings using a custom comparator that compares concatenations.

B. Use a greedy approach that always picks the largest number first.

C. Generate all permutations of the numbers and select the maximum concatenation.

D. Apply dynamic programming to build the largest number from subproblems.

Solution

1. Step 1: Understand problem constraints

   The problem requires ordering numbers to maximize concatenated value, which is not solved by simple numeric or lexicographic sorting.

2. Step 2: Identify correct approach

   Sorting with a custom comparator comparing concatenations (a+b vs b+a) ensures correct relative order for maximum combined number.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Custom comparator sorting is the standard optimal approach [OK]

Hint: Largest number needs custom string concatenation sort [OK]

Common Mistakes:

• Assuming numeric sort or lexicographic sort suffices

2. The following code attempts to find the minimum absolute difference but contains a subtle bug. Which line causes incorrect results?

def minimum_abs_difference(arr):
    min_diff = float('inf')
    for i in range(len(arr) - 1):
        diff = arr[i + 1] - arr[i]
        if diff < min_diff:
            min_diff = diff
    arr.sort()
    return min_diff

medium

A. Line 2: initializing min_diff before sorting

B. Line 6: sorting after scanning pairs

C. Line 7: returning min_diff without recomputing

D. Line 3: iterating without sorting first

Solution

1. Step 1: Identify order of operations

   The array is scanned for differences before sorting, so adjacent pairs are not guaranteed to be closest.

2. Step 2: Pinpoint the bug

   Line 3 iterates over unsorted array, causing incorrect min_diff.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Sorting must happen before scanning adjacent pairs [OK]

Hint: Must sort before scanning adjacent pairs [OK]

Common Mistakes:

• Sorting after scanning
• Not updating min_diff correctly

3. What is the time complexity of the optimal wiggle sort algorithm that uses sorting, median finding, and in-place three-way partitioning with virtual indexing on an input array of length n?

medium

A. O(n log n) because median finding requires sorting and partitioning is linear

B. O(n) because partitioning and virtual indexing are linear time operations

C. O(n^2) because of repeated swaps during three-way partitioning

D. O(n log n) due to the initial sorting step dominating the runtime

Solution

1. Step 1: Identify the dominant operation

   The algorithm first sorts the array, which takes O(n log n) time.

2. Step 2: Analyze partitioning and median finding

   Median is found by indexing the sorted array (O(1)), and three-way partitioning with virtual indexing runs in O(n) time.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sorting dominates, so overall complexity is O(n log n) [OK]

Hint: Sorting dominates time complexity despite linear partitioning [OK]

Common Mistakes:

• Assuming median finding is O(n) without sorting
• Confusing partitioning swaps as quadratic
• Ignoring sorting step's cost

4. Consider the following buggy implementation of wiggle sort. Which line contains the subtle bug that causes the algorithm to fail on inputs with duplicates?

medium

A. Line 9: def virtual_index(i): return (1 + 2 * i) % (n | 1)

B. Line 3: nums.sort()

C. Line 4: median = nums[n // 2]

D. Line 15: elif nums[vi] < median:

Solution

1. Step 1: Identify median calculation

   The median is incorrectly chosen as nums[n // 2], which is the upper median for even-length arrays, but the algorithm requires the lower median nums[(n - 1) // 2].

2. Step 2: Understand impact on partitioning

   Incorrect median causes wrong partitioning of elements equal to median, leading to clustering and violation of wiggle property especially with duplicates.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Correct median index is (n - 1) // 2, not n // 2 [OK]

Hint: Median index off-by-one breaks partitioning with duplicates [OK]

Common Mistakes:

• Using n//2 instead of (n-1)//2 for median
• Ignoring duplicates in partitioning
• Misusing virtual indexing

5. Suppose the input array can contain duplicate elements and negative numbers. Which modification to the optimal approach ensures correct minimum absolute difference calculation?

hard

A. Sort the array and scan adjacent pairs, but use absolute difference instead of subtraction.

B. Sort the array and scan adjacent pairs using subtraction as is, since sorting orders negatives correctly.

C. Use nested loops to compare all pairs because sorting fails with negatives.

D. Ignore duplicates and negatives since they don't affect minimum difference.

Solution

1. Step 1: Understand sorting with negatives

   Sorting places negative numbers in ascending order correctly.

2. Step 2: Adjacent subtraction works for minimum difference

   Difference between adjacent sorted elements is always non-negative or zero; no need for absolute value.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Sorting handles negatives; subtraction suffices [OK]

Hint: Sorting handles negatives; no abs needed on adjacent pairs [OK]

Common Mistakes:

• Using abs unnecessarily
• Thinking sorting fails with negatives