Missing Ranges

🎯

Missing Ranges

easySORT_SEARCHAmazonGoogleFacebook

Imagine you are monitoring a sequence of daily temperature readings, but some days' data is missing. You want to quickly identify which days have missing data ranges.

💡 This problem is about scanning a sorted list to find gaps or missing intervals. Beginners often struggle because they try to check every number individually instead of leveraging the sorted order to detect ranges efficiently.

📋

Problem Statement

Given a sorted integer array nums and two integers lower and upper, return the smallest sorted list of ranges that cover every missing number in the inclusive range [lower, upper] that is not in nums. Each missing range should be represented as a string: a single number if the range contains only one number, or 'start->end' if it contains multiple numbers.

0 ≤ nums.length ≤ 10^5-10^9 ≤ lower ≤ upper ≤ 10^9nums is sorted in ascending order and contains unique elements

💡

Example

Input"nums = [0, 1, 3, 50, 75], lower = 0, upper = 99"

Output24->4951->7476->99

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

• Empty nums array → entire range is missing
• nums contains all numbers in range → no missing ranges
• lower equals upper → single number range
• nums with only one element at the boundary → missing ranges before or after

⚠️

Common Mistakes

Not handling the missing range at the start (before first element)

Misses missing numbers between lower and first element

✅ Initialize previous pointer to lower - 1 and check gap before first element

Not handling the missing range at the end (after last element)

Misses missing numbers between last element and upper

✅ Add sentinel iteration or check after loop to handle trailing missing range

Incorrectly formatting single number ranges as 'start->end'

Output does not match expected format, causing wrong answer

✅ Check if start == end and output single number string instead of range

Using linear scan over entire range when range is huge

Solution times out or is inefficient

✅ Use scanning nums approach or binary search to avoid scanning every number

Not considering empty nums array

Code may crash or return incorrect result

✅ Handle empty nums by returning the entire range as missing

🧠

Brute Force (Check Every Number in Range)

💡 This approach exists to build intuition by directly checking each number in the range, which is simple but inefficient for large ranges.

Intuition

Iterate through every number from lower to upper and check if it is in nums. If not, record it as missing. Group consecutive missing numbers into ranges.

Algorithm

1. Initialize an empty list to store missing ranges.
2. Iterate from lower to upper inclusive.
3. For each number, check if it is in nums.
4. If not, track consecutive missing numbers and add them as ranges.

💡 The challenge is to correctly group consecutive missing numbers into ranges while scanning every number.

</>

Code

def find_missing_ranges(nums, lower, upper):
    missing = []
    nums_set = set(nums)
    start = None
    for num in range(lower, upper + 1):
        if num not in nums_set:
            if start is None:
                start = num
        else:
            if start is not None:
                if start == num - 1:
                    missing.append(str(start))
                else:
                    missing.append(f"{start}->{num - 1}")
                start = None
    if start is not None:
        if start == upper:
            missing.append(str(start))
        else:
            missing.append(f"{start}->{upper}")
    return missing

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

Line Notes

nums_set = set(nums)Convert list to set for O(1) membership checks

for num in range(lower, upper + 1):Scan every number in the full range to detect missing ones

if num not in nums_set:Check if current number is missing

if start is None:Start a new missing range when first missing number found

if start == num - 1:Single number missing range vs multiple numbers

missing.append(f"{start}->{num - 1}")Add range string for multiple missing numbers

if start is not None:Handle trailing missing range after loop ends

import java.util.*;
public class MissingRanges {
    public static List<String> findMissingRanges(int[] nums, int lower, int upper) {
        List<String> missing = new ArrayList<>();
        Set<Integer> numSet = new HashSet<>();
        for (int num : nums) numSet.add(num);
        Integer start = null;
        for (int num = lower; num <= upper; num++) {
            if (!numSet.contains(num)) {
                if (start == null) start = num;
            } else {
                if (start != null) {
                    if (start == num - 1) missing.add(String.valueOf(start));
                    else missing.add(start + "->" + (num - 1));
                    start = null;
                }
            }
        }
        if (start != null) {
            if (start == upper) missing.add(String.valueOf(start));
            else missing.add(start + "->" + upper);
        }
        return missing;
    }

    public static void main(String[] args) {
        int[] nums = {0, 1, 3, 50, 75};
        int lower = 0, upper = 99;
        System.out.println(findMissingRanges(nums, lower, upper));
    }
}

Line Notes

Set<Integer> numSet = new HashSet<>();Use HashSet for O(1) membership checks

for (int num = lower; num <= upper; num++) {Iterate through entire range to find missing numbers

if (!numSet.contains(num)) {Detect missing numbers

if (start == null) start = num;Mark start of missing range

if (start != null) {Handle trailing missing range after loop

if (start == num - 1) missing.add(String.valueOf(start));Single number missing range

missing.add(start + "->" + (num - 1));Add range string for multiple missing numbers

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

vector<string> findMissingRanges(vector<int>& nums, int lower, int upper) {
    unordered_set<int> numSet(nums.begin(), nums.end());
    vector<string> missing;
    int start = -1;
    for (int num = lower; num <= upper; num++) {
        if (numSet.find(num) == numSet.end()) {
            if (start == -1) start = num;
        } else {
            if (start != -1) {
                if (start == num - 1) missing.push_back(to_string(start));
                else missing.push_back(to_string(start) + "->" + to_string(num - 1));
                start = -1;
            }
        }
    }
    if (start != -1) {
        if (start == upper) missing.push_back(to_string(start));
        else missing.push_back(to_string(start) + "->" + to_string(upper));
    }
    return missing;
}

int main() {
    vector<int> nums = {0, 1, 3, 50, 75};
    int lower = 0, upper = 99;
    vector<string> result = findMissingRanges(nums, lower, upper);
    for (auto& s : result) cout << s << " ";
    cout << endl;
    return 0;
}

Line Notes

unordered_set<int> numSet(nums.begin(), nums.end());Hash set for O(1) membership checks

for (int num = lower; num <= upper; num++) {Scan entire range to find missing numbers

if (numSet.find(num) == numSet.end()) {Check if number is missing

if (start == -1) start = num;Mark start of missing range

if (start != -1) {Handle trailing missing range after loop

if (start == num - 1) missing.push_back(to_string(start));Single number missing range

missing.push_back(to_string(start) + "->" + to_string(num - 1));Add range string for multiple missing numbers

function findMissingRanges(nums, lower, upper) {
    const numSet = new Set(nums);
    const missing = [];
    let start = null;
    for (let num = lower; num <= upper; num++) {
        if (!numSet.has(num)) {
            if (start === null) start = num;
        } else {
            if (start !== null) {
                if (start === num - 1) missing.push(start.toString());
                else missing.push(`${start}->${num - 1}`);
                start = null;
            }
        }
    }
    if (start !== null) {
        if (start === upper) missing.push(start.toString());
        else missing.push(`${start}->${upper}`);
    }
    return missing;
}

// Example usage
console.log(findMissingRanges([0, 1, 3, 50, 75], 0, 99));

Line Notes

const numSet = new Set(nums);Create set for O(1) membership checks

for (let num = lower; num <= upper; num++) {Iterate through entire range to find missing numbers

if (!numSet.has(num)) {Detect missing numbers

if (start === null) start = num;Mark start of missing range

if (start !== null) {Handle trailing missing range after loop

if (start === num - 1) missing.push(start.toString());Single number missing range

missing.push(`${start}->${num - 1}`);Add range string for multiple missing numbers

⏱

Complexity

TimeO(upper - lower + n)

SpaceO(n) for the set and output

We scan every number in the range [lower, upper], which can be large, and use a set of size n for membership checks.

💡 If the range is 100 and nums length is 5, we do about 100 membership checks, which is inefficient for large ranges.

Interview Verdict: TLE for large ranges

This approach is too slow when the range is huge, so we need a better method that doesn't check every number.

🧠

Better Approach (Scan nums with Pointers)

💡 This approach leverages the sorted nature of nums to find missing ranges by scanning nums once, avoiding checking every number in the range.

Intuition

Use the nums array to identify gaps between consecutive elements and between the boundaries and the array ends to find missing ranges.

Algorithm

1. Initialize a previous pointer to lower - 1.
2. Iterate through nums plus one extra iteration for upper + 1 as a sentinel.
3. For each current number, check if there is a gap between previous and current.
4. If gap exists, add the missing range to the result.
5. Update previous to current.

💡 The trick is to treat lower - 1 and upper + 1 as boundaries to simplify gap detection at edges.

</>

Code

def find_missing_ranges(nums, lower, upper):
    missing = []
    prev = lower - 1
    for i in range(len(nums) + 1):
        curr = nums[i] if i < len(nums) else upper + 1
        if curr - prev > 1:
            start = prev + 1
            end = curr - 1
            if start == end:
                missing.append(str(start))
            else:
                missing.append(f"{start}->{end}")
        prev = curr
    return missing

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

Line Notes

prev = lower - 1Initialize previous pointer just before lower to handle start boundary

for i in range(len(nums) + 1):Iterate through nums plus one extra iteration for upper + 1 sentinel

curr = nums[i] if i < len(nums) else upper + 1Set current to nums[i] or sentinel beyond upper

if curr - prev > 1:Detect gap between previous and current

start = prev + 1Start of missing range is one after previous

end = curr - 1End of missing range is one before current

missing.append(str(start))Single number missing range

missing.append(f"{start}->{end}")Multiple number missing range

prev = currUpdate previous pointer

import java.util.*;
public class MissingRanges {
    public static List<String> findMissingRanges(int[] nums, int lower, int upper) {
        List<String> missing = new ArrayList<>();
        int prev = lower - 1;
        for (int i = 0; i <= nums.length; i++) {
            int curr = (i < nums.length) ? nums[i] : upper + 1;
            if (curr - prev > 1) {
                int start = prev + 1;
                int end = curr - 1;
                if (start == end) missing.add(String.valueOf(start));
                else missing.add(start + "->" + end);
            }
            prev = curr;
        }
        return missing;
    }

    public static void main(String[] args) {
        int[] nums = {0, 1, 3, 50, 75};
        int lower = 0, upper = 99;
        System.out.println(findMissingRanges(nums, lower, upper));
    }
}

Line Notes

int prev = lower - 1;Initialize previous pointer before lower boundary

for (int i = 0; i <= nums.length; i++) {Iterate through nums plus one sentinel iteration

int curr = (i < nums.length) ? nums[i] : upper + 1;Set current to nums[i] or sentinel beyond upper

if (curr - prev > 1) {Check if gap exists between prev and curr

int start = prev + 1;Start of missing range

int end = curr - 1;End of missing range

if (start == end) missing.add(String.valueOf(start));Single number missing range

else missing.add(start + "->" + end);Add range string for multiple missing numbers

prev = curr;Update previous pointer

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

vector<string> findMissingRanges(vector<int>& nums, int lower, int upper) {
    vector<string> missing;
    int prev = lower - 1;
    for (int i = 0; i <= (int)nums.size(); i++) {
        int curr = (i < (int)nums.size()) ? nums[i] : upper + 1;
        if (curr - prev > 1) {
            int start = prev + 1;
            int end = curr - 1;
            if (start == end) missing.push_back(to_string(start));
            else missing.push_back(to_string(start) + "->" + to_string(end));
        }
        prev = curr;
    }
    return missing;
}

int main() {
    vector<int> nums = {0, 1, 3, 50, 75};
    int lower = 0, upper = 99;
    vector<string> result = findMissingRanges(nums, lower, upper);
    for (auto& s : result) cout << s << " ";
    cout << endl;
    return 0;
}

Line Notes

int prev = lower - 1;Initialize previous pointer before lower boundary

for (int i = 0; i <= (int)nums.size(); i++) {Iterate through nums plus sentinel iteration

int curr = (i < (int)nums.size()) ? nums[i] : upper + 1;Set current to nums[i] or sentinel beyond upper

if (curr - prev > 1) {Detect gap between prev and curr

int start = prev + 1;Start of missing range

int end = curr - 1;End of missing range

if (start == end) missing.push_back(to_string(start));Single number missing range

else missing.push_back(to_string(start) + "->" + to_string(end));Add range string for multiple missing numbers

prev = curr;Update previous pointer

function findMissingRanges(nums, lower, upper) {
    const missing = [];
    let prev = lower - 1;
    for (let i = 0; i <= nums.length; i++) {
        let curr = (i < nums.length) ? nums[i] : upper + 1;
        if (curr - prev > 1) {
            let start = prev + 1;
            let end = curr - 1;
            if (start === end) missing.push(start.toString());
            else missing.push(`${start}->${end}`);
        }
        prev = curr;
    }
    return missing;
}

// Example usage
console.log(findMissingRanges([0, 1, 3, 50, 75], 0, 99));

Line Notes

let prev = lower - 1;Initialize previous pointer before lower boundary

for (let i = 0; i <= nums.length; i++) {Iterate through nums plus sentinel iteration

let curr = (i < nums.length) ? nums[i] : upper + 1;Set current to nums[i] or sentinel beyond upper

if (curr - prev > 1) {Detect gap between prev and curr

let start = prev + 1;Start of missing range

let end = curr - 1;End of missing range

if (start === end) missing.push(start.toString());Single number missing range

else missing.push(`${start}->${end}`);Add range string for multiple missing numbers

prev = curr;Update previous pointer

⏱

Complexity

TimeO(n)

SpaceO(1) extra space besides output

We scan nums once and detect gaps using simple arithmetic, no extra data structures needed.

💡 For n=100, we do only 100 iterations, much faster than scanning the entire range if it was large.

Interview Verdict: Accepted and efficient

This approach is optimal for this problem and is what you should implement in interviews.

🧠

Optimal Approach (Using Binary Search to Find Missing Ranges)

💡 This approach uses binary search to quickly find the position of boundaries and missing ranges, useful if nums is very large and range is huge.

Intuition

Use binary search to find the next number after a missing range start, then jump to that position to find the next gap, skipping unnecessary checks.

Algorithm

1. Initialize a pointer at lower.
2. While pointer ≤ upper, use binary search to find the smallest number in nums ≥ pointer.
3. If pointer < found number, record missing range from pointer to found number - 1.
4. Update pointer to found number + 1 and repeat.
5. If no number found, record missing range from pointer to upper and stop.

💡 Binary search lets us skip large chunks of the range by jumping to known numbers in nums.

</>

Code

import bisect

def find_missing_ranges(nums, lower, upper):
    missing = []
    pointer = lower
    while pointer <= upper:
        idx = bisect.bisect_left(nums, pointer)
        if idx == len(nums):
            # No more numbers in nums >= pointer
            if pointer <= upper:
                if pointer == upper:
                    missing.append(str(pointer))
                else:
                    missing.append(f"{pointer}->{upper}")
            break
        curr = nums[idx]
        if pointer < curr:
            end = curr - 1
            if pointer == end:
                missing.append(str(pointer))
            else:
                missing.append(f"{pointer}->{end}")
        pointer = curr + 1
    return missing

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

Line Notes

import bisectUse built-in binary search module for efficient searching

pointer = lowerStart scanning from lower boundary

idx = bisect.bisect_left(nums, pointer)Find index of smallest number >= pointer

if idx == len(nums):No more numbers in nums beyond pointer

if pointer == upper:Single number missing range at end

missing.append(f"{pointer}->{upper}")Add missing range to end

pointer = curr + 1Jump pointer past current number to find next gap

import java.util.*;
public class MissingRanges {
    public static List<String> findMissingRanges(int[] nums, int lower, int upper) {
        List<String> missing = new ArrayList<>();
        int pointer = lower;
        while (pointer <= upper) {
            int idx = Arrays.binarySearch(nums, pointer);
            if (idx < 0) idx = -idx - 1;
            if (idx == nums.length) {
                if (pointer <= upper) {
                    if (pointer == upper) missing.add(String.valueOf(pointer));
                    else missing.add(pointer + "->" + upper);
                }
                break;
            }
            int curr = nums[idx];
            if (pointer < curr) {
                int end = curr - 1;
                if (pointer == end) missing.add(String.valueOf(pointer));
                else missing.add(pointer + "->" + end);
            }
            pointer = curr + 1;
        }
        return missing;
    }

    public static void main(String[] args) {
        int[] nums = {0, 1, 3, 50, 75};
        int lower = 0, upper = 99;
        System.out.println(findMissingRanges(nums, lower, upper));
    }
}

Line Notes

int idx = Arrays.binarySearch(nums, pointer);Use binary search to find position of pointer in nums

if (idx < 0) idx = -idx - 1;Convert negative insertion point to index of next larger element

if (idx == nums.length) {No more numbers in nums beyond pointer

if (pointer == upper) missing.add(String.valueOf(pointer));Single number missing range at end

missing.add(pointer + "->" + upper);Add missing range to end

pointer = curr + 1;Jump pointer past current number to find next gap

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

vector<string> findMissingRanges(vector<int>& nums, int lower, int upper) {
    vector<string> missing;
    int pointer = lower;
    while (pointer <= upper) {
        auto it = lower_bound(nums.begin(), nums.end(), pointer);
        if (it == nums.end()) {
            if (pointer <= upper) {
                if (pointer == upper) missing.push_back(to_string(pointer));
                else missing.push_back(to_string(pointer) + "->" + to_string(upper));
            }
            break;
        }
        int curr = *it;
        if (pointer < curr) {
            int end = curr - 1;
            if (pointer == end) missing.push_back(to_string(pointer));
            else missing.push_back(to_string(pointer) + "->" + to_string(end));
        }
        pointer = curr + 1;
    }
    return missing;
}

int main() {
    vector<int> nums = {0, 1, 3, 50, 75};
    int lower = 0, upper = 99;
    vector<string> result = findMissingRanges(nums, lower, upper);
    for (auto& s : result) cout << s << " ";
    cout << endl;
    return 0;
}

Line Notes

auto it = lower_bound(nums.begin(), nums.end(), pointer);Binary search to find first number >= pointer

if (it == nums.end()) {No more numbers in nums beyond pointer

if (pointer == upper) missing.push_back(to_string(pointer));Single number missing range at end

missing.push_back(to_string(pointer) + "->" + to_string(upper));Add missing range to end

pointer = curr + 1;Jump pointer past current number to find next gap

int curr = *it;Dereference iterator to get current number

function findMissingRanges(nums, lower, upper) {
    const missing = [];
    let pointer = lower;
    while (pointer <= upper) {
        let left = 0, right = nums.length - 1;
        let idx = nums.length;
        while (left <= right) {
            let mid = Math.floor((left + right) / 2);
            if (nums[mid] >= pointer) {
                idx = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        if (idx === nums.length) {
            if (pointer <= upper) {
                if (pointer === upper) missing.push(pointer.toString());
                else missing.push(`${pointer}->${upper}`);
            }
            break;
        }
        let curr = nums[idx];
        if (pointer < curr) {
            let end = curr - 1;
            if (pointer === end) missing.push(pointer.toString());
            else missing.push(`${pointer}->${end}`);
        }
        pointer = curr + 1;
    }
    return missing;
}

// Example usage
console.log(findMissingRanges([0, 1, 3, 50, 75], 0, 99));

Line Notes

while (left <= right) {Perform binary search to find first number >= pointer

if (nums[mid] >= pointer) {Adjust right pointer to find leftmost suitable index

idx = mid;Update candidate index for binary search result

if (idx === nums.length) {No more numbers in nums beyond pointer

if (pointer === upper) missing.push(pointer.toString());Single number missing range at end

missing.push(`${pointer}->${upper}`);Add missing range to end

pointer = curr + 1;Jump pointer past current number to find next gap

⏱

Complexity

TimeO(n log n) worst case

SpaceO(1) extra space besides output

Each iteration uses binary search O(log n) and pointer moves forward, total O(n log n) in worst case.

💡 This is efficient if range is huge but nums is small, as we skip large gaps quickly.

Interview Verdict: Accepted, useful for very large ranges

Binary search is a good optimization when the range is huge compared to nums size.

📊

All Approaches - One-Glance Tradeoffs

💡 The scanning nums approach (Approach 2) is the best balance of simplicity and efficiency and should be coded in most interviews.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(upper - lower + n)	O(n)	No	N/A	Mention only - too slow for large ranges
2. Scan nums with pointers	O(n)	O(1)	No	N/A	Code this approach in interviews
3. Binary Search optimization	O(n log n)	O(1)	No	N/A	Mention if range is huge and nums is small

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding all approaches, and prepare to explain tradeoffs clearly in interviews.

How to Present

Step 1: Clarify input constraints and ask about edge cases.Step 2: Describe the brute force approach to show understanding.Step 3: Explain the better approach using scanning and pointers.Step 4: If asked, discuss binary search optimization for large ranges.Step 5: Code the better approach as it is optimal and accepted.Step 6: Test your code with edge cases and examples.

Time Allocation

Clarify: 2min → Approach: 3min → Code: 10min → Test: 5min. Total ~20min

What the Interviewer Tests

Interviewer tests your ability to leverage sorted input, handle edge cases, and optimize from brute force to efficient scanning.

Common Follow-ups

• What if nums is empty? → Return the entire range as missing.
• How to handle integer overflow when computing ranges? → Use long or careful arithmetic.
• Can you do this if nums is unsorted? → Sort first or use a set but lose efficiency.
• What if the range is very large? → Use binary search approach to skip large gaps.

💡 These follow-ups test your robustness and ability to adapt your solution to different constraints.

🔍

Pattern Recognition

When to Use

Use this pattern when you have a sorted array and need to find missing elements or gaps within a range.

Signature Phrases

missing numbers in a rangesmallest sorted list of rangescover every missing number

NOT This Pattern When

Problems that require finding duplicates or counting frequencies are different patterns.

Similar Problems

Find Missing Number - simpler version with one missing numberSummary Ranges - similar grouping of consecutive numbersMissing Number in Array - detecting missing elements in a sequence

Practice

1. 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

2. What is the time complexity of the optimal approach that sorts the array and scans adjacent pairs to find the minimum absolute difference?

medium

A. O(n) because scanning adjacent pairs is linear

B. O(n²) because every pair is compared

C. O(n log n) due to sorting, scanning is O(n)

D. O(log n) because sorting uses divide and conquer

Solution

1. Step 1: Identify sorting cost

   Sorting an array of size n takes O(n log n) time.

2. Step 2: Identify scanning cost

   Scanning adjacent pairs is a single pass O(n).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Sorting dominates total time -> O(n log n) [OK]

Hint: Sorting dominates; scanning is linear [OK]

Common Mistakes:

• Confusing scanning cost as sorting cost
• Assuming O(n) overall without sorting

3. The following code attempts to find the minimum time difference between time points. Which line contains a subtle bug that causes incorrect results on inputs with duplicate times?

def findMinDifference(timePoints):
    seen = [False] * 1440
    for t in timePoints:
        h, m = map(int, t.split(':'))
        total = h * 60 + m
        seen[total] = True
    prev = -1
    first = -1
    min_diff = 1440
    for i in range(1440):
        if seen[i]:
            if prev != -1:
                min_diff = min(min_diff, i - prev)
            else:
                first = i
            prev = i
    min_diff = min(min_diff, 1440 - prev + first)
    return min_diff

medium

A. Line updating min_diff inside the loop

B. Line initializing prev = -1

C. Line that sets seen[total] = True without checking duplicates

D. Line computing min_diff with circular difference after the loop

Solution

1. Step 1: Check duplicate detection logic

   The code sets seen[total] = True but does not check if seen[total] was already True, missing duplicates.

2. Step 2: Consequence of missing duplicate check

   Without detecting duplicates, the function cannot return 0 early, causing wrong minimum difference on duplicate inputs.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Adding a duplicate check before setting seen fixes the bug [OK]

Hint: Check for duplicate times before marking seen [OK]

Common Mistakes:

• Ignoring duplicates leads to wrong min difference
• Misplaced min_diff update
• Forgetting circular difference check

4. What is the time and space complexity of the optimal one-pass Dutch National Flag algorithm for sorting colors in an array of length n?

medium

A. Time: O(n log n), Space: O(1) due to in-place swaps

B. Time: O(n^2), Space: O(1) due to nested pointer updates

C. Time: O(n), Space: O(n) because it uses extra arrays for counting

D. Time: O(n), Space: O(1) because it scans array once with constant pointers

Solution

1. Step 1: Identify time complexity of outer loop

   The algorithm uses a single while loop with mid pointer moving forward, scanning each element at most once, so O(n).

2. Step 2: Identify space complexity

   Only three pointers (low, mid, high) are used, no extra arrays or recursion, so O(1) space.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Single pass with constant pointers -> O(n) time and O(1) space [OK]

Hint: One pass with constant pointers means O(n) time and O(1) space [OK]

Common Mistakes:

• Confusing counting sort space with Dutch Flag space
• Assuming nested loops cause O(n^2) time
• Thinking swaps add extra space

5. 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