Minimum Time Difference

Problem Statement

LeetCode-539: 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: timePoints = ["23:59","00:00"]
Output: 1

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

timePoints[i] is in the format “HH:MM”.

Approach

A few observations to make:

1. The minimum difference between two time points can be calculated by sorting the time points and then calculating the difference between adjacent time points.
2. To simplify the calculation, we can convert the time points to minutes. This will make it easier to calculate the difference between two time points.
3. Due to the circular nature of the clock, the difference between the first and last time points should also be considered.
4. The overall time complexity of the solution will be governed by the sorting of the time points.

Implementation

Here is a Java implementation of the approach:

public int findMinDifference(List<String> timePoints) {
    int[] minutes = new int[timePoints.size()];
    for (int i = 0; i < timePoints.size(); i++) {
        String[] time = timePoints.get(i).split(":");
        int hours = Integer.parseInt(time[0]);
        int mins = Integer.parseInt(time[1]);
        minutes[i] = hours * 60 + mins;
    }
    
    Arrays.sort(minutes);
    int ans = Integer.MAX_VALUE;
    for (int i = 0; i < minutes.length - 1; i++) {
        ans = Math.min(ans, minutes[i + 1] - minutes[i]);
    }
    
    // compare the extreme time points
    // considering the circular nature of the clock
    return Math.min(
        ans,
        24 * 60 - minutes[minutes.length - 1] + minutes[0]
    );
}

Complexity Analysis

As mentioned above the overall time complexity of the solution will be governed by the sorting of the time points. Assuming there are $n$ time points, the time complexity of sorting the time points will be $O(n \cdot \log n)$.

Follow-up

We can improve the time complexity of the solution by using a bucket sort approach. Since the time points are in the range of $0 \rightarrow 24 * 60$ (post conversion to minutes), we can use a linear time complexity approach to sort the time points.

Refer to bucket sort algorithm for more details.