Missing Ranges

📋

Missing Ranges

Edge cases:

</>

IDE

def find_missing_ranges(nums: list[int], lower: int, upper: int) -> list[str]:public List<String> findMissingRanges(int[] nums, int lower, int upper)vector<string> findMissingRanges(vector<int>& nums, int lower, int upper)function findMissingRanges(nums, lower, upper)

def find_missing_ranges(nums, lower, upper):
    # Write your solution here
    pass

class Solution {
    public List<String> findMissingRanges(int[] nums, int lower, int upper) {
        // Write your solution here
        return new ArrayList<>();
    }
}

#include <vector>
#include <string>
using namespace std;

vector<string> findMissingRanges(vector<int>& nums, int lower, int upper) {
    // Write your solution here
    return {};
}

function findMissingRanges(nums, lower, upper) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: ["2->49", "51->74", "76->99"]Missed single missing number '2' as a separate range; merged incorrectly or skipped.✅ Add condition to handle single missing numbers as separate strings, not merged ranges.

Wrong: ["0->3"]Returned full range for empty nums but lower and upper are equal or small range.✅ Check if lower == upper and return single number string instead of range.

Wrong: ["0", "3->9"]Missed single missing number '3' as separate range; merged incorrectly.✅ Distinguish gap size 1 and format as single number string.

Wrong: ["1->10"]Merged all missing single numbers into one large range incorrectly.✅ Check gaps between consecutive nums and add single numbers separately.

Wrong: []Fails to detect missing ranges when duplicates cause false negatives.✅ Ensure input nums is unique and sorted before processing.

✓

Test Cases

Focus on handling empty inputs and boundary cases correctly.

Watch out for subtle off-by-one errors and input constraints violations.

Think about time complexity and avoid brute force over large ranges.

t1_01basic

Input{"nums":[0,1,3,50,75],"lower":0,"upper":99}

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

⏱ Performance - must finish in 2000ms

Numbers 2, 4 to 49, 51 to 74, and 76 to 99 are missing from the array within the given bounds.

💡 Consider scanning through nums and checking gaps between consecutive elements.

💡 Check if the difference between consecutive numbers is more than 1 to identify missing ranges.

💡 For each gap, add a single number string if gap size is 1, else add 'start->end' format.

Why it failed: Failed to identify missing ranges correctly; likely off-by-one errors in gap detection. Fix by ensuring gaps are detected when nums[i] > prev + 1 and format ranges accordingly.

✓ Correctly identifies all missing ranges including single numbers and ranges.

t1_02basic

Input{"nums":[1,2,4,7],"lower":0,"upper":9}

Expected["0","3","5->6","8->9"]

⏱ Performance - must finish in 2000ms

Missing numbers are 0, 3, 5 to 6, and 8 to 9 within the range 0 to 9.

💡 Don't forget to check for missing ranges before the first element and after the last element.

💡 Use a variable to track the previous number and compare with current to find gaps.

💡 Add missing ranges before nums[0] if lower < nums[0], and after nums[-1] if upper > nums[-1].

Why it failed: Missed missing ranges at the boundaries (before first or after last element). Fix by checking and adding ranges before nums[0] and after nums[-1].

✓ Correctly handles missing ranges at the start and end of the range.

t2_01edge

Input{"nums":[],"lower":1,"upper":3}

Expected["1->3"]

⏱ Performance - must finish in 2000ms

Empty nums means entire range 1 to 3 is missing.

💡 If nums is empty, the entire range from lower to upper is missing.

💡 Check if nums is empty before processing gaps.

💡 Return a single range 'lower->upper' if lower != upper, else single number string.

Why it failed: Fails to handle empty nums array; returns empty list or incorrect ranges. Fix by adding a condition to return full range when nums is empty.

✓ Correctly returns full missing range when nums is empty.

t2_02edge

Input{"nums":[5],"lower":5,"upper":5}

Expected[]

⏱ Performance - must finish in 2000ms

Single element equals lower and upper, so no missing ranges.

💡 When lower equals upper and nums contains that number, no missing ranges exist.

💡 Check if nums contains the only number in the range.

💡 Return empty list if no missing numbers found.

Why it failed: Incorrectly returns missing ranges when nums contains the only number in range. Fix by checking if nums covers the entire single number range.

✓ Correctly returns empty list when no missing numbers.

t2_03edge

Input{"nums":[0,1,2,3,4],"lower":0,"upper":4}

Expected[]

⏱ Performance - must finish in 2000ms

nums contains all numbers in the range, so no missing ranges.

💡 If nums covers the entire range from lower to upper, no missing ranges exist.

💡 Check if there are any gaps between consecutive nums elements.

💡 Return empty list if no gaps found.

Why it failed: Fails to detect no missing ranges when nums covers entire range. Fix by verifying gaps between all consecutive elements and boundaries.

✓ Correctly returns empty list when no missing numbers.

t2_04edge

Input{"nums":[10],"lower":0,"upper":20}

Expected["0->9","11->20"]

⏱ Performance - must finish in 2000ms

Single element at boundary with missing ranges before and after.

💡 Check for missing ranges before the first element and after the last element.

💡 Use previous pointer initialized to lower - 1 to detect gaps.

💡 Add ranges accordingly for gaps before nums[0] and after nums[-1].

Why it failed: Misses missing ranges before or after single element at boundary. Fix by checking boundaries explicitly.

✓ Correctly identifies missing ranges before and after single element.

t3_01corner

Input{"nums":[2,4,6,8],"lower":1,"upper":10}

Expected["1","3","5","7","9->10"]

⏱ Performance - must finish in 2000ms

Missing numbers are 1, 3, 5, 7, and 9 to 10.

💡 Check carefully for single missing numbers between elements.

💡 Don't merge single missing numbers into ranges incorrectly.

💡 Add single number strings for gaps of size 1, ranges for larger gaps.

Why it failed: Incorrectly merges single missing numbers into ranges or misses them. Fix by distinguishing gap size 1 and formatting accordingly.

✓ Correctly distinguishes single missing numbers and ranges.

t3_02corner

Input{"nums":[1,2,2,3],"lower":1,"upper":3}

Expected[]

⏱ Performance - must finish in 2000ms

Input violates unique elements constraint; duplicates ignored or handled. No missing numbers in 1 to 3.

💡 Input should have unique elements; duplicates may cause incorrect gaps.

💡 Ensure input is sorted and unique before processing.

💡 If duplicates present, remove or ignore them to avoid false gaps.

Why it failed: Fails due to duplicates causing false missing ranges. Fix by enforcing uniqueness or ignoring duplicates before gap detection.

✓ Handles or ignores duplicates correctly, no false missing ranges.

t3_03corner

Input{"nums":[0,2,4,6,8],"lower":0,"upper":8}

Expected["1","3","5","7"]

⏱ Performance - must finish in 2000ms

Missing numbers are all odd numbers between 0 and 8.

💡 Check all gaps between consecutive elements carefully.

💡 Avoid off-by-one errors when calculating missing ranges.

💡 Use inclusive checks: missing if nums[i] > prev + 1.

Why it failed: Off-by-one errors cause missing numbers to be skipped or merged incorrectly. Fix by using strict inequality and inclusive range checks.

✓ Correctly identifies all missing single numbers in gaps.

t4_01performance

Input{"nums":[0,2,4,6,8,10,12,14,16,18,20,22,24,26,28,30,32,34,36,38,40,42,44,46,48,50,52,54,56,58,60,62,64,66,68,70,72,74,76,78,80,82,84,86,88,90,92,94,96,98,100,102,104,106,108,110,112,114,116,118,120,122,124,126,128,130,132,134,136,138,140,142,144,146,148,150,152,154,156,158,160,162,164,166,168,170,172,174,176,178,180,182,184,186,188,190,192,194,196,198],"lower":0,"upper":199}

Expected["1","3","5","7","9","11","13","15","17","19","21","23","25","27","29","31","33","35","37","39","41","43","45","47","49","51","53","55","57","59","61","63","65","67","69","71","73","75","77","79","81","83","85","87","89","91","93","95","97","99","101","103","105","107","109","111","113","115","117","119","121","123","125","127","129","131","133","135","137","139","141","143","145","147","149","151","153","155","157","159","161","163","165","167","169","171","173","175","177","179","181","183","185","187","189","191","193","195","197","199"]

⏱ Performance - must finish in 2000ms

n=100, nums contains even numbers from 0 to 198, missing odd numbers in range 0 to 199. O(n) or O(n log n) solution must complete within 2s.

💡 Brute force checking every number in range is too slow for large ranges.

💡 Use scanning through nums and detecting gaps efficiently.

💡 Avoid iterating over entire range; rely on nums array gaps.

Why it failed: TLE due to brute force iteration over large range. Fix by scanning nums and detecting gaps without enumerating every number.

✓ Efficient solution runs within time limits using gap detection.

Practice

1. Consider the following code snippet implementing the optimal solution to rearrange an array so no two adjacent elements are equal. What is the output of the function call make_array_beautiful_heap([1,1,2])?

easy

A. []

B. [1, 1, 2]

C. [1, 2, 1]

D. [2, 1, 1]

Solution

1. Step 1: Check max frequency condition

   Frequency counts: 1 -> 2, 2 -> 1; max_freq=2, n=3, (n+1)//2=2, so condition passes.

2. Step 2: Trace heap operations and result construction

   Heap: [(-2,1), (-1,2)] Pop (-2,1): res=[1], prev_count=-1, prev_num=1 Pop (-1,2): res=[1,2], push back (-1,1) since prev_count<0 Pop (-1,1): res=[1,2,1] Return [1,2,1]

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Output matches expected rearrangement with no adjacent duplicates [OK]

Hint: Check max frequency and simulate heap pops [OK]

Common Mistakes:

• Returning original array without rearrangement
• Confusing heap push/pop order

2. You are given a list of time points in 24-hour format (e.g., "23:59", "00:00") and need to find the minimum difference in minutes between any two time points, considering the circular nature of the clock (i.e., times wrap around midnight). Which approach guarantees an optimal solution for this problem?

easy

A. Sort the times converted to minutes, then find the minimum difference between adjacent times including the circular pair (last and first).

B. Use a brute force nested loop to compare all pairs of times and compute their differences.

C. Use dynamic programming to store minimum differences while iterating through the times.

D. Apply a greedy algorithm that picks the closest time pairs without sorting.

Solution

1. Step 1: Understand the circular nature of time

   Since times wrap around midnight, the minimum difference might be between the last and first times after sorting.

2. Step 2: Sort and check adjacent differences including circular pair

   Sorting times converted to minutes allows a single pass to find minimum adjacent differences, including the circular pair, guaranteeing optimality.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sorting enables O(n log n) solution that correctly handles circular wrap [OK]

Hint: Sort times and check adjacent pairs including wrap [OK]

Common Mistakes:

• Using brute force is too slow for large inputs
• Ignoring circular difference between last and first times
• Trying greedy without sorting fails on wrap-around

3. You are given a sorted array of integers and a quadratic function f(x) = ax² + bx + c. You need to return a sorted array of the values f(x) applied to each element x in the input array. Which approach guarantees an optimal O(n) time solution?

easy

A. Use two pointers at the start and end of the input array and fill the output array from the end or start depending on the sign of a, leveraging the parabola shape.

B. Use dynamic programming to store intermediate results and build the sorted transformed array incrementally.

C. Apply the quadratic function to each element and then sort the resulting array using a standard sorting algorithm.

D. Use a max-heap to insert transformed values and then extract them in sorted order.

Solution

1. Step 1: Understand the parabola shape

   The quadratic function forms a parabola. If a >= 0, the largest values are at the ends of the input array; if a < 0, the smallest values are at the ends.

2. Step 2: Use two pointers to fill output

   By comparing transformed values at both ends, we can fill the output array from the appropriate end in O(n) time without sorting.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Two pointers leverage sorted input and parabola shape for linear time [OK]

Hint: Two pointers exploit parabola shape for O(n) [OK]

Common Mistakes:

• Assuming sorting is always needed after transformation
• Trying DP without leveraging input order

4. Suppose the input array can contain colors represented by integers 0, 1, 2, and 3, and you want to sort them in order (0 first, then 1, then 2, then 3) in one pass with constant extra space. Which modification to the Dutch National Flag algorithm is correct?

hard

A. Use counting sort instead, as the one-pass three-pointer approach cannot be directly extended to four colors.

B. Extend the algorithm by adding a fourth pointer and perform multiple passes to partition each color.

C. Modify the algorithm to use three pointers but with nested loops to handle the extra color.

D. Apply the Dutch National Flag algorithm twice: first to separate 0 and non-0, then on the non-0 part to separate 1, 2, and 3.

Solution

1. Step 1: Understand the limitation of Dutch National Flag algorithm

   It is designed specifically for three distinct values using three pointers.

2. Step 2: Consider extension to four colors

   Extending to four colors in one pass with constant space is non-trivial; the algorithm does not generalize easily.

3. Step 3: Identify correct approach

   Counting sort is a stable, simple approach for small fixed number of colors and works in O(n) time with O(1) space for fixed range.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Counting sort handles multiple colors easily; Dutch Flag is specialized for three [OK]

Hint: Dutch Flag is for 3 colors; counting sort handles more colors easily [OK]

Common Mistakes:

• Trying to add pointers and keep one-pass for 4 colors
• Assuming Dutch Flag generalizes directly
• Using nested loops that increase complexity

5. Suppose the problem changes: now you must sort each diagonal but allow elements to be reused multiple times (i.e., duplicates can be placed anywhere along the diagonal). Which modification to the algorithm correctly handles this variant efficiently?

hard

A. Sort each diagonal once and store sorted arrays; assign elements from these arrays repeatedly as needed.

B. Use counting sort per diagonal to handle duplicates efficiently and assign elements accordingly.

C. Use the same min-heap approach but skip popping elements to allow reuse.

D. Apply dynamic programming to track reuse counts and reconstruct diagonals with duplicates.

Solution

1. Step 1: Recognize reuse implies duplicates can appear multiple times

   Min-heaps popping elements once won't allow reuse; we need a method that counts frequencies.

2. Step 2: Use counting sort per diagonal

   Counting sort efficiently handles duplicates by frequency counts, allowing reuse without repeated heap operations.

3. Step 3: Assign elements back using frequency counts

   Reconstruct diagonals by placing elements according to counts, supporting reuse efficiently.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Counting sort suits duplicates and reuse better than heap popping [OK]

Hint: Counting sort handles duplicates and reuse efficiently [OK]

Common Mistakes:

• Trying to reuse popped heap elements
• Re-sorting entire matrix repeatedly
• Using DP unnecessarily complicates solution