539. Minimum Time Difference

Description

The problem requires determining the minimum difference in time between any two given time points, considering that time wraps around after midnight (i.e., 24-hour format). Time points are provided in "HH:MM" format, and we need to return the smallest difference between any two time points in minutes.

Intuition

The key observation is that the time points are circular, meaning that we should account for the fact that the time difference between the last and first time points might be the smallest. Converting the time points into minutes from midnight allows for easier comparison of time differences. Sorting the time points in minutes and calculating consecutive differences helps us find the minimum difference efficiently.

Approach

1. Convert each time point into the total number of minutes since midnight.
2. Sort the time points to simplify finding consecutive differences.
3. Append the first time point plus 1440 minutes (one day) to account for circular behavior.
4. Iterate through the sorted time points, computing the difference between consecutive entries, including the circular case.
5. Return the minimum difference found.

Complexity

Time Complexity:

O(n log n), where n is the number of time points. Sorting the time points takes O(n log n), and calculating the differences takes O(n).

Space Complexity:

O(n), as we store the time points in minutes in an additional list.

Code

C++

class Solution {
public:
    int findMinDifference(std::vector& timePoints) {
        std::vector minutes;

        // Convert time strings into minutes
        for (std::string& time : timePoints) {
            int hours = std::stoi(time.substr(0, 2));
            int mins = std::stoi(time.substr(3, 2));
            minutes.push_back(hours * 60 + mins);
        }

        // Sort the time in minutes
        std::sort(minutes.begin(), minutes.end());

        // Append the first time + 1440 to handle the circular case
        minutes.push_back(minutes[0] + 1440);

        // Find the minimum difference
        int minDiff = INT_MAX;
        for (int i = 1; i < minutes.size(); ++i) {
            minDiff = std::min(minDiff, minutes[i] - minutes[i - 1]);
        }

        return minDiff;
    }
};

Python

class Solution:
    def findMinDifference(self, timePoints: List[str]) -> int:
        # Convert time strings into minutes
        minutes = []
        for time in timePoints:
            hours, mins = map(int, time.split(":"))
            minutes.append(hours * 60 + mins)
        
        # Sort the time in minutes
        minutes.sort()
        
        # Append the first time + 1440 to handle the circular case
        minutes.append(minutes[0] + 1440)
        
        # Find the minimum difference
        minDiff = float('inf')
        for i in range(1, len(minutes)):
            minDiff = min(minDiff, minutes[i] - minutes[i - 1])
        
        return minDiff

Java

class Solution {
    public int findMinDifference(List timePoints) {
        List minutes = new ArrayList<>();

        // Convert time strings into minutes
        for (String time : timePoints) {
            String[] split = time.split(":");
            int hours = Integer.parseInt(split[0]);
            int mins = Integer.parseInt(split[1]);
            minutes.add(hours * 60 + mins);
        }

        // Sort the time in minutes
        Collections.sort(minutes);

        // Append the first time + 1440 to handle the circular case
        minutes.add(minutes.get(0) + 1440);

        // Find the minimum difference
        int minDiff = Integer.MAX_VALUE;
        for (int i = 1; i < minutes.size(); i++) {
            minDiff = Math.min(minDiff, minutes.get(i) - minutes.get(i - 1));
        }

        return minDiff;
    }
}

JavaScript

var findMinDifference = function (timePoints) {

    timePoints.sort();
    timePoints = timePoints.map(el => {
        let [hours, minutes] = el.split(':');

        return Number(hours) * 60 + Number(minutes);
    })

    timePoints.push(timePoints[0] + 1440);
    let minDiff = Infinity;
    
    for (let i = 1; i < timePoints.length; i++) {
        minDiff = Math.min(minDiff, timePoints[i] - timePoints[i - 1]);
    }

    return minDiff;
};