539. Minimum Time Difference¶

Description¶

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.

Example 1

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

Example 2

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

Constraints

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

Solution: Sorting¶

Convert timePoints to minutes and sort them. The minimum difference must be the difference in an adjacent pair of times, if sort the minutes in ascending order. Thus, we can retrieve the smallest difference by calculating the difference between each adjacent pair of elements from minutes.

Why adjacent elements have smaller differences, compared to non-adjacent elements?

Difference between adjacent elements \(a_i - a_{i+1}\)
Difference between non-adjacent elements \(a_i - a_j, \text{where } j > i+1\)
Due to Monotonic Sequence¹ \(a_i \geq a_{i+1} \geq a_{i+2} \geq \ldots \geq a_n\), the difference between adjacent elements is always smaller than the difference between non-adjacent elements.

Time Complexity: O(N⋅logN),
- Convert timePoints to minutes takes O(N) time
- Sorting timePoints using QuickSort which takes O(N⋅logN) time
Space Complexity: O(N)
- minutes array takes O(N) space to store converted input

TypeScript

function findMinDifference(timePoints: string[]): number {
    function _convertToMinutes(timeString: string): number {
        const hours = Number(timeString.split(":")[0]);
        const minutes = Number(timeString.split(":")[1]);
        return hours * 60 + minutes;
    }
    const minutes = timePoints.map<number>(v => _convertToMinutes(v));

    minutes.sort((a, b) => a - b);

    let smallest = Number.MAX_SAFE_INTEGER;

    // Differences between adjacent elements
    for (let i = 0; i < minutes.length - 1; i++) {
        smallest = Math.min(smallest, minutes[i + 1] - minutes[i])
    }

    // Edge case time loop back to 00:00, comparing last and first element
    return Math.min(smallest, 24 * 60 - minutes[minutes.length - 1] + minutes[0])
};

Solution: Bucket Sort¶

Since minutes are falling in the range of 0 to 24*60, we can use Bucket Sort which can solve the problem with linear time complexity.

Time Complexity: O(n)
- O(n) to convert timePoints to minutes
- O(1) to find the minimum difference
Space Complexity: O(1)
- minutes always has a fixed size of 24*60 elements

TypeScript

function findMinDifference(timePoints: string[]): number {
    function _convertToMinutes(timeString: string): number {
        const hours = Number(timeString.split(":")[0]);
        const minutes = Number(timeString.split(":")[1]);
        return hours * 60 + minutes;
    }

    const minutes = Array(24 * 60).fill(false);

    for (let i = 0; i < timePoints.length; i++) {
        const minute = _convertToMinutes(timePoints[i]);

        // Duplicate time will be the smallest differences
        if (minutes[minute]) return 0;

        minutes[minute] = true;
    }

    let prevIndex = Number.MAX_SAFE_INTEGER;
    let firstTimePointInMinutes = Number.MAX_SAFE_INTEGER;
    let lastTimePointInMinutes = Number.MAX_SAFE_INTEGER;
    let smallest = Number.MAX_SAFE_INTEGER;

    for (let i = 0; i < 24 * 60; i++) {
        if (minutes[i]) {
            if (prevIndex != Number.MAX_SAFE_INTEGER) {
                smallest = Math.min(smallest, i - prevIndex)
            }
            prevIndex = i;
            if (firstTimePointInMinutes == Number.MAX_SAFE_INTEGER) {
                firstTimePointInMinutes = i;
            }
            lastTimePointInMinutes = i;
        }
    }

    // Edge case time loop back to 00:00, comparing last and first element
    return Math.min(smallest, 24 * 60 - lastTimePointInMinutes + firstTimePointInMinutes)
};

Why not considered it as Counting Sort?

Some said that the solution is using Counting Sort instead of Bucket Sort which is not fully wrong. But Counting Sort considered as non-comparison-based sorting algorithm, and the solution did use comparison.
Concept of Bucket Sort is dividing the range into multiple buckets, sorting each bucket, and then merging them. minutes looks like multiple buckets but only has one element inside each of them, even though the value in Bucket Sort normally will not be a binary(boolean).

What's the trade-off?

24*60 considered O(1) in theory, but it might impact the performance if timePoints is very large.
Additionally, the constant space array can be inefficient if many entries are not used which can cause overhead(higher memory resourse usage) and potentially slower performance than the sorting solution.

Monotonic Sequence ↩