Minimum Time Difference (Sort Circular Times)

📋

Problem

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.

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)

Edge cases: 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 0Times spread evenly across the day → minimum difference is the smallest gap between adjacent sorted times

</>

IDE

def findMinDifference(timePoints: list[str]) -> int:public int findMinDifference(List<String> timePoints)int findMinDifference(vector<string> &timePoints)function findMinDifference(timePoints)

def findMinDifference(timePoints):
    # Write your solution here
    pass

class Solution {
    public int findMinDifference(List<String> timePoints) {
        // Write your solution here
        return 0;
    }
}

#include <vector>
using namespace std;

int findMinDifference(vector<string> &timePoints) {
    // Write your solution here
    return 0;
}

function findMinDifference(timePoints) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: Incorrect minimum difference ignoring circular wrap-aroundDid not check difference between last and first times after sorting✅ After sorting, compute min difference including min(diff between last and first + 1440 - diff)

Wrong: Minimum difference greater than 0 when duplicates existDid not detect duplicates in sorted times✅ Return 0 immediately if any two adjacent times are equal after sorting

Wrong: Fails or crashes on single element inputNo handling for input length 1✅ Return 0 if input length is 1

Wrong: Timeout on large inputsUsing brute force O(n^2) approach✅ Use sorting + single pass O(n log n) or bucket sort O(n) approach

✓

Test Cases

Focus on handling edge cases like single element and duplicates.

Watch out for common pitfalls like missing duplicates or wrap-around checks.

Optimize your solution to avoid timeouts on large inputs.

t1_01basic

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

Expected1

⏱ Performance - must finish in 2000ms

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

💡 Sort the times to compare adjacent pairs easily.

💡 Convert times to minutes and check differences between adjacent sorted times and circular wrap-around.

💡 Calculate differences as min(current - previous, 1440 - (current - previous)) to handle circular day.

Why it failed: Incorrect output means you likely missed the circular difference calculation between last and first time points. Fix by checking difference between last and first after sorting.

✓ Correctly handles circular time difference and sorting.

t1_02basic

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

Expected59

⏱ Performance - must finish in 2000ms

Sorted times are 01:01 (61), 02:01 (121), 03:00 (180). Minimum difference is between 02:01 and 03:00 = 59 minutes.

💡 Convert all times to minutes and sort them.

💡 Check differences between all adjacent pairs after sorting.

💡 Minimum difference is the smallest gap found, no wrap-around needed here.

Why it failed: If output is wrong, you probably did not sort times or did not convert times to minutes correctly. Fix by parsing and sorting before difference calculation.

✓ Correctly computes minimum adjacent difference after sorting.

t2_01edge

Input["00:00"]

Expected0

⏱ Performance - must finish in 2000ms

Only one time point means minimum difference is 0 by definition.

💡 Consider what happens if there is only one time point.

💡 Minimum difference should be 0 since no pairs exist.

💡 Return 0 immediately if input length is 1.

Why it failed: Failing this test means your code does not handle single-element input correctly. Fix by returning 0 if length is 1.

✓ Handles single time point input correctly.

t2_02edge

Input["12:34","12:34","12:34"]

Expected0

⏱ Performance - must finish in 2000ms

All time points are identical, so minimum difference is 0.

💡 Check for duplicates after sorting.

💡 If any two adjacent times are equal, minimum difference is 0.

💡 Return 0 immediately when duplicates found.

Why it failed: Failing means you did not check for duplicates properly. Fix by returning 0 if adjacent times are equal after sorting.

✓ Correctly detects duplicates and returns 0.

t2_03edge

Input["00:00","06:00","12:00","18:00"]

Expected360

⏱ Performance - must finish in 2000ms

Times are evenly spaced every 6 hours (360 minutes). Minimum difference is 360.

💡 Sort times and convert to minutes.

💡 Check differences between adjacent times and wrap-around.

💡 Minimum difference is the smallest gap found, here 360 minutes.

Why it failed: Failing means you did not correctly compute differences or missed wrap-around. Fix by checking circular difference between last and first times.

✓ Correctly computes minimum difference for evenly spaced times.

t3_01corner

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

Expected1

⏱ Performance - must finish in 2000ms

Minimum difference is between 00:01 and 00:02 (1 minute), not between 23:59 and 00:01 (2 minutes).

💡 Sorting times is crucial to find minimum adjacent difference.

💡 Check all adjacent pairs after sorting, not just first and last.

💡 Minimum difference is min of all adjacent pairs including wrap-around.

Why it failed: Failing means you only checked circular difference between first and last times, ignoring other adjacent pairs. Fix by checking all adjacent pairs after sorting.

✓ Correctly finds minimum difference among all adjacent pairs.

t3_02corner

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

Expected0

⏱ Performance - must finish in 2000ms

Duplicates cause minimum difference 0 even if other times are far apart.

💡 Check for duplicates after sorting.

💡 Duplicates guarantee minimum difference 0.

💡 Return 0 immediately if duplicates found.

Why it failed: Failing means you did not detect duplicates properly. Fix by returning 0 if any adjacent times are equal after sorting.

✓ Correctly detects duplicates and returns 0.

t3_03corner

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

Expected1

⏱ Performance - must finish in 2000ms

Minimum difference is between 23:59 and 00:00 (1 minute), not between 00:00 and 12:00 (720 minutes).

💡 Remember to check circular difference between last and first times.

💡 Convert times to minutes and consider 1440 - difference for wrap-around.

💡 Minimum difference is min of all adjacent pairs including wrap-around.

Why it failed: Failing means you missed circular wrap-around difference. Fix by checking difference between last and first times after sorting.

✓ Correctly handles circular difference at day boundary.

t4_01performance

Input{"_description":"n=100000 at constraint boundary - executor generates this input"}

Expectednull

⏱ Performance - must finish in 2000ms

Input size n=100000 requires O(n log n) or better solution to run within 2 seconds.

💡 Brute force O(n^2) will time out for large n.

💡 Use sorting and single pass to find minimum difference in O(n log n).

💡 Consider bucket sort or boolean array for O(n) time.

Why it failed: TLE indicates your solution is O(n^2). Fix by implementing sorting + single pass or bucket sort approach.

✓ Solution runs efficiently in O(n log n) or better.

Practice

1. Given the following Python code for finding missing ranges, what is the final output when calling find_missing_ranges([0, 1, 3, 50, 75], 0, 99)?

easy

A. ['2', '4->49', '51->74', '76->99']

B. ['2', '4->49', '51->74', '76->98', '99']

C. ['2', '4->49', '51->74', '76->99']

D. ['2', '4->49', '51->74', '75->99']

Solution

1. Step 1: Trace pointer and bisect calls

   Start pointer=0, bisect finds 0 at idx=0, pointer updated to 1+1=2. At pointer=2, bisect finds idx=2 with curr=3, missing range 2 (single number) added. Pointer updated to 3+1=4. At pointer=4, bisect finds idx=3 with curr=50, missing range 4->49 added. Pointer updated to 50+1=51. At pointer=51, bisect finds idx=4 with curr=75, missing range 51->74 added. Pointer updated to 75+1=76. At pointer=76, bisect idx=5 (end), missing range 76->99 added. Loop ends.

2. Step 2: Confirm final missing ranges list

   Missing ranges: ['2', '4->49', '51->74', '76->99']

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   All gaps between nums and bounds correctly identified [OK]

Hint: Check pointer updates and bisect indices carefully [OK]

Common Mistakes:

• Off-by-one errors in range ends
• Including last number incorrectly
• Misformatting single number ranges

2. The following code attempts to find the maximum gap between successive elements in a list using the bucket sort approach. Identify the line containing the subtle bug that can cause incorrect results for some inputs.

def maximumGap(nums):
    if len(nums) < 2:
        return 0
    min_num, max_num = min(nums), max(nums)
    if min_num == max_num:
        return 0
    bucket_size = max(1, (max_num - min_num) // (len(nums) - 1))
    bucket_count = (max_num - min_num) // bucket_size
    buckets = [[None, None] for _ in range(bucket_count + 1)]
    for num in nums:
        idx = (num - min_num) // bucket_size
        if buckets[idx][0] is None or num < buckets[idx][0]:
            buckets[idx][0] = num
        if buckets[idx][1] is None or num > buckets[idx][1]:
            buckets[idx][1] = num
    max_gap = 0
    prev_max = None
    for b in buckets:
        if b[0] is None:
            continue
        if prev_max is not None:
            max_gap = max(max_gap, b[0] - prev_max)
        prev_max = b[1]
    return max_gap

medium

A. Line assigning idx: idx = (num - min_num) // bucket_size

B. Line calculating bucket_size: bucket_size = max(1, (max_num - min_num) // (len(nums) - 1))

C. Line updating max_gap inside the for-loop scanning buckets

D. Line calculating bucket_count: bucket_count = (max_num - min_num) // bucket_size

Solution

1. Step 1: Understand bucket count calculation

   Bucket count should be ceil((max_num - min_num) / bucket_size) to cover full range.

2. Step 2: Identify bug in bucket_count line

   Using integer division truncates, possibly missing the last bucket, causing some elements to be out of range or buckets to overlap.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Correct bucket count must cover entire range [OK]

Hint: Bucket count must cover full range, use ceiling not floor [OK]

Common Mistakes:

• Using floor division for bucket count
• Incorrect bucket size causing overlaps
• Assuming max gap inside buckets

3. The following code attempts to sort a matrix diagonally using min-heaps keyed by (row - col). Identify the line containing the subtle bug that causes incorrect sorting or corrupted output.

from typing import List
import collections
import heapq

def diagonalSort(mat: List[List[int]]) -> List[List[int]]:
    m, n = len(mat), len(mat[0])
    diagonals = collections.defaultdict(list)
    for i in range(m):
        for j in range(n):
            heapq.heappush(diagonals[i + j], mat[i][j])  # Line X
    for i in range(m):
        for j in range(n):
            mat[i][j] = heapq.heappop(diagonals[i - j])  # Line Y
    return mat

medium

A. Line X: Using i + j as diagonal key instead of i - j.

B. Line Y: Popping from diagonals keyed by i - j instead of i + j.

C. Line X: Using heapq.heappush instead of sorting the diagonal list first.

D. Line Y: Assigning popped element directly without checking if heap is empty.

Solution

1. Step 1: Check diagonal key consistency

   The diagonal key must be consistent for both pushing and popping. Here, push uses i + j, pop uses i - j, causing mismatch.

2. Step 2: Identify impact of key mismatch

   Elements pushed into one diagonal heap are popped from a different key, leading to empty heaps or incorrect elements assigned.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Diagonal keys must match exactly for correct sorting [OK]

Hint: Diagonal key must be consistent for push and pop [OK]

Common Mistakes:

• Mixing i + j and i - j keys
• Forgetting to check heap emptiness
• Using reverse sorting but popping incorrectly

4. Suppose the problem is modified so that elements can be reused unlimited times to form an infinitely long array with no two adjacent elements equal. Which modification to the heap-based algorithm correctly handles this variant?

hard

A. Remove the max frequency check and keep pushing elements back with updated counts indefinitely.

B. Use a queue instead of a heap to cycle through elements ensuring no two adjacent are equal.

C. Use a max heap but reset counts to original frequencies after each full pass through the heap.

D. Modify the algorithm to never decrement counts and always push elements back to allow infinite reuse.

Solution

1. Step 1: Understand infinite reuse implication

   Since elements can be reused unlimited times, counts do not decrease; the algorithm must allow repeated placement without decrementing counts.

2. Step 2: Modify heap usage accordingly

   Never decrement counts and always push elements back to heap to maintain availability, ensuring no two adjacent elements are equal.

3. Step 3: Evaluate other options

   Removing max frequency check or resetting counts breaks correctness or efficiency; queue does not prioritize frequency.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Maintaining counts without decrement allows infinite reuse without adjacency violation [OK]

Hint: Infinite reuse means counts stay constant [OK]

Common Mistakes:

• Removing checks without adjusting counts
• Resetting counts causing incorrect order

5. Suppose the input list nums can contain duplicate numbers and is not guaranteed to be sorted. Which modification to the optimal binary search approach is necessary to correctly find missing ranges?

hard

A. Modify binary search to skip duplicates by checking neighbors

B. Use a hash set to track presence and scan the entire range linearly

C. Apply binary search directly without changes since duplicates don't affect bisect

D. Sort the list and remove duplicates before applying binary search

Solution

1. Step 1: Understand binary search prerequisites

   Binary search requires a sorted list with unique elements to correctly locate insertion points and detect gaps.

2. Step 2: Preprocess input by sorting and removing duplicates

   Sorting ensures order; removing duplicates prevents incorrect gap detection caused by repeated numbers.

3. Step 3: Apply binary search on cleaned list

   After preprocessing, the existing binary search approach works correctly.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Sorting and deduplication are essential preprocessing steps [OK]

Hint: Binary search needs sorted unique data [OK]

Common Mistakes:

• Ignoring duplicates
• Assuming bisect handles duplicates correctly
• Switching to linear scan unnecessarily