LeetCode 539: Minimum Time Difference

Problem Restatement

We are given a list of time points in 24-hour "HH:MM" format.

We need to return the minimum difference in minutes between any two time points. The clock wraps around after midnight, so the difference between "23:59" and "00:00" is 1, not 1439.

The input contains at least two time points. Each time point is formatted as "HH:MM".

Input and Output

Function shape:

def findMinDifference(timePoints: list[str]) -> int:
    ...

Examples

Consider:

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

The difference across midnight is:

1

So the answer is:

1

Another example:

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

The time "00:00" appears twice.

Two identical time points have difference:

0

So the answer is:

0

First Thought: Compare Every Pair

A direct solution is to compare every pair of time points.

For each pair, convert both times to minutes and compute the circular difference.

For times a and b, the direct difference is:

abs(a - b)

But because the clock wraps around, the circular difference is:

min(abs(a - b), 1440 - abs(a - b))

This works, but it takes O(n^2) time.

Since the number of time points can be large, we should avoid comparing every pair.

Key Insight

There are only:

24 * 60 = 1440

possible time values in one day.

Also, after converting times to minutes and sorting them, the minimum difference must occur between two adjacent values in sorted order, including the circular pair between the last and first time.

For example:

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

converts to:

[0, 30, 1439]

Adjacent differences are:

30 - 0 = 30
1439 - 30 = 1409

But we must also compare the wrap-around difference:

1440 - 1439 + 0 = 1

So the answer is 1.

Algorithm

1. If there are more than 1440 time points, return 0.

   By the pigeonhole principle, at least two time points must be equal.

2. Convert each time string to minutes since midnight.

   For "HH:MM":

hours * 60 + minutes

3. Sort the minute values.

4. Compare every adjacent pair.

5. Compare the circular pair: last time to first time across midnight.

6. Return the smallest difference.

Correctness

After converting each time point to minutes since midnight, every time becomes an integer from 0 to 1439.

Sorting these values places them in chronological order within the same day.

For any two non-adjacent times in sorted order, there is at least one time between them. Therefore, the gap between the non-adjacent pair cannot be smaller than all gaps among adjacent times inside that interval.

So the minimum non-circular difference must occur between adjacent sorted values.

The only pair not represented by normal adjacency is the pair across midnight: the largest time of the day and the smallest time of the day. The algorithm explicitly checks this wrap-around gap.

Therefore, the algorithm examines every possible candidate for the minimum circular time difference and returns the correct answer.

Complexity

Let n = len(timePoints).

The early duplicate rule can return 0 immediately when n > 1440.

Implementation

class Solution:
    def findMinDifference(self, timePoints: list[str]) -> int:
        if len(timePoints) > 1440:
            return 0

        minutes = []

        for time in timePoints:
            hour = int(time[:2])
            minute = int(time[3:])
            minutes.append(hour * 60 + minute)

        minutes.sort()

        answer = 1440

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

        wrap_difference = 1440 - minutes[-1] + minutes[0]
        answer = min(answer, wrap_difference)

        return answer

Code Explanation

There are only 1440 possible minute values in a day:

if len(timePoints) > 1440:
    return 0

If the input has more than 1440 values, at least two are equal, so the minimum difference is 0.

Each time string is converted to minutes:

hour = int(time[:2])
minute = int(time[3:])
minutes.append(hour * 60 + minute)

For example:

"23:59" -> 23 * 60 + 59 = 1439

After sorting:

minutes.sort()

we compare adjacent values:

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

Then we check the midnight wrap-around case:

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

For "23:59" and "00:00", this gives:

1440 - 1439 + 0 = 1

Bucket Version

Because there are only 1440 possible times, we can avoid sorting by using a boolean bucket array.

class Solution:
    def findMinDifference(self, timePoints: list[str]) -> int:
        if len(timePoints) > 1440:
            return 0

        seen = [False] * 1440

        for time in timePoints:
            hour = int(time[:2])
            minute = int(time[3:])
            value = hour * 60 + minute

            if seen[value]:
                return 0

            seen[value] = True

        first = None
        prev = None
        answer = 1440

        for value in range(1440):
            if not seen[value]:
                continue

            if first is None:
                first = value

            if prev is not None:
                answer = min(answer, value - prev)

            prev = value

        answer = min(answer, 1440 - prev + first)
        return answer

This version runs in O(n + 1440) time and uses O(1440) space.

Testing

def run_tests():
    s = Solution()

    assert s.findMinDifference(["23:59", "00:00"]) == 1
    assert s.findMinDifference(["00:00", "23:59", "00:00"]) == 0
    assert s.findMinDifference(["01:01", "02:01", "03:00"]) == 59
    assert s.findMinDifference(["00:00", "12:00"]) == 720
    assert s.findMinDifference(["23:50", "00:10"]) == 20

    print("all tests passed")

run_tests()