539. Minimum Time Difference

MediumView on LeetCode

Array Math String Sorting

Time: O(n)

Space: O(1)

Intuition

Convert times to minutes, sort, check consecutive differences including wraparound (24*60 - last + first).

Algorithm

1Parse each "HH:MM" to total minutes.
2Sort the minutes array.
3Check all consecutive differences. Also check circular difference: 1440 - last + first.
4Return minimum difference.

Example Walkthrough

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

1.Convert: [1439, 0]. Sort: [0, 1439].
2.Consecutive diff: 1439. Circular: 1440-1439+0=1.

Output: 1

Common Pitfalls

•Don't forget the wraparound from last time to first time (adding 24*60).

539.cs

// Approach: Convert times to total minutes, bucket sort into a boolean array,
// then scan for the minimum gap including the circular wrap-around.
// Time: O(n) Space: O(1)

public class Solution
{
    public int FindMinDifference(IList<string> timePoints)
    {
        int ans = 24 * 60;
        int first = 24 * 60;

        bool[] bucket = new bool[24 * 60];

        foreach (var timePoint in timePoints)
        {
            int num = int.Parse(timePoint.Substring(0, 2)) * 60 + int.Parse(timePoint.Substring(3));
            first = Math.Min(first, num);
            if (bucket[num])
                return 0;
            bucket[num] = true;
        }

        int prev = first;

        for (int i = first + 1; i < bucket.Length; ++i)
        {
            if (bucket[i])
            {
                ans = Math.Min(ans, i - prev);
                prev = i;
            }
        }

        return Math.Min(ans, 24 * 60 - prev + first);
    }
}

Was this solution helpful?