Minimum Time Difference

MEDIUM

Description

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 * 10⁴
timePoints[i] is in the format "HH:MM".

Approaches

Checkout 3 different approaches to solve Minimum Time Difference. Click on different approaches to view the approach and algorithm in detail.

Brute Force Comparison

The most straightforward approach is to compare every possible pair of time points in the list. For each pair, we calculate the time difference in minutes and keep track of the minimum difference found so far. A key detail is to handle the circular nature of the 24-hour clock; for example, the difference between "23:59" and "00:00" is 1 minute, not 1439 minutes.

Algorithm

Initialize a variable minDiff to a very large value (e.g., Integer.MAX_VALUE).
Use nested loops to iterate through every unique pair of time points in the input list.
For each pair of time strings, convert them into total minutes from midnight (00:00). For a time HH:MM, the total minutes are HH * 60 + MM.
Calculate the absolute difference between the two minute values, let's call it diff.
Since the clock is circular, the actual difference is the smaller of diff and the wrap-around difference, which is (24 * 60) - diff.
Update minDiff with the minimum of its current value and the calculated circular difference.
After checking all pairs, return minDiff.

This method involves a nested loop structure. The outer loop picks a time point, and the inner loop iterates through the subsequent time points to form a pair. For each pair, we first need a helper function to convert the "HH:MM" string format into a numerical representation, such as the total number of minutes past midnight. Once we have two time points as minutes, say t1 and t2, we calculate two potential differences: the direct difference abs(t1 - t2) and the wrap-around difference (24 * 60) - abs(t1 - t2). The smaller of these two is the true minimum difference for that pair. We compare this value with a global minimum and update it if necessary. We repeat this for all pairs.

class Solution {
    public int findMinDifference(java.util.List<String> timePoints) {
        int minDiff = Integer.MAX_VALUE;
        int n = timePoints.size();

        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int time1 = convertToMinutes(timePoints.get(i));
                int time2 = convertToMinutes(timePoints.get(j));
                
                int diff = Math.abs(time1 - time2);
                // Consider the wrap-around difference
                int circularDiff = Math.min(diff, 24 * 60 - diff);
                
                minDiff = Math.min(minDiff, circularDiff);
            }
        }
        return minDiff;
    }

    private int convertToMinutes(String time) {
        String[] parts = time.split(":");
        return Integer.parseInt(parts[0]) * 60 + Integer.parseInt(parts[1]);
    }
}

Complexity Analysis

Time Complexity: O(N^2), where N is the number of time points. We iterate through all possible pairs of time points, which is N * (N-1) / 2 pairs.Space Complexity: O(1), as we only use a few variables to store the minimum difference and intermediate calculations, regardless of the input size.

Pros and Cons

Pros:

Simple to understand and implement.
Requires no extra space.

Cons:

Highly inefficient, with a time complexity of O(N^2).
Will result in a 'Time Limit Exceeded' error on platforms like LeetCode for larger inputs.

Code Solutions

Checking out 3 solutions in different languages for Minimum Time Difference. Click on different languages to view the code.

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

Video Solution

Watch the video walkthrough for Minimum Time Difference

Algorithms:

Sorting

Patterns:

Math

Data Structures:

ArrayString

Companies:

Visa |Zoho |carwale |Palantir Technologies |