Domain 2MediumCORE

Minimum Time Difference

We are given a list of times in 'HH:MM' format representing points on a 24-hour clock. The goal is to find the minimum difference in minutes between any two time-points within that list.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#String

539. Minimum Time Difference

Model: qwen3.5:9b
Topics: String
FAANG asked: 0
Acceptance rate: 52.4%


Problem Breakdown

We are given a list of times in “HH:MM” format representing points on a 24-hour clock. The goal is to find the minimum difference in minutes between any two time-points within that list.

Key inputs and outputs include:

  • Input: A list of strings (timePoints), where each string follows strict “HH:MM” formatting (00-23 for hours, 00-59 for minutes). The length is guaranteed to be at least 2 based on constraints.
  • Output: An integer representing the smallest positive difference in minutes between any pair of times.

Implicit edge cases and tricky aspects:

  1. Circular Nature: Time wraps around midnight (e.g., “00:00” follows “23:59”). A naive linear subtraction fails here without special handling for the boundary crossing.
  2. Duplicates: If two time-points are identical, the difference is 0. This must be captured correctly.
  3. Scale: With up to 2×1042 \times 10^4 elements, an O(N2)O(N^2) solution will exceed typical execution limits (Time Limit Exceeded). We need a more efficient approach than comparing every pair.

Intuition

A brute-force strategy would involve iterating through all pairs of time-points and calculating the absolute difference for each. This results in O(N2)O(N^2) complexity, which is too slow given NN can be up to 20,000 (4×1084 \times 10^8 operations).

To optimize, we should observe that if times are ordered linearly (sorted), the minimum difference between any two elements must occur between adjacent neighbors in that sorted sequence. If you have three points A<B<CA < B < C, then diff(A,C)=diff(A,B)+diff(B,C)\text{diff}(A,C) = \text{diff}(A,B) + \text{diff}(B,C), so checking non-adjacent pairs is redundant for finding the minimum gap within a linear segment.

However, because time is circular (24-hour cycle), we must also consider the “wrap-around” distance between the last element and the first element in our sorted list. The key insight is:

  1. Convert all times to minutes from midnight (0-1439) for easy arithmetic.
  2. Sort these integers.
  3. Iterate through adjacent pairs to find local minimums.
  4. Explicitly check the circular gap between last and first.

Approach

The algorithm proceeds in three main steps:

  1. Normalization: Parse each “HH:MM” string into an integer representing minutes from midnight (H×60+MH \times 60 + M). This allows direct numerical comparison.
  2. Sorting & Linear Scan: Sort the list of minute values. Iterate through the sorted array, calculating current - previous for every adjacent pair and updating a running minimum (min_diff). Initialize min_diff to infinity or handle duplicates (where diff is 0).
  3. Circular Check: Calculate the difference between the first element plus one full day (14401440 minutes) and the last element: (first + 24*60) - last. Compare this against our running minimum.

This approach ensures we cover all adjacent gaps in a linear timeline as well as the wrap-around gap, guaranteeing correctness with O(Nlog⁡N)O(N \log N) complexity due to sorting.

Complexity Analysis

  • Time Complexity: O(Nlog⁡N)O(N \log N). The dominant operation is sorting the list of time integers (NN elements). Converting strings takes O(1)O(1) per element (fixed format), and iterating through the sorted array takes O(N)O(N). Total: O(Nlog⁡N+N)=O(Nlog⁡N)O(N \log N + N) = O(N \log N).
  • Space Complexity: O(N)O(N). We store an integer list of size NN for sorting. If we modify input in-place (not recommended here), it could be O(1)O(1) auxiliary, but standard Python sort creates a new structure or uses internal buffers proportional to NN.

Solution

def findMinDifference(timePoints):
    # Convert "HH:MM" strings to minutes from midnight for easier comparison.
    times = []
    for t in timePoints:
        h, m = map(int, t.split(':'))
        times.append(h * 60 + m)

    # Sort the minute values to easily find adjacent differences.
    times.sort()
    
    min_diff = float('inf')
    
    # Check linear gaps between adjacent elements in sorted list.
    for i in range(len(times) - 1):
        diff = times[i+1] - times[i]
        if diff < min_diff:
            min_diff = diff
            
    # Handle the circular wrap-around case (last element to first).
    # Add 24*60 minutes to the first element to simulate next day.
    circular_gap = (times[0] + 1440) - times[-1]
    
    if circular_gap < min_diff:
        min_diff = circular_gap
        
    return min_diff

Edge Cases Handled

  • Duplicate Times: If the list contains ["08:00", "08:00"], sorting places them adjacent. The difference is 0, which correctly updates min_diff.
  • Midnight Wrap-Around: For inputs like ["23:59", "00:00"], the linear scan sees a large gap (1439 minutes). The explicit circular check calculates (0 + 1440) - 1439 = 1 minute, correctly identifying this as the minimum.
  • Single Element: While constraints specify N≥2N \geq 2, if only one time existed, min_diff would remain infinity (or require specific handling). The current logic assumes valid input per constraints but handles duplicates naturally via sorting.