LeetCode 539 - Minimum Time Difference

The problem gives a list of time points in 24-hour clock format, where every time is represented as a string in the form "HH:MM". Your task is to determine the smallest difference in minutes between any two time points in the list.

leetcodemediumarraymathstringsorting

LeetCode Problem 539

Difficulty: 🟡 Medium
Topics: Array, Math, String, Sorting

Solution

Problem Understanding

The problem gives a list of time points in 24-hour clock format, where every time is represented as a string in the form "HH:MM". Your task is to determine the smallest difference in minutes between any two time points in the list.

A key detail is that time is cyclic, meaning the clock wraps around at midnight. For example, the difference between "23:59" and "00:00" is not 1439 minutes, it is 1 minute because the clock resets after midnight. This wraparound behavior is one of the most important aspects of the problem.

The input consists of an array of strings, where each string represents a valid time. The output is a single integer, representing the minimum number of minutes separating any two time points.

The constraints are important:

  • 2 <= timePoints.length <= 2 * 10^4
  • Each time string is guaranteed to be in "HH:MM" format.

The number of inputs can be as large as 20,000, which means a naive comparison of every pair becomes expensive. Since there are only 1440 unique minutes in a day (24 * 60), this observation can help us optimize.

There are several important edge cases:

  1. Duplicate time points

If the same time appears more than once, the answer is immediately 0, since the difference between identical times is zero. 2. Midnight wraparound

A naive sorted comparison might miss cases like "23:59" and "00:00", where the smallest difference crosses midnight. 3. Minimum input size

When only two time points exist, we still must correctly account for circular time. 4. Large input size with repeated values

Since there are only 1440 distinct times but up to 20,000 entries, duplicates are highly likely. By the pigeonhole principle, if len(timePoints) > 1440, the answer must be 0.

Approaches

Brute Force Approach

The simplest way to solve this problem is to compare every pair of time points.

First, convert every "HH:MM" string into total minutes from midnight. For example:

  • "01:30" → 90
  • "23:59" → 1439

Then, for every pair (i, j), compute the absolute difference in minutes. Since the clock wraps around, we must also consider the circular difference:

$$\text{difference} = \min(|a - b|, 1440 - |a - b|)$$

We keep track of the smallest difference encountered.

This approach is correct because it explicitly checks every possible pair, guaranteeing that the minimum difference is found. However, it is too slow for large inputs because comparing every pair takes quadratic time.

With up to 20,000 time points:

$$O(n^2) = 400,000,000$$

operations in the worst case, which is impractical.

Optimal Approach

The key observation is that after converting times to minutes, sorting makes the problem much easier.

If numbers are sorted, the smallest difference between any two values must occur between adjacent elements. This is a fundamental property of sorted sequences.

For example:

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

Convert to minutes:

[1439, 0, 750]

Sort:

[0, 750, 1439]

Now we only compare neighboring values:

  • 750 - 0 = 750
  • 1439 - 750 = 689

But we still need to handle circular wraparound:

(1440 - 1439) + 0 = 1

So the minimum is 1.

This reduces the work dramatically because sorting costs O(n log n) and the adjacent scan costs O(n).

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(n) Convert times and compare every pair
Optimal O(n log n) O(n) Sort minutes and compare adjacent times plus wraparound

Algorithm Walkthrough

Optimal Algorithm

  1. Handle the duplicate shortcut

Since there are only 1440 unique minute values in a day, if the number of time points exceeds 1440, duplicates must exist. In that case, return 0 immediately. 2. Convert all time strings into minutes

For every time string:

  • Split into hours and minutes
  • Convert to integers
  • Compute:
total_minutes = hours * 60 + minutes

This gives a numeric representation that is easier to sort and compare. 3. Sort the minutes array

Sorting places all time points in chronological order.

Once sorted, the minimum difference between any two non-wraparound times must exist between adjacent elements. 4. Compare adjacent elements

Iterate through the sorted array and compute:

difference = current - previous

Track the minimum difference seen so far. 5. Handle the circular midnight case

Compare the first and last times:

wrap_difference = 1440 - last + first

This captures cases where the shortest gap crosses midnight. 6. Return the smallest difference

After checking adjacent pairs and the wraparound pair, return the minimum value found.

Why it works

After sorting, every time point's nearest candidate for minimum difference must be one of its neighbors. If a smaller difference existed between non-adjacent elements, then some adjacent pair between them would necessarily be even smaller, which is a contradiction.

The only missing comparison is the circular connection between the last and first elements, because clocks wrap around at midnight. Including this final comparison guarantees that every relevant pair is considered.

Python Solution

from typing import List

class Solution:
    def findMinDifference(self, timePoints: List[str]) -> int:
        # Pigeonhole principle: more than 1440 times means duplicates
        if len(timePoints) > 1440:
            return 0

        minutes = []

        for time_point in timePoints:
            hours, mins = map(int, time_point.split(":"))
            total_minutes = hours * 60 + mins
            minutes.append(total_minutes)

        minutes.sort()

        minimum_difference = float("inf")

        for index in range(1, len(minutes)):
            difference = minutes[index] - minutes[index - 1]
            minimum_difference = min(minimum_difference, difference)

        wraparound_difference = (
            1440 - minutes[-1] + minutes[0]
        )

        minimum_difference = min(
            minimum_difference,
            wraparound_difference
        )

        return minimum_difference

The implementation begins with an optimization based on the pigeonhole principle. Since there are only 1440 unique minute values in a day, any input larger than this must contain duplicates, which guarantees a minimum difference of 0.

Next, each time string is converted into total minutes from midnight. This simplifies comparisons because working with integers is easier than manipulating time strings.

The list of minutes is then sorted. After sorting, we scan adjacent elements and compute their differences, updating the running minimum whenever a smaller gap is found.

Finally, the implementation explicitly checks the circular difference between the last and first time values to account for midnight wraparound. The smallest computed value is returned.

Go Solution

package main

import (
	"sort"
	"strconv"
	"strings"
)

func findMinDifference(timePoints []string) int {
	// Pigeonhole principle
	if len(timePoints) > 1440 {
		return 0
	}

	minutes := make([]int, 0, len(timePoints))

	for _, timePoint := range timePoints {
		parts := strings.Split(timePoint, ":")

		hours, _ := strconv.Atoi(parts[0])
		mins, _ := strconv.Atoi(parts[1])

		totalMinutes := hours*60 + mins
		minutes = append(minutes, totalMinutes)
	}

	sort.Ints(minutes)

	minDifference := 1 << 30

	for i := 1; i < len(minutes); i++ {
		difference := minutes[i] - minutes[i-1]

		if difference < minDifference {
			minDifference = difference
		}
	}

	wraparoundDifference := 1440 - minutes[len(minutes)-1] + minutes[0]

	if wraparoundDifference < minDifference {
		minDifference = wraparoundDifference
	}

	return minDifference
}

The Go implementation follows the same logic as the Python version. Time strings are split using strings.Split, and numeric conversion is handled with strconv.Atoi.

Unlike Python's float("inf"), Go uses a very large integer (1 << 30) as the initial minimum value. Since the maximum possible difference is only 1440, this is safely larger than any valid answer.

Go slices are dynamically sized, so we initialize the slice with a capacity equal to the input length to reduce reallocations.

Worked Examples

Example 1

Input

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

Step 1: Convert to minutes

Time Minutes
23:59 1439
00:00 0

Array:

[1439, 0]

Step 2: Sort

[0, 1439]

Step 3: Compare adjacent times

Pair Difference
1439 - 0 1439

Current minimum:

1439

Step 4: Check wraparound

1440 - 1439 + 0 = 1

Final minimum:

1

Output

1

Example 2

Input

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

Step 1: Convert to minutes

Time Minutes
00:00 0
23:59 1439
00:00 0

Array:

[0, 1439, 0]

Step 2: Sort

[0, 0, 1439]

Step 3: Compare adjacent times

Pair Difference
0 - 0 0
1439 - 0 1439

Minimum becomes:

0

Step 4: Check wraparound

1440 - 1439 + 0 = 1

Minimum remains:

0

Output

0

Complexity Analysis

Measure Complexity Explanation
Time O(n log n) Sorting dominates the runtime
Space O(n) Stores converted minute values

The conversion phase takes O(n) time, and scanning adjacent differences also takes O(n). However, sorting requires O(n log n) time, which dominates the total complexity.

The additional space comes from storing the converted minute values in an array, requiring O(n) auxiliary space.

Test Cases

solution = Solution()

assert solution.findMinDifference(
    ["23:59", "00:00"]
) == 1  # midnight wraparound

assert solution.findMinDifference(
    ["00:00", "23:59", "00:00"]
) == 0  # duplicate time

assert solution.findMinDifference(
    ["01:01", "02:01", "03:00"]
) == 59  # normal sorted gap

assert solution.findMinDifference(
    ["12:00", "12:01"]
) == 1  # smallest non-zero difference

assert solution.findMinDifference(
    ["00:00", "12:00"]
) == 720  # half-day difference

assert solution.findMinDifference(
    ["23:58", "23:59", "00:00"]
) == 1  # adjacent near midnight

assert solution.findMinDifference(
    ["05:31", "22:08", "00:35"]
) == 177  # arbitrary unordered input

assert solution.findMinDifference(
    ["00:00", "00:01"]
) == 1  # minimum input size

assert solution.findMinDifference(
    ["11:11", "11:11"]
) == 0  # identical times

assert solution.findMinDifference(
    ["00:00"] * 1441
) == 0  # pigeonhole principle shortcut
Test Why
["23:59", "00:00"] Verifies midnight wraparound
["00:00", "23:59", "00:00"] Verifies duplicate detection
["01:01", "02:01", "03:00"] Tests normal sorted differences
["12:00", "12:01"] Verifies smallest positive gap
["00:00", "12:00"] Tests large difference
["23:58", "23:59", "00:00"] Verifies near-midnight ordering
["05:31", "22:08", "00:35"] Tests unordered input
["00:00", "00:01"] Validates minimum input size
["11:11", "11:11"] Tests identical times
1441 identical times Verifies pigeonhole optimization

Edge Cases

Duplicate Time Points

A common source of bugs is forgetting that identical time points can exist. If "00:00" appears twice, the minimum difference is immediately 0. The implementation naturally handles this after sorting because duplicates become adjacent, producing a difference of 0. Additionally, the pigeonhole optimization catches guaranteed duplicates when the input size exceeds 1440.

Midnight Wraparound

The smallest difference may occur across midnight instead of between adjacent sorted values. For example, "23:59" and "00:00" appear far apart numerically (1439 and 0) but are actually only one minute apart on a clock. The implementation handles this explicitly using:

1440 - last + first

which correctly models circular time.

Minimal Input Size

When only two time points are present, there is only one adjacent comparison after sorting. A careless implementation might forget to check wraparound separately, causing incorrect results for cases like "23:59" and "00:00". This implementation always performs the circular comparison, ensuring correctness even for the smallest valid input size.