Minimum Time Difference (Sort Circular Times)

🎯

Minimum Time Difference (Sort Circular Times)

mediumSORT_SEARCHAmazonGoogle

Imagine you are scheduling meetings across different time zones and want to find the smallest gap between any two meeting start times, considering the day wraps around at midnight.

💡 This problem involves understanding how to handle circular time differences and sorting times to efficiently find minimum gaps. Beginners often struggle with the circular nature of time and how to compare times that wrap around midnight.

📋

Problem Statement

Given a list of 24-hour clock times in 'HH:MM' format, return the minimum difference in minutes between any two time points in the list. The time difference is circular, meaning the difference between '23:59' and '00:00' is 1 minute.

1 ≤ n ≤ 10^5 (number of time points)Each time point is in the format 'HH:MM'Times are valid 24-hour times (00:00 to 23:59)

💡

Example

Input["23:59","00:00"]

Output1

The difference between 23:59 and 00:00 is 1 minute, which is the minimum possible.

Input["01:01","02:01","03:00"]

Output59

The minimum difference is between 02:01 and 03:00, which is 59 minutes.

• Only one time point → minimum difference is 0 or undefined (problem assumes at least two times)
• All time points are the same → minimum difference is 0
• Times spread evenly across the day → minimum difference is the smallest gap between adjacent sorted times
• Times near midnight and early morning → circular difference must be considered

⚠️

Common Mistakes

Ignoring circular difference between last and first times

Incorrect minimum difference, often too large

✅ Always check difference between last and first times after sorting

Not handling duplicate times

Misses minimum difference of zero, returns wrong result

✅ Detect duplicates early and return 0 immediately

Comparing times as strings instead of converting to minutes

Lexicographical comparison leads to wrong ordering and differences

✅ Convert times to total minutes before sorting or comparing

Using nested loops for large inputs

Solution times out or is inefficient

✅ Use sorting or bucket approach to reduce complexity

🧠

Brute Force (Nested Loops Checking All Pairs)

💡 This approach exists to build intuition by directly comparing every pair of times, helping beginners understand the problem's circular nature before optimizing.

Intuition

Convert all times to minutes, then compare every pair to find the minimum difference, considering the circular wrap-around at midnight.

Algorithm

1. Convert each time string to total minutes from 00:00.
2. Initialize minimum difference to a large number.
3. Use two nested loops to compare every pair of times.
4. Calculate the absolute difference and also consider the circular difference (1440 - difference).
5. Update the minimum difference if a smaller one is found.
6. Return the minimum difference found.

💡 Nested loops make it easy to understand but inefficient; the circular difference is the tricky part to get right.

</>

Code

def findMinDifference(timePoints):
    minutes = []
    for t in timePoints:
        h, m = map(int, t.split(':'))
        minutes.append(h * 60 + m)
    min_diff = 1440
    n = len(minutes)
    for i in range(n):
        for j in range(i + 1, n):
            diff = abs(minutes[i] - minutes[j])
            min_diff = min(min_diff, diff, 1440 - diff)
    return min_diff

# Example usage
if __name__ == '__main__':
    print(findMinDifference(["23:59", "00:00"]))  # Output: 1

Line Notes

for t in timePoints:Convert each time string to minutes for easier numeric comparison

h, m = map(int, t.split(':'))Parse hours and minutes from the time string

minutes.append(h * 60 + m)Convert time to total minutes from midnight

for i in range(n):Outer loop to pick first time point

for j in range(i + 1, n):Inner loop to pick second time point, avoiding repeats

diff = abs(minutes[i] - minutes[j])Calculate absolute difference between two times

min_diff = min(min_diff, diff, 1440 - diff)Update minimum difference considering circular wrap-around

return min_diffReturn the smallest difference found

import java.util.*;
public class Solution {
    public static int findMinDifference(List<String> timePoints) {
        List<Integer> minutes = new ArrayList<>();
        for (String t : timePoints) {
            String[] parts = t.split(":");
            int h = Integer.parseInt(parts[0]);
            int m = Integer.parseInt(parts[1]);
            minutes.add(h * 60 + m);
        }
        int minDiff = 1440;
        int n = minutes.size();
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int diff = Math.abs(minutes.get(i) - minutes.get(j));
                minDiff = Math.min(minDiff, Math.min(diff, 1440 - diff));
            }
        }
        return minDiff;
    }

    public static void main(String[] args) {
        List<String> times = Arrays.asList("23:59", "00:00");
        System.out.println(findMinDifference(times)); // Output: 1
    }
}

Line Notes

for (String t : timePoints)Iterate over each time string to convert to minutes

String[] parts = t.split(":")Split time string into hours and minutes

minutes.add(h * 60 + m)Convert time to total minutes and store

for (int i = 0; i < n; i++)Outer loop to select first time

for (int j = i + 1; j < n; j++)Inner loop to select second time without repeats

int diff = Math.abs(minutes.get(i) - minutes.get(j))Calculate absolute difference

minDiff = Math.min(minDiff, Math.min(diff, 1440 - diff))Update minimum difference considering circular wrap

return minDiffReturn the smallest difference found

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

int findMinDifference(vector<string>& timePoints) {
    vector<int> minutes;
    for (auto& t : timePoints) {
        int h = stoi(t.substr(0, 2));
        int m = stoi(t.substr(3, 2));
        minutes.push_back(h * 60 + m);
    }
    int minDiff = 1440;
    int n = minutes.size();
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            int diff = abs(minutes[i] - minutes[j]);
            minDiff = min(minDiff, min(diff, 1440 - diff));
        }
    }
    return minDiff;
}

int main() {
    vector<string> times = {"23:59", "00:00"};
    cout << findMinDifference(times) << endl; // Output: 1
    return 0;
}

Line Notes

for (auto& t : timePoints)Iterate over each time string to convert

int h = stoi(t.substr(0, 2))Extract hours from string

int m = stoi(t.substr(3, 2))Extract minutes from string

minutes.push_back(h * 60 + m)Convert to total minutes and store

for (int i = 0; i < n; i++)Outer loop for first time

for (int j = i + 1; j < n; j++)Inner loop for second time

int diff = abs(minutes[i] - minutes[j])Calculate absolute difference

minDiff = min(minDiff, min(diff, 1440 - diff))Update minimum difference considering circular wrap

return minDiffReturn the smallest difference

function findMinDifference(timePoints) {
    const minutes = [];
    for (const t of timePoints) {
        const [h, m] = t.split(':').map(Number);
        minutes.push(h * 60 + m);
    }
    let minDiff = 1440;
    const n = minutes.length;
    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
            const diff = Math.abs(minutes[i] - minutes[j]);
            minDiff = Math.min(minDiff, diff, 1440 - diff);
        }
    }
    return minDiff;
}

// Example usage
console.log(findMinDifference(["23:59", "00:00"])); // Output: 1

Line Notes

for (const t of timePoints)Iterate over each time string

const [h, m] = t.split(':').map(Number)Parse hours and minutes as numbers

minutes.push(h * 60 + m)Convert time to total minutes

for (let i = 0; i < n; i++)Outer loop for first time

for (let j = i + 1; j < n; j++)Inner loop for second time

const diff = Math.abs(minutes[i] - minutes[j])Calculate absolute difference

minDiff = Math.min(minDiff, diff, 1440 - diff)Update minimum difference considering circular wrap

return minDiffReturn the smallest difference found

⏱

Complexity

TimeO(n^2)

SpaceO(n)

We convert times in O(n), then compare every pair in nested loops O(n^2). Space is O(n) for storing converted times.

💡 For n=20, this means 20*19/2=190 comparisons, which is manageable, but for n=100000 it becomes 5 billion comparisons, which is too slow.

Interview Verdict: TLE / Use only to introduce

This approach is too slow for large inputs but helps understand the problem and correctness before optimizing.

🧠

Sorting + Single Pass to Find Minimum Adjacent Difference

💡 Sorting the times allows us to only check adjacent pairs for minimum difference, drastically reducing comparisons and handling circular wrap by checking first and last times.

Intuition

Convert times to minutes, sort them, then find the minimum difference between adjacent times in the sorted list, including the circular difference between last and first.

Algorithm

1. Convert all time points to minutes.
2. Sort the list of minutes.
3. Initialize minimum difference to the difference between the last and first times considering circular wrap.
4. Iterate through the sorted list and update minimum difference by comparing adjacent times.
5. Return the minimum difference found.

💡 Sorting reduces complexity and focusing on adjacent pairs simplifies the problem, but remembering to check circular difference is key.

</>

Code

def findMinDifference(timePoints):
    minutes = []
    for t in timePoints:
        h, m = map(int, t.split(':'))
        minutes.append(h * 60 + m)
    minutes.sort()
    min_diff = 1440 - (minutes[-1] - minutes[0])  # circular difference
    for i in range(1, len(minutes)):
        diff = minutes[i] - minutes[i - 1]
        min_diff = min(min_diff, diff)
    return min_diff

# Example usage
if __name__ == '__main__':
    print(findMinDifference(["23:59", "00:00"]))  # Output: 1

Line Notes

minutes.sort()Sort times to bring close times next to each other

min_diff = 1440 - (minutes[-1] - minutes[0])Initialize min_diff with circular difference between last and first times correctly

for i in range(1, len(minutes))Iterate through sorted times to check adjacent differences

diff = minutes[i] - minutes[i - 1]Calculate difference between adjacent times

min_diff = min(min_diff, diff)Update minimum difference if smaller found

return min_diffReturn the smallest difference

import java.util.*;
public class Solution {
    public static int findMinDifference(List<String> timePoints) {
        List<Integer> minutes = new ArrayList<>();
        for (String t : timePoints) {
            String[] parts = t.split(":");
            int h = Integer.parseInt(parts[0]);
            int m = Integer.parseInt(parts[1]);
            minutes.add(h * 60 + m);
        }
        Collections.sort(minutes);
        int minDiff = 1440 - (minutes.get(minutes.size() - 1) - minutes.get(0));
        for (int i = 1; i < minutes.size(); i++) {
            int diff = minutes.get(i) - minutes.get(i - 1);
            minDiff = Math.min(minDiff, diff);
        }
        return minDiff;
    }

    public static void main(String[] args) {
        List<String> times = Arrays.asList("23:59", "00:00");
        System.out.println(findMinDifference(times)); // Output: 1
    }
}

Line Notes

Collections.sort(minutes)Sort the list of times in ascending order

int minDiff = 1440 - (minutes.get(minutes.size() - 1) - minutes.get(0))Initialize minDiff with circular difference between last and first times correctly

for (int i = 1; i < minutes.size(); i++)Loop through sorted times to check adjacent differences

int diff = minutes.get(i) - minutes.get(i - 1)Calculate difference between adjacent times

minDiff = Math.min(minDiff, diff)Update minimum difference if smaller found

return minDiffReturn the smallest difference

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

int findMinDifference(vector<string>& timePoints) {
    vector<int> minutes;
    for (auto& t : timePoints) {
        int h = stoi(t.substr(0, 2));
        int m = stoi(t.substr(3, 2));
        minutes.push_back(h * 60 + m);
    }
    sort(minutes.begin(), minutes.end());
    int minDiff = 1440 - (minutes.back() - minutes[0]);
    for (int i = 1; i < minutes.size(); i++) {
        int diff = minutes[i] - minutes[i - 1];
        minDiff = min(minDiff, diff);
    }
    return minDiff;
}

int main() {
    vector<string> times = {"23:59", "00:00"};
    cout << findMinDifference(times) << endl; // Output: 1
    return 0;
}

Line Notes

sort(minutes.begin(), minutes.end())Sort times to bring close times next to each other

int minDiff = 1440 - (minutes.back() - minutes[0])Initialize minDiff with circular difference between last and first times correctly

for (int i = 1; i < minutes.size(); i++)Loop through sorted times to check adjacent differences

int diff = minutes[i] - minutes[i - 1]Calculate difference between adjacent times

minDiff = min(minDiff, diff)Update minimum difference if smaller found

return minDiffReturn the smallest difference

function findMinDifference(timePoints) {
    const minutes = [];
    for (const t of timePoints) {
        const [h, m] = t.split(':').map(Number);
        minutes.push(h * 60 + m);
    }
    minutes.sort((a, b) => a - b);
    let minDiff = 1440 - (minutes[minutes.length - 1] - minutes[0]);
    for (let i = 1; i < minutes.length; i++) {
        const diff = minutes[i] - minutes[i - 1];
        minDiff = Math.min(minDiff, diff);
    }
    return minDiff;
}

// Example usage
console.log(findMinDifference(["23:59", "00:00"])); // Output: 1

Line Notes

minutes.sort((a, b) => a - b)Sort times numerically ascending

let minDiff = 1440 - (minutes[minutes.length - 1] - minutes[0])Initialize minDiff with circular difference between last and first times correctly

for (let i = 1; i < minutes.length; i++)Loop through sorted times to check adjacent differences

const diff = minutes[i] - minutes[i - 1]Calculate difference between adjacent times

minDiff = Math.min(minDiff, diff)Update minimum difference if smaller found

return minDiffReturn the smallest difference

⏱

Complexity

TimeO(n log n)

SpaceO(n)

Converting times is O(n), sorting is O(n log n), and single pass to find min difference is O(n). Space is O(n) for storing times.

💡 For n=100000, sorting is feasible and much faster than brute force, making this approach practical for interviews.

Interview Verdict: Accepted / Optimal for large inputs

This approach balances simplicity and efficiency, making it the preferred solution in interviews.

🧠

Bucket Sort Optimization (Using Boolean Array for Times)

💡 Since times are limited to 1440 minutes in a day, we can use a boolean array to mark times and find minimum difference in O(n) time, avoiding sorting overhead.

Intuition

Mark each time point in a boolean array of size 1440, then scan the array to find the minimum difference between consecutive true entries, including circular wrap.

Algorithm

1. Create a boolean array of size 1440 initialized to false.
2. Convert each time to minutes and mark the corresponding index true; if duplicate found, return 0 immediately.
3. Scan the boolean array to find the minimum difference between consecutive true indices.
4. Also consider the circular difference between the last and first true indices.
5. Return the minimum difference found.

💡 This approach uses extra space but achieves linear time by exploiting the fixed time range and handles duplicates efficiently.

</>

Code

def findMinDifference(timePoints):
    seen = [False] * 1440
    for t in timePoints:
        h, m = map(int, t.split(':'))
        total = h * 60 + m
        if seen[total]:
            return 0  # duplicate times mean min diff is 0
        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

# Example usage
if __name__ == '__main__':
    print(findMinDifference(["23:59", "00:00"]))  # Output: 1

Line Notes

seen = [False] * 1440Create fixed-size array to mark times

if seen[total]: return 0If duplicate time found, minimum difference is zero

for i in range(1440)Scan all possible times in order

if seen[i]Check if this time was marked

min_diff = min(min_diff, i - prev)Update min difference between consecutive marked times

min_diff = min(min_diff, 1440 - prev + first)Check circular difference between last and first marked times

return min_diffReturn the smallest difference

import java.util.*;
public class Solution {
    public static int findMinDifference(List<String> timePoints) {
        boolean[] seen = new boolean[1440];
        for (String t : timePoints) {
            String[] parts = t.split(":");
            int h = Integer.parseInt(parts[0]);
            int m = Integer.parseInt(parts[1]);
            int total = h * 60 + m;
            if (seen[total]) return 0;
            seen[total] = true;
        }
        int prev = -1, first = -1, minDiff = 1440;
        for (int i = 0; i < 1440; i++) {
            if (seen[i]) {
                if (prev != -1) {
                    minDiff = Math.min(minDiff, i - prev);
                } else {
                    first = i;
                }
                prev = i;
            }
        }
        minDiff = Math.min(minDiff, 1440 - prev + first);
        return minDiff;
    }

    public static void main(String[] args) {
        List<String> times = Arrays.asList("23:59", "00:00");
        System.out.println(findMinDifference(times)); // Output: 1
    }
}

Line Notes

boolean[] seen = new boolean[1440]Create fixed-size boolean array for times

if (seen[total]) return 0Return 0 immediately if duplicate time found

for (int i = 0; i < 1440; i++)Scan all possible times in order

if (seen[i])Check if time is marked

minDiff = Math.min(minDiff, i - prev)Update min difference between consecutive marked times

minDiff = Math.min(minDiff, 1440 - prev + first)Check circular difference between last and first marked times

return minDiffReturn the smallest difference

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

int findMinDifference(vector<string>& timePoints) {
    vector<bool> seen(1440, false);
    for (auto& t : timePoints) {
        int h = stoi(t.substr(0, 2));
        int m = stoi(t.substr(3, 2));
        int total = h * 60 + m;
        if (seen[total]) return 0;
        seen[total] = true;
    }
    int prev = -1, first = -1, minDiff = 1440;
    for (int i = 0; i < 1440; i++) {
        if (seen[i]) {
            if (prev != -1) {
                minDiff = min(minDiff, i - prev);
            } else {
                first = i;
            }
            prev = i;
        }
    }
    minDiff = min(minDiff, 1440 - prev + first);
    return minDiff;
}

int main() {
    vector<string> times = {"23:59", "00:00"};
    cout << findMinDifference(times) << endl; // Output: 1
    return 0;
}

Line Notes

vector<bool> seen(1440, false)Create fixed-size boolean vector for times

if (seen[total]) return 0Return 0 if duplicate time found

for (int i = 0; i < 1440; i++)Scan all possible times in order

if (seen[i])Check if time is marked

minDiff = min(minDiff, i - prev)Update min difference between consecutive marked times

minDiff = min(minDiff, 1440 - prev + first)Check circular difference between last and first marked times

return minDiffReturn the smallest difference

function findMinDifference(timePoints) {
    const seen = new Array(1440).fill(false);
    for (const t of timePoints) {
        const [h, m] = t.split(':').map(Number);
        const total = h * 60 + m;
        if (seen[total]) return 0;
        seen[total] = true;
    }
    let prev = -1, first = -1, minDiff = 1440;
    for (let i = 0; i < 1440; i++) {
        if (seen[i]) {
            if (prev !== -1) {
                minDiff = Math.min(minDiff, i - prev);
            } else {
                first = i;
            }
            prev = i;
        }
    }
    minDiff = Math.min(minDiff, 1440 - prev + first);
    return minDiff;
}

// Example usage
console.log(findMinDifference(["23:59", "00:00"])); // Output: 1

Line Notes

const seen = new Array(1440).fill(false)Create fixed-size boolean array for times

if (seen[total]) return 0Return 0 if duplicate time found

for (let i = 0; i < 1440; i++)Scan all possible times in order

if (seen[i])Check if time is marked

minDiff = Math.min(minDiff, i - prev)Update min difference between consecutive marked times

minDiff = Math.min(minDiff, 1440 - prev + first)Check circular difference between last and first marked times

return minDiffReturn the smallest difference

⏱

Complexity

TimeO(n)

SpaceO(1) (fixed size 1440 array)

Marking times is O(n), scanning fixed 1440 slots is O(1) constant time. Space is fixed at 1440 booleans regardless of input size.

💡 This approach is fastest for large inputs because it avoids sorting and uses constant space relative to input size.

Interview Verdict: Accepted / Most optimal for large inputs

This approach leverages problem constraints for optimal performance and is a great example of using domain knowledge.

📊

All Approaches - One-Glance Tradeoffs

💡 Use the sorting approach in 95% of interviews; bucket sort is optimal but less common unless constraints are known.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n^2)	O(n)	No	N/A	Mention only - never code
2. Sorting + Single Pass	O(n log n)	O(n)	No	N/A	Code this approach in most interviews
3. Bucket Sort (Boolean Array)	O(n)	O(1) fixed 1440 size	No	N/A	Mention as optimization if time range is fixed

💼

Interview Strategy

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

How to Present

Step 1: Clarify the problem and constraints, especially the circular nature of time.Step 2: Present the brute force approach to show understanding.Step 3: Optimize by sorting and checking adjacent pairs.Step 4: Discuss the bucket sort approach leveraging fixed time range.Step 5: Code the chosen approach and test with edge cases.

Time Allocation

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

What the Interviewer Tests

Interviewer tests problem understanding, ability to optimize from brute force, handling of circular time, and clean coding.

Common Follow-ups

• What if times are not guaranteed unique? → Return 0 immediately on duplicates.
• Can you handle times in 12-hour format? → Convert to 24-hour format first.

💡 Follow-ups test robustness and ability to adapt solution to variations.

🔍

Pattern Recognition

When to Use

1) Problem involves times or circular values; 2) Need minimum difference; 3) Input can be sorted; 4) Circular wrap-around matters.

Signature Phrases

minimum difference between times24-hour clockcircular time differencewrap around midnight

NOT This Pattern When

Problems that require interval merging or scheduling without circular wrap are different patterns.

Similar Problems

Find K Closest Elements - also uses sorting and difference calculationMeeting Rooms II - involves sorting intervals and checking overlaps

Practice

1. Consider the following Python code for finding the maximum gap in a list of integers. What is the value of max_gap after the second iteration of the for-loop when the input is [3, 6, 9, 1]?

from typing import List

def maximumGap(nums: List[int]) -> int:
    if len(nums) < 2:
        return 0
    min_num, max_num = min(nums), max(nums)
    if min_num == max_num:
        return 0
    nums.sort()
    max_gap = 0
    for i in range(1, len(nums)):
        max_gap = max(max_gap, nums[i] - nums[i-1])
    return max_gap

print(maximumGap([3,6,9,1]))  # Output: ?

easy

A. 3

B. 5

C. 6

D. 8

Solution

1. Step 1: Sort the input array

   Input: [3,6,9,1] -> Sorted: [1,3,6,9]

2. Step 2: Trace max_gap updates in the loop

   Iteration 1 (i=1): max_gap = max(0, 3-1) = 2 Iteration 2 (i=2): max_gap = max(2, 6-3) = 3

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   max_gap after second iteration is 3 [OK]

Hint: Sort first, then scan adjacent differences [OK]

Common Mistakes:

• Off-by-one errors in loop
• Using unsorted array differences
• Confusing iteration indices

2. Given the following code snippet implementing the optimal wiggle sort, what is the content of the array nums after the while loop completes when the input is [1, 3, 2]?

easy

A. [2, 3, 1]

B. [1, 3, 2]

C. [3, 1, 2]

D. [1, 2, 3]

Solution

1. Step 1: Sort and find median

   Sorted nums = [1, 2, 3], median = nums[(3-1)//2] = nums[1] = 2.

2. Step 2: Apply virtual indexing and partition

   Virtual indices for i=0,1,2 are (1+2*0)%3=1, (1+2*1)%3=0, (1+2*2)%3=2. - i=0: nums[1]=2 equals median -> i=1 - i=1: nums[0]=1 less than median -> swap with nums[virtual_index(right=2)]=nums[2]=3, right=1 - After swap: nums=[3,2,1], i=1, right=1 - i=1: nums[0]=3 greater than median -> swap with nums[virtual_index(left=0)]=nums[1]=2, left=1, i=2 - Final nums=[2,3,1]

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Final array satisfies wiggle property: 2 < 3 > 1 [OK]

Hint: Trace virtual indices carefully to get final array [OK]

Common Mistakes:

• Confusing virtual index mapping
• Off-by-one in median calculation
• Not updating pointers correctly

3. Consider the following buggy code snippet for finding missing ranges. Which line contains the subtle bug that causes missing ranges at the start of the interval to be ignored?

medium

A. Line with condition 'if pointer <= curr:' should be 'if pointer < curr:'

B. Line updating pointer to 'curr + 1' should be 'curr' instead

C. Line checking 'if idx == len(nums):' should check 'if idx > len(nums):'

D. Line appending missing range should format single numbers as 'start->end' always

Solution

1. Step 1: Identify condition for missing range detection

   The condition 'if pointer <= curr:' incorrectly includes the case pointer == curr, causing no gap detection before first element if pointer equals first number.

2. Step 2: Correct condition to 'if pointer < curr:'

   This ensures missing ranges are detected only when pointer is strictly less than current number, capturing missing numbers before first element.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Changing to '<' fixes missing start ranges [OK]

Hint: Check strict inequality when detecting gaps [OK]

Common Mistakes:

• Using <= instead of <
• Incorrect pointer update
• Wrong formatting of single numbers

4. What is the time complexity of the optimal counting sort based solution for the relative sort array problem, where n = length of arr1 and k = maximum value in arr1?

medium

A. O(n + k) because frequency counting and outputting are linear in n and k

B. O(n log n) due to sorting leftover elements

C. O(n * k) because nested loops iterate over arr1 and frequency array

D. O(k log k) due to sorting the frequency array keys

Solution

1. Step 1: Analyze frequency counting

   Counting frequencies over arr1 is O(n), where n is arr1 length.

2. Step 2: Analyze output construction

   Outputting elements by iterating frequency array of size k is O(k). No sorting is done on leftover elements.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Counting sort runs in linear time relative to n and k [OK]

Hint: Counting sort is linear in input size and max value [OK]

Common Mistakes:

• Assuming leftover elements require sorting (O(n log n))
• Confusing nested loops causing O(n*k)
• Thinking frequency array keys need sorting

5. The following code attempts to implement the Dutch National Flag algorithm but contains a subtle bug:

def sortColors(nums):
    low, mid, high = 0, 0, len(nums) - 1
    while mid <= high:
        if nums[mid] == 0:
            nums[low], nums[mid] = nums[mid], nums[low]
            low += 1
            # mid += 1  # Missing increment here
        elif nums[mid] == 1:
            mid += 1
        else:  # nums[mid] == 2
            nums[mid], nums[high] = nums[high], nums[mid]
            high -= 1

Which line contains the bug that causes incorrect behavior or infinite loops?

medium

A. Line where mid is incremented after swapping 0 (missing here)

B. Line where nums[mid] and nums[high] are swapped and high is decremented

C. Line where mid is incremented when nums[mid] == 1

D. Line where nums[low], nums[mid] are swapped and low is incremented

Solution

1. Step 1: Identify missing pointer update

   After swapping 0 to the front, mid must increment to avoid reprocessing the same element.

2. Step 2: Consequence of missing mid increment

   Without mid increment, mid stays pointing to swapped 0, causing infinite loop or incorrect order.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing mid increment after swapping 0 causes infinite loop [OK]

Hint: Always increment mid after swapping 0 to front [OK]

Common Mistakes:

• Forgetting to increment mid after swapping 0
• Incrementing mid after swapping 2 (wrong)
• Confusing roles of low and mid pointers