539. Minimum Time Difference

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 * 104
• timePoints[i] is in the format “HH:MM”.

Approach 01:

class Solution {
public:
    int findMinDifference(vector<string>& timePoints) {
        int minimumDifference = 24 * 60;  // Represents the minimum time difference in minutes
        int earliestTime = 24 * 60;  // The earliest time in the timePoints
        vector<bool> timeSeen(24 * 60, false);  // Bucket to track seen times (in minutes from 00:00)

        // Convert time points to minutes and mark them in the bucket
        for (const string& time : timePoints) {
            int currentTimeInMinutes = stoi(time.substr(0, 2)) * 60 + stoi(time.substr(3));
            earliestTime = min(earliestTime, currentTimeInMinutes);
            
            if (timeSeen[currentTimeInMinutes])  // If the time is already seen, the minimum difference is zero
                return 0;
                
            timeSeen[currentTimeInMinutes] = true;
        }

        int previousTime = earliestTime;  // Keep track of the previous time in the sorted order

        // Find the minimum difference between consecutive times
        for (int i = earliestTime + 1; i < timeSeen.size(); ++i) {
            if (timeSeen[i]) {
                minimumDifference = min(minimumDifference, i - previousTime);
                previousTime = i;
            }
        }

        // Compare the time difference between the first and last times considering the circular nature of the clock
        return min(minimumDifference, 24 * 60 - previousTime + earliestTime);
    }
};

class Solution:
    def findMinDifference(self, timePoints: List[str]) -> int:
        totalMinutesInDay = 24 * 60  # Total minutes in a day
        minimumDifference = totalMinutesInDay  # The minimum time difference in minutes
        earliestTime = totalMinutesInDay  # The earliest time in minutes
        timeSeen = [False] * totalMinutesInDay  # Bucket to track if a time has been seen

        # Convert time points to minutes and mark them in the timeSeen array
        for time in timePoints:
            currentTimeInMinutes = int(time[:2]) * 60 + int(time[3:])
            earliestTime = min(earliestTime, currentTimeInMinutes)

            if timeSeen[currentTimeInMinutes]:  # If the time has already been seen, return 0
                return 0

            timeSeen[currentTimeInMinutes] = True

        previousTime = earliestTime  # Keep track of the previous time in the sorted order

        # Find the minimum difference between consecutive times
        for i in range(earliestTime + 1, totalMinutesInDay):
            if timeSeen[i]:
                minimumDifference = min(minimumDifference, i - previousTime)
                previousTime = i

        # Compare the time difference between the first and last times considering the circular nature of the clock
        return min(minimumDifference, totalMinutesInDay - previousTime + earliestTime)

Time Complexity

• Parsing Time Points:

  Each time point is converted from a string to an integer representing minutes since midnight. For each time string, this takes constant time \(O(1)\), and for \(n\) time points, this results in \(O(n)\) time complexity.

• Marking Time Points:

  Marking each time point in the timeSeen vector takes constant time for each time point, leading to \(O(n)\) overall complexity for marking all time points.

• Finding the Minimum Difference:

  After marking all time points, the algorithm traverses the timeSeen vector, which has a fixed size of 1440 (minutes in a day). This operation takes \(O(1)\), since the traversal length does not depend on the input size.

• Overall Time Complexity:

  The overall time complexity is \(O(n)\), where n is the number of time points in the input.

Space Complexity

• Space for Time Points and Buckets:

  The algorithm uses a fixed-size vector timeSeen of size 1440 (representing each minute of the day) to mark seen times. This results in \(O(1)\) additional space since the size is constant.

• Space for Variables:

  Additional variables such as minimumDifference, earliestTime, and previousTime take up constant space \(O(1)\).

• Overall Space Complexity:

  The overall space complexity is \(O(1)\), since the space used does not scale with the input size \(n\).