Problem of The Day: Minimum Time Difference

Problem Statement

Intuition

The problem asks us to find the minimum difference between any two time points in a given list of time strings. Since time is cyclical (i.e., the time wraps around after 24 hours), the intuitive approach is to convert all the time points to minutes, sort them, and compute the differences between consecutive times. Additionally, we must consider the difference between the first and last time, accounting for the wrap-around at midnight.

Approach

1. Convert each time point from HH:MM format into the total number of minutes since midnight.
2. Store these values in a list and sort it.
3. Calculate the difference between consecutive time points in the sorted list, ensuring to account for the wrap-around from the last time back to the first time.
4. Keep track of the minimum difference encountered.
5. Return the minimum difference.

Complexity

• Time complexity:
  The time complexity is dominated by the sorting step, so the time complexity is \(O(n \log n)\), where n is the number of time points.

• Space complexity:
  The space complexity is \(O(n)\) because we store the converted time points in a list.

Code

class Solution:
    def findMinDifference(self, timePoints: List[str]) -> int:
        converted_list = []
        total_min = 24 * 60
        for timePoint in timePoints:
            hour, mins = timePoint.split(':')
            curr_total_min = int(hour) * 60 + int(mins)
            if curr_total_min == 0:
                curr_total_min = total_min
            converted_list.append(curr_total_min)
        converted_list.sort()
        converted_list.append(converted_list[0] + total_min)
        min_diff = float('inf')
        for i in range(len(converted_list) - 1):
            diff = (converted_list[i + 1] - converted_list[i])
            min_diff = min(min_diff, diff)
        return min_diff

Editorial

Approach 1: Sort

class Solution:
    def findMinDifference(self, timePoints: List[str]) -> int:
        # convert input to minutes
        minutes = [int(time[:2]) * 60 + int(time[3:]) for time in timePoints]

        # sort times in ascending order
        minutes.sort()

        # find minimum difference across adjacent elements
        ans = min(minutes[i + 1] - minutes[i] for i in range(len(minutes) - 1))

        # consider difference between last and first element
        return min(ans, 24 * 60 - minutes[-1] + minutes[0])

• time: O(N log N)
• space: O(N)

Approach 2: Bucket Sort

class Solution:
    def findMinDifference(self, timePoints: List[str]) -> int:
        # create buckets array for the times converted to minutes
        minutes = [False] * (24 * 60)
        for time in timePoints:
            h, m = map(int, time.split(":"))
            min_time = h * 60 + m
            if minutes[min_time]:
                return 0
            minutes[min_time] = True
        prevIndex = float("inf")
        firstIndex = float("inf")
        lastIndex = float("inf")
        ans = float("inf")

        # find differences between adjacent elements in sorted array
        for i in range(24 * 60):
            if minutes[i]:
                if prevIndex != float("inf"):
                    ans = min(ans, i - prevIndex)
                prevIndex = i
                if firstIndex == float("inf"):
                    firstIndex = i
                lastIndex = i

        return min(ans, 24 * 60 - lastIndex + firstIndex)

• time: O(N)
• space: O(1)