#539

Medium

LeetCode Problem Workspace

Minimum Time Difference

Calculate the smallest time difference between clock points using array manipulation and mathematical conversions efficiently.

array math string sorting

Problem Statement

Given a list of time points in 24-hour "HH:MM" format, find the minimum difference in minutes between any two times. The difference is measured on a circular clock, meaning the day wraps from 23:59 to 00:00.

Return the smallest difference in minutes. Each time point is guaranteed to be a valid 24-hour format, and duplicates may appear, making zero the minimum in some cases.

Examples

Example 1

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

Output: 1

Example details omitted.

Example 2

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

Output: 0

Example details omitted.

Constraints

2 <= timePoints.length <= 2 * 104
timePoints[i] is in the format "HH:MM".

Solution Approach

Convert Times to Minutes

Iterate through the array of time strings, split each into hours and minutes, and convert each to total minutes. This allows straightforward numerical comparison instead of string manipulation.

Sort and Compute Differences

Sort the array of minute values, then compute differences between consecutive elements. Track the minimum difference found in this linear pass, which identifies the smallest gap efficiently.

Handle Circular Difference

Include the difference between the last and first element across midnight using modulo 1440 to account for the day wrap-around. This ensures the circular nature of time is respected and no minimal gap is missed.

Complexity Analysis

Metric	Value
Time	O(N)
Space	O(1)

Time complexity is O(N) for converting and sorting if bucket counting is used, otherwise O(N log N) with standard sort. Space complexity is O(1) aside from the array of minutes since in-place computations are possible.

What Interviewers Usually Probe

Asks about handling duplicates and zero-minute differences.
Checks awareness of circular time calculation and modulo logic.
Tests for edge cases like adjacent midnight values.

Common Pitfalls or Variants

Common pitfalls

Forgetting the wrap-around from 23:59 to 00:00 and missing minimal differences.
Incorrectly comparing string times instead of numeric minutes.
Not handling duplicate times which can produce zero difference.

Follow-up variants

Compute maximum time difference instead of minimum.
Allow times with seconds and compute minimal difference including seconds.
Find k smallest differences among all time points.

FAQ

What is the main approach for Minimum Time Difference?

Convert all time strings to minutes, sort the array, then check consecutive differences including the circular midnight case.

Can timePoints contain duplicates?

Yes, duplicates are allowed and can result in a minimum difference of zero.

Why do we need to consider circular differences?

Because the clock wraps from 23:59 to 00:00, ignoring this can miss the true minimal difference.

What is the optimal time complexity?

Using bucket sort or counting sort, the problem can be solved in O(N) time, otherwise standard sorting gives O(N log N).

Which pattern does this problem follow?

This is an Array plus Math pattern where array manipulation and numeric calculations are combined for efficient solution.

terminal

Solution

Solution 1: Sorting

We notice that there can be at most $24 \times 60 = 1440$ distinct time points. Therefore, if the length of $timePoints$ exceeds $1440$, it implies there are duplicate time points, and we can return $0$ early.

1

2

3

4

5

6

7

class Solution:
    def findMinDifference(self, timePoints: List[str]) -> int:
        if len(timePoints) > 1440:
            return 0
        nums = sorted(int(x[:2]) * 60 + int(x[3:]) for x in timePoints)
        nums.append(nums[0] + 1440)
        return min(b - a for a, b in pairwise(nums))

Continue Practicing

#524 longest word in dictionary through deleting #522 longest uncommon subsequence ii #472 concatenated words