Problem

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.

Examples

Example 1:

1
2
3

Input:
timePoints = ["23:59","00:00"]
Output: 1

Example 2:

1
2
3

Input:
timePoints = ["00:00","23:59","00:00"]
Output: 0

Solution

Method 1 - Sorting

To solve this problem, we’ll follow these steps:

  1. Convert Time Points to Minutes: Convert each time point from “HH:MM” format to the total number of minutes from 00:00.
  2. Sort the Time Points: Sort the list of times in ascending order based on their total minutes representation.
  3. Calculate Differences:
    • Calculate the difference between each consecutive time point in the sorted list.
    • Remember to consider the difference between the first and the last time point, accounting for the circular nature of the clock (i.e., the difference between “23:59” and “00:00”).
  4. Find the Minimum Difference: Keep track of the minimum difference found during the comparisons.

Video explanation

Here is the video explaining this method in detail. Please check it out:

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

public class Solution {
    public int findMinDifference(List<String> timePoints) {
        // Convert all timePoints to minutes
        List<Integer> minutesList = new ArrayList<>();
        for (String time : timePoints) {
            int minutes = convertToMinutes(time);
            minutesList.add(minutes);
        }

        // Sort the list of minutes
        Collections.sort(minutesList);

        // Initialize the minimum difference to the maximum possible value
        int minDifference = Integer.MAX_VALUE;

        // Calculate differences between consecutive time points
        for (int i = 1; i < minutesList.size(); i++) {
            int diff = minutesList.get(i) - minutesList.get(i - 1);
            minDifference = Math.min(minDifference, diff);
        }

        // Calculate the difference across the midnight boundary
        int midnightDiff =
            1440 - minutesList.get(minutesList.size() - 1) + minutesList.get(0);
        minDifference = Math.min(minDifference, midnightDiff);

        return minDifference;
    }

    private int convertToMinutes(String time) {
        String[] parts = time.split(":");
        int hours = Integer.parseInt(parts[0]);
        int minutes = Integer.parseInt(parts[1]);
        return hours * 60 + minutes;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution:
    def findMinDifference(self, timePoints: List[str]) -> int:
        def convertToMinutes(time: str) -> int:
            hours, minutes = time.split(":")
            return int(hours) * 60 + int(minutes)

        # Convert all time points to minutes
        minutesList = [convertToMinutes(time) for time in timePoints]

        # Sort the list of minutes
        minutesList.sort()

        # Initialize the minimum difference to a large number
        minDifference = float("inf")

        # Calculate differences between consecutive time points
        for i in range(1, len(minutesList)):
            diff = minutesList[i] - minutesList[i - 1]
            minDifference = min(minDifference, diff)

        # Calculate the difference across the midnight boundary
        midnightDiff = 1440 + minutesList[0] - minutesList[-1]
        minDifference = min(minDifference, midnightDiff)

        return minDifference

Complexity

  • Time: O(n log n) where n is number of time points in input list
    • mainly coming from sorting
    • O(n) for iterating through the list
  • Space: O(n), for storing the minute representations