Minimum Time Difference - Leetcode Solution

The Minimum Time Difference problem on LeetCode asks the user to find the minimum difference in time between any given pair of time stamps in a list of time stamps.

The input to the problem is a list of time stamps in the format "hh:mm". The time stamps in the list are unordered and may repeat. The output is the minimum difference in minutes between any pair of time stamps in the list.

To solve this problem, we can use three steps:

1. Convert each time stamp to minutes.
2. Sort the time stamps in ascending order.
3. Calculate the minimum difference between adjacent time stamps and compare it to other differences until we find the minimum time difference.

Here's the Python code:

class Solution:
    def findMinDifference(self, timePoints: List[str]) -> int:
        
        # Step 1: Convert each time stamp to minutes and store the values in a list
        minutes = []
        for time in timePoints:
            hour, minute = time.split(':')
            minutes.append(int(hour) * 60 + int(minute))
        
        # Step 2: Sort the time stamps in ascending order
        minutes.sort()
        
        # Step 3: Calculate the minimum difference between adjacent time stamps
        min_diff = float('inf')
        for i in range(len(minutes) - 1):
            diff = minutes[i+1] - minutes[i]
            if diff < min_diff:
                min_diff = diff
                
        # Check the difference between the first and the last element
        diff = minutes[0] + 1440 - minutes[-1]
        if diff < min_diff:
            min_diff = diff
        
        # Return the minimum difference
        return min_diff

In this implementation, we first convert each time stamp to minutes and store the values in a list called "minutes". Then we use Python's built-in "sort()" method to sort the list in ascending order.

We then use a loop to calculate the difference between adjacent time stamps and update the minimum difference if necessary. The "float('inf')" is used to initialize the "min_diff" variable to an infinitely large value at the beginning of the loop.

After this loop, we need to check whether the difference between the first and the last element in the sorted list is smaller than the minimum difference we have found so far. If it is, we update the "min_diff" variable.

Finally, we return the minimum difference.

1class Solution {
2public:
3    int findMinDifference(vector<string>& timePoints) {
4        // sort the vector in ascending order
5        sort(timePoints.begin(), timePoints.end());
6        
7        // initialize the minimum difference to be the difference between the first and last time points
8        int minDiff = getDifference(timePoints[0], timePoints[timePoints.size() - 1]);
9        
10        // iterate through the vector, comparing the differences between adjacent time points
11        for (int i = 1; i < timePoints.size(); i++) {
12            int diff = getDifference(timePoints[i - 1], timePoints[i]);
13            minDiff = min(minDiff, diff);
14        }
15        
16        return minDiff;
17    }
18    
19    // helper function to get the difference between two time points in minutes
20    int getDifference(string time1, string time2) {
21        int hour1 = stoi(time1.substr(0, 2));
22        int min1 = stoi(time1.substr(3, 2));
23        int hour2 = stoi(time2.substr(0, 2));
24        int min2 = stoi(time2.substr(3, 2));
25        
26        // if the difference is negative, we take the absolute value and add 1440 (one day in minutes)
27        int diff = (hour2 - hour1) * 60 + (min2 - min1);
28        return diff < 0 ? abs(diff) + 1440 : diff;
29    }
30};