Code Implementation

class Solution:
    def findMinDifference(self, timePoints):
        minutes = []
        for time in timePoints:
            h, m = map(int, time.split(":"))
            minutes.append(h * 60 + m)
        minutes.sort()
        min_diff = 1440  # Maximum possible in 24h
        for i in range(1, len(minutes)):
            min_diff = min(min_diff, minutes[i] - minutes[i-1])
        # Wrap around difference (last and first)
        min_diff = min(min_diff, 1440 + minutes[0] - minutes[-1])
        return min_diff
      

class Solution {
public:
    int findMinDifference(vector<string>& timePoints) {
        vector<int> minutes;
        for (const string& time : timePoints) {
            int h = stoi(time.substr(0,2));
            int m = stoi(time.substr(3,2));
            minutes.push_back(h * 60 + m);
        }
        sort(minutes.begin(), minutes.end());
        int minDiff = 1440;
        for (int i = 1; i < minutes.size(); ++i) {
            minDiff = min(minDiff, minutes[i] - minutes[i-1]);
        }
        minDiff = min(minDiff, 1440 + minutes[0] - minutes.back());
        return minDiff;
    }
};
      

class Solution {
    public int findMinDifference(List<String> timePoints) {
        List<Integer> minutes = new ArrayList<>();
        for (String time : timePoints) {
            String[] parts = time.split(":");
            int h = Integer.parseInt(parts[0]);
            int m = Integer.parseInt(parts[1]);
            minutes.add(h * 60 + m);
        }
        Collections.sort(minutes);
        int minDiff = 1440;
        for (int i = 1; i < minutes.size(); ++i) {
            minDiff = Math.min(minDiff, minutes.get(i) - minutes.get(i-1));
        }
        minDiff = Math.min(minDiff, 1440 + minutes.get(0) - minutes.get(minutes.size()-1));
        return minDiff;
    }
}
      

var findMinDifference = function(timePoints) {
    let minutes = timePoints.map(time => {
        let [h, m] = time.split(":").map(Number);
        return h * 60 + m;
    });
    minutes.sort((a, b) => a - b);
    let minDiff = 1440;
    for (let i = 1; i < minutes.length; ++i) {
        minDiff = Math.min(minDiff, minutes[i] - minutes[i-1]);
    }
    minDiff = Math.min(minDiff, 1440 + minutes[0] - minutes[minutes.length-1]);
    return minDiff;
};
      

Problem Description

You are given a list of strings, timePoints, where each string represents a time in the 24-hour format "HH:MM". Your task is to find the minimum difference in minutes between any two time points in the list.

• Each time is a valid 24-hour time (e.g., "23:59", "00:00").
• The difference between two times may wrap around midnight (e.g., the difference between "23:59" and "00:00" is 1 minute).
• Return the minimum difference in minutes between any two time points.
• You can assume there is at least two time points.

Thought Process

At first glance, it may seem that we need to compare every pair of time points to find the minimum difference. This brute-force approach would involve calculating the difference between all possible pairs, which can be slow if there are many time points.

However, since time wraps around at midnight, we need to be careful when calculating the difference. For example, the difference between "23:59" and "00:00" is only 1 minute, not 1439.

To optimize, we can convert all times to minutes since midnight, sort them, and then only need to check the differences between adjacent times in the sorted list (including the wrap-around case).

Solution Approach

• Step 1: Convert each time string in timePoints to the number of minutes since midnight. For example, "01:30" becomes 90.
• Step 2: Sort the list of minutes. Sorting ensures that the smallest differences (except wrap-around) will be between adjacent times.
• Step 3: Iterate through the sorted list and compute the difference between each pair of adjacent times.
• Step 4: To handle the wrap-around case (from the last time to the first time on the next day), compute the difference between the last and first time, considering the 24-hour cycle (i.e., 1440 + first - last).
• Step 5: Return the minimum difference found.

Sorting is used to efficiently find the smallest difference, as the closest times will be next to each other in the sorted order. Converting to minutes simplifies the calculations and makes wrap-around handling straightforward.

Example Walkthrough

Let's consider the input ["23:59","00:00","12:30"].

1. Convert to minutes:
   • "23:59" → 23*60 + 59 = 1439
   • "00:00" → 0*60 + 0 = 0
   • "12:30" → 12*60 + 30 = 750
2. Sort: [0, 750, 1439]
3. Compute differences:
   • Between 0 and 750: 750
   • Between 750 and 1439: 689
   • Wrap-around: 1440 + 0 - 1439 = 1
4. Minimum difference is 1 minute.

This shows how the wrap-around case can produce the minimum difference.

Time and Space Complexity

• Brute-force approach:
  • Compare every pair: O(N^2) time, where N is the number of time points.
  • Space: O(N) for storing converted minutes.
• Optimized approach:
  • Convert times: O(N) time.
  • Sort times: O(N log N) time.
  • Single pass for differences: O(N) time.
  • Total: O(N log N) time, O(N) space.

The optimized approach is much faster for large inputs.

Summary

The key insight is to convert times to minutes, sort them, and only check adjacent pairs (including the wrap-around), rather than all possible pairs. This leverages sorting for efficiency and handles the day wrap-around elegantly, resulting in a concise and efficient solution.