Minimum Time Difference: Circular Sort Trick

LeetCode #539 Minimum Time Difference is a medium problem that looks deceptively simple. You are given a list of times in "HH:MM" format, and you need to find the minimum difference in minutes between any two times. The trick is that time is circular: 23:59 and 00:00 are only 1 minute apart, not 1439 minutes apart.

The problem

Given a list of 24-hour clock time points in "HH:MM" format, return the minimum minutes difference between any two time points in the list.

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

Input:  ["00:00", "23:59", "12:30", "05:15"]
Output: 1

The first example is the key insight. If you just compute 23*60+59 - 0 = 1439, you get the wrong answer. The times wrap around midnight, so the actual difference is just 1 minute.

The brute force

The naive approach: convert all times to minutes, then compare every pair.

def find_min_difference_brute(time_points):
    minutes = []
    for t in time_points:
        h, m = map(int, t.split(":"))
        minutes.append(h * 60 + m)

    min_diff = float("inf")
    n = len(minutes)
    for i in range(n):
        for j in range(i + 1, n):
            diff = abs(minutes[i] - minutes[j])
            diff = min(diff, 1440 - diff)
            min_diff = min(min_diff, diff)

    return min_diff

This works, but it checks every pair. That is O(n^2) comparisons. For a large list of times, we can do better.

The key observation: if we sort the times, the minimum difference must occur between adjacent elements (or between the last and first, wrapping around). Non-adjacent elements in a sorted array are always farther apart than at least one adjacent pair.

The approach

The algorithm has three parts:

1. Convert each "HH:MM" string to total minutes since midnight (an integer in [0, 1439]).
2. Sort the array of minutes.
3. Scan adjacent pairs and also check the circular wrap-around between the last and first element.

The wrap-around distance is 1440 - sorted[-1] + sorted[0]. This accounts for the gap that crosses midnight.

The code

def find_min_difference(time_points):
    minutes = sorted(
        int(t[:2]) * 60 + int(t[3:]) for t in time_points
    )

    min_diff = 1440 - minutes[-1] + minutes[0]

    for i in range(1, len(minutes)):
        min_diff = min(min_diff, minutes[i] - minutes[i - 1])

    return min_diff

That is the entire solution. Let's walk through why each piece works:

1. We parse and sort in one step. int(t[:2]) grabs the hours, int(t[3:]) grabs the minutes.
2. We initialize min_diff with the wrap-around distance. This handles the circular case without needing a special check at the end.
3. We loop through adjacent pairs. Since the array is sorted, minutes[i] - minutes[i-1] is always non-negative.
4. We return the smallest difference found.

Step-by-step walkthrough

Let's trace through timePoints = ["23:59", "00:00", "12:30", "05:15"]:

"23:59" → 23×60+59 = 1439
"00:00" → 0×60+0 = 0
"12:30" → 12×60+30 = 750
"05:15" → 5×60+15 = 315

[1439, 0, 750, 315] → sorted → [0, 315, 750, 1439]

315 - 0 = 315 minutes
750 - 315 = 435 minutes
1439 - 750 = 689 minutes

1440 - 1439 + 0 = 1 minute
(from 23:59 to 00:00 crossing midnight)

min(315, 435, 689, 1) = 1

Notice how sorting makes the problem linear. Without sorting, you would need to compare every pair. With sorting, the closest pair must be adjacent (or the wrap-around pair), so you only check n differences.

Complexity analysis

Time: O(n log n). Sorting dominates. The conversion is O(n) and the scan is O(n), but sorting costs O(n log n).

Space: O(n). We store the array of minutes. Some implementations sort in place, but we still need O(n) for the converted values.

The building blocks

This problem is built on two reusable bricks:

Circular distance formula

When values wrap around a fixed range, the distance between two values a and b in a range [0, M) is:

diff = min(abs(a - b), M - abs(a - b))

Or equivalently, after sorting, the wrap-around gap is M - last + first. You will see this pattern in circular array problems, clock arithmetic, and modular distance questions.

Sort to reduce pairwise comparisons

Whenever a problem asks for the minimum (or maximum) difference between any pair of elements, sorting is usually the first move. After sorting, the minimum difference must be between adjacent elements. This reduces the search from O(n^2) pairs to O(n) adjacent checks.

The same idea appears in problems like finding the closest pair of points (1D case), minimum absolute difference, and contains duplicate variants.

Edge cases

Before submitting, verify your solution handles:

• Duplicate times like ["01:00", "01:00"]: the answer is 0. After sorting, adjacent duplicates produce a difference of 0 immediately.
• Only two times like ["00:00", "12:00"]: the answer is 720 (or min(720, 720) since both directions are equal).
• Times at exactly midnight and noon like ["00:00", "12:00", "23:59"]: the wrap-around from 23:59 to 00:00 is 1, which beats the 720-minute gap.
• Maximum possible list size: since there are only 1440 distinct minute values, any list with more than 1440 times must contain a duplicate. You can short-circuit and return 0 in that case.

From understanding to recall

You have seen how sorting plus a wrap-around check solves this problem cleanly. The algorithm is short, but under interview pressure, people forget the wrap-around formula or get confused about whether to initialize min_diff before or after the loop.

The details that trip people up: initializing with the circular gap, using 1440 - last + first instead of abs(last - first), and remembering that sorting makes adjacent comparison sufficient. These are small things, but they matter when you are writing code on a whiteboard.

Spaced repetition locks in the pattern. You practice converting times, writing the sort, and computing the wrap-around at increasing intervals. After a few reps, the entire solution is automatic. You see "minimum difference" and "circular" and your hands write the code before your brain finishes reading the problem.

Related posts

• Sort Colors - Another sorting problem where the key insight is choosing the right sorting strategy for the constraint
• Merge Intervals - Sorting intervals to reduce pairwise comparisons to a linear scan, the same fundamental trick
• Group Anagrams - Uses sorting as a normalization step, showing how sorting enables efficient grouping

CodeBricks breaks the circular-sort pattern into its reusable pieces and drills them individually. You practice the conversion, the sort, and the wrap-around check as separate bricks, then combine them under timed conditions so the full solution becomes automatic.