539. Minimum Time Difference


Problem Description

The task is to find the smallest difference in minutes between any pair of given time points where time points are represented in "HH:MM" (24-hour) format. The expectation is to calculate and return the minimum number of minutes that one would need to add or subtract to convert one time into another, considering all possible pairs within the list.

Intuition

To arrive at the intuitive solution, consider that time points are cyclical; 00:00 comes after 23:59 in a day. Hence, the times form a circular sequence. If we have the times as minutes past midnight, then the smallest difference is not necessarily between consecutive times in a 24-hour window but may span across midnight. Here's the step-by-step intuition:

  1. Convert to minutes: Since we are to find differences in minutes, and times are given in hours and minutes, we convert everything into minutes to simplify calculations.

  2. Sort the times: Sorting makes consecutive time points the nearest neighbors, saving us from checking each pair of time points. After sorting, the time points form a timeline from the earliest to the latest within a day.

  3. Deal with the 24-hour wraparound: A crucial step is to handle the end-of-day wraparound when the difference between a late time and an early time spans over midnight (e.g. comparing 23:50 and 00:05). To manage this, we clone the first time point, add 24 hours (in minutes) to it, and append it to the sorted times; this simplifies our loop. The minimum difference can still be found in consecutive times because of our circular timeline.

  4. Find the minimum difference: Loop through the sorted minutes and find the minimum difference between each adjacent pair, including the end-of-day wraparound we created.

This approach ensures that all comparisons needed to ascertain the minimum time difference are made, with the cyclical nature of time taken into account, using a single loop through the points.

Learn more about Math and Sorting patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece:

What is the space complexity of the following code?

1int sum(int n) {
2  if (n <= 0) {
3    return 0;
4  }
5  return n + sum(n - 1);
6}

Solution Approach

The solution provided here leverages a few straightforward concepts: sorting, modular arithmetic (to handle the circular nature of time), and greedy algorithms (to find the minimum value). The detailed solution approach is as follows:

  1. Upper Bound Check: Before we begin any processing, we check if the list has more than 24 * 60 time points. If it does, it means there must be a duplicate time since there are only 24 * 60 minutes in a day. In this case, the minimum difference between any two time-points would be 0, as two or more time points are the same.

  2. Convert Times to Minutes: We convert each time-point from the HH:MM format to minutes since midnight using a list comprehension. This involves splitting each time string into hours and minutes, converting them to integers, and then to total minutes: int(t[:2]) * 60 + int(t[3:]).

  3. Sort Minutes: Sorting the minute values helps to place the time points on a timeline from the smallest to the largest, making it easier to calculate consecutive differences.

  4. Handle Circular Case: To address the wraparound at the end of the day (i.e., 00:00 is technically 0 minutes since midnight but follows 23:59 from the previous day), we append the smallest time (plus one full day, 24 * 60 minutes) to the end of our list.

  5. Initialize Result: We set a variable res with a high initial value (using the last element which we artificially inflated in the previous step).

  6. Find Minimum Difference: Loop through the list starting from index 1, and calculate the difference between the current element and the previous element (mins[i] - mins[i - 1]). If the difference is smaller than the current res, update res. The process ensures we find the smallest difference.

By looping through only once and having our times sorted, we effectively use a greedy approach to find the minimum time difference without having to compare every single pair, which would be less efficient.

The Solution class provided represents an implementation of these steps, using Python's list and sorting capabilities to obtain the result efficiently.

1class Solution:
2    def findMinDifference(self, timePoints: List[str]) -> int:
3        if len(timePoints) > 24 * 60:
4            return 0
5        mins = sorted(int(t[:2]) * 60 + int(t[3:]) for t in timePoints)
6        mins.append(mins[0] + 24 * 60)
7        res = mins[-1]
8        for i in range(1, len(mins)):
9            res = min(res, mins[i] - mins[i - 1])
10        return res

In summary, the algorithm uses an upper bound check, conversion to a single unit (minutes), sorting, circular case handling, and greedy minimum difference calculation to solve the problem effectively.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which one best describes the time complexity of the following code?

1int factorial(int n) {
2  if (n < 0) {
3    return -1;
4  } else if (n == 0) {
5    return 1;
6  } else {
7    return n * factorial(n - 1);
8  }
9}

Example Walkthrough

Let's illustrate the solution approach with a small example. Suppose we have the following list of time points:

1["23:59", "00:00", "12:34", "22:00"]

Now, let's walk through the steps:

  1. Upper Bound Check: The list has fewer than 24 * 60 time points, so we need to proceed with the rest of the calculation since there is no immediate indication of duplicate times.

  2. Convert Times to Minutes: We convert each time point to the number of minutes since midnight.

    • "23:59" becomes 23 * 60 + 59 = 1439 minutes.
    • "00:00" becomes 0 * 60 + 0 = 0 minutes.
    • "12:34" becomes 12 * 60 + 34 = 754 minutes.
    • "22:00" becomes 22 * 60 + 0 = 1320 minutes.
  3. Sort Minutes: We sort the minute values to get [0, 754, 1320, 1439].

  4. Handle Circular Case: We append the smallest time (plus one full day) to the end. So, 0 + 24 * 60 = 1440 minutes is added to the list, resulting in [0, 754, 1320, 1439, 1440].

  5. Initialize Result: We set res to a high initial value using the last element which was inflated in the previous step, so res = 1440.

  6. Find Minimum Difference: We calculate the differences between consecutive elements.

    • Difference between 754 and 0 is 754 - 0 = 754.
    • Difference between 1320 and 754 is 1320 - 754 = 566.
    • Difference between 1439 and 1320 is 1439 - 1320 = 119.
    • Difference between 1440 and 1439 is 1440 - 1439 = 1.

The smallest difference is 1, so we update res to 1.

Following these steps, the solution class's method findMinDifference would return 1 as the smallest difference in minutes between any two given time points in this list.

Not Sure What to Study? Take the 2-min Quiz:

Depth first search is equivalent to which of the tree traversal order?

Python Solution

1class Solution:
2    def findMinDifference(self, time_points: List[str]) -> int:
3        # If there are more time points than the total minutes in a day,
4        # it means at least two time_points are the same, 
5        # hence the minimum difference is 0.
6        if len(time_points) > 24 * 60:
7            return 0
8      
9        # Convert the time points to minutes and sort them.
10        minutes = sorted(int(time[:2]) * 60 + int(time[3:]) for time in time_points)
11      
12        # Add the first element plus 24 hours to the end of the list 
13        # to calculate the circular difference.
14        minutes.append(minutes[0] + 24 * 60)
15      
16        # Initialize the result with a maximum value for later comparison.
17        min_difference = minutes[-1]
18      
19        # Calculate the minimum difference by iterating through the sorted minutes.
20        for i in range(1, len(minutes)):
21            min_difference = min(min_difference, minutes[i] - minutes[i - 1])
22      
23        # Return the minimum difference found.
24        return min_difference
25

Java Solution

1class Solution {
2  
3    public int findMinDifference(List<String> timePoints) {
4        // If there are more time points than minutes in a day, we have at least two identical times.
5        if (timePoints.size() > 24 * 60) {
6            return 0;
7        }
8      
9        // Convert the list of time points into minutes since midnight.
10        List<Integer> timePointsInMinutes = new ArrayList<>();
11        for (String timePoint : timePoints) {
12            String[] time = timePoint.split(":");
13            int minutes = Integer.parseInt(time[0]) * 60 + Integer.parseInt(time[1]);
14            timePointsInMinutes.add(minutes);
15        }
16      
17        // Sort the list of time points in minutes.
18        Collections.sort(timePointsInMinutes);
19      
20        // Add the first time point again to the end of the list converted to the next day,
21        // to make it easier to calculate the min difference with the last time point.
22        timePointsInMinutes.add(timePointsInMinutes.get(0) + 24 * 60);
23      
24        // Initialize the minimum difference to the maximum possible value (24 hours), 
25        // which will be updated in the following loop.
26        int minDifference = 24 * 60;
27        for (int i = 1; i < timePointsInMinutes.size(); ++i) {
28            // Update the minimum difference if a smaller difference is found.
29            minDifference = Math.min(minDifference, timePointsInMinutes.get(i) - timePointsInMinutes.get(i - 1));
30        }
31      
32        // Return the minimum difference in minutes between any two time points.
33        return minDifference;
34    }
35}
36

C++ Solution

1class Solution {
2public:
3    int findMinDifference(vector<string>& timePoints) {
4        // If there are more time points than minutes in a day, there must be a duplicate.
5        // Since duplicate times would have 0 difference, return 0.
6        const int totalMinutesInDay = 24 * 60;
7        if (timePoints.size() > totalMinutesInDay) {
8            return 0;
9        }
10
11        // Vector to hold the time points in minutes since midnight.
12        vector<int> minutes;
13      
14        // Convert time points from string to minutes since midnight.
15        for (const auto& time : timePoints) {
16            int hour = stoi(time.substr(0, 2));
17            int minute = stoi(time.substr(3));
18            minutes.push_back(hour * 60 + minute);
19        }
20      
21        // Sort the converted time points.
22        sort(minutes.begin(), minutes.end());
23      
24        // Append the first time point plus 24 hours to handle the circular time comparison.
25        minutes.push_back(minutes[0] + totalMinutesInDay);
26      
27        // Initialize the result with the maximum possible difference.
28        int minDifference = totalMinutesInDay;
29      
30        // Loop through the sorted time points to find the minimum difference.
31        for (int i = 1; i < minutes.size(); ++i) {
32            // Compare each pair of adjacent time points.
33            minDifference = min(minDifference, minutes[i] - minutes[i - 1]);
34        }
35      
36        // Return the minimum time difference found.
37        return minDifference;
38    }
39};
40

Typescript Solution

1function findMinDifference(timePoints: string[]): number {
2    // Convert each time point to minutes since the start of the day and sort the array
3    const minutesArray = timePoints
4        .map(time => {
5            const hours = Number(time.slice(0, 2));
6            const minutes = Number(time.slice(3, 5));
7            return hours * 60 + minutes;
8        })
9        .sort((a, b) => a - b);
10      
11    const numTimePoints = minutesArray.length;
12    let minimumDifference = Infinity;
13
14    // Find the minimum difference between consecutive time points
15    for (let i = 0; i < numTimePoints - 1; i++) {
16        minimumDifference = Math.min(minimumDifference, minutesArray[i + 1] - minutesArray[i]);
17    }
18
19    // To account for the circular nature of the clock, 
20    // calculate the difference between the last and first time point across midnight
21    const differenceAcrossMidnight = minutesArray[0] + 24 * 60 - minutesArray[numTimePoints - 1];
22    minimumDifference = Math.min(minimumDifference, differenceAcrossMidnight);
23
24    return minimumDifference;
25}
26
Fast Track Your Learning with Our Quick Skills Quiz:

Is the following code DFS or BFS?

1void search(Node root) {
2  if (!root) return;
3  visit(root);
4  root.visited = true;
5  for (Node node in root.adjacent) {
6    if (!node.visited) {
7      search(node);
8    }
9  }
10}

Time and Space Complexity

Time Complexity

The given code comprises of several operations. Let's analyze them step-by-step:

  1. Checking Length of timePoints: The operation len(timePoints) takes O(n) time, where n is the number of elements in timePoints.
  2. Conversion and Sorting of timePoints: The conversion takes linear time, O(n) as each element is processed once. Sorting the converted times will take O(n log n) time where n is the length of the timePoints.
  3. Appending an Element: Takes O(1) time.
  4. Iterating over the Sorted mins List: This loop runs in O(n) time.

The dominant term here is O(n log n) due to the sorting step. Thus the overall time complexity is O(n log n).

Space Complexity

The space complexity includes the space required for the inputs and any additional space used by the algorithm to compute the final result:

  1. List mins: Additional space is required to store the converted time points, which is O(n).
  2. Constant Space: Used by variables for calculating the minimum, such as res and the loop index i.

Hence, the space complexity of the code is O(n) where n is the number of elements in timePoints.

Learn more about how to find time and space complexity quickly.


Recommended Readings


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫