Minimum time difference

100.Minimum Time Difference

Array

Sorting

Greedy

Problem Statement:

Given a list of 24-hour clock time points in "HH:MM" format, return the minimum difference in minutes between any two time points in the list.

Algorithm:

We explore two different approaches to solving this problem:

1. Bucket Solution (O(n)):
• Create a boolean array where each index represents a minute in a day (1440 total).
• Mark the presence of each time point by converting it to minutes and setting the corresponding index in the array to true.
• Iterate through the array to find the smallest difference between adjacent true values and account for the circular nature of time.
2. Sorting Solution (O(n log n)):
• Convert each time point to minutes and store it in an array.
• Sort the array in ascending order.
• Calculate the difference between adjacent elements and include the circular difference (last and first times).

Complexity:

Bucket Solution: Time O(n) | Space O(1)
Sorting Solution: Time O(n log n) | Space O(n)

Java Implementation:

public class Solution {
    // Bucket Solution
    public int findMinDifference(List timePoints) {
        boolean[] minutes = new boolean[24 * 60]; // 1440 minutes in a day
        for (String time : timePoints) {
            int min = Integer.parseInt(time.substring(0, 2)) * 60 +
                      Integer.parseInt(time.substring(3));
            if (minutes[min]) return 0; // Duplicate times mean minimum difference is 0
            minutes[min] = true;
        }

        int firstIndex = -1, lastIndex = -1, ans = Integer.MAX_VALUE;
        for (int i = 0; i < 1440; i++) {
            if (minutes[i]) {
                if (lastIndex != -1) ans = Math.min(ans, i - lastIndex);
                if (firstIndex == -1) firstIndex = i;
                lastIndex = i;
            }
        }
        return Math.min(ans, 1440 - lastIndex + firstIndex);
    }

    // Sorting Solution
    public int findMinDifferenceSort(List timePoints) {
        int[] minutes = new int[timePoints.size()];
        for (int i = 0; i < timePoints.size(); i++) {
            String time = timePoints.get(i);
            int h = Integer.parseInt(time.substring(0, 2));
            int m = Integer.parseInt(time.substring(3));
            minutes[i] = h * 60 + m;
        }

        Arrays.sort(minutes); // Sort times in ascending order
        int ans = Integer.MAX_VALUE;
        for (int i = 0; i < minutes.length - 1; i++) {
            ans = Math.min(ans, minutes[i + 1] - minutes[i]);
        }
        return Math.min(ans, 1440 - minutes[minutes.length - 1] + minutes[0]);
    }
}
                

Python Implementation:

def findMinDifference(timePoints):
    # Bucket Solution
    minutes = [False] * 1440
    for time in timePoints:
        h, m = map(int, time.split(":"))
        total_minutes = h * 60 + m
        if minutes[total_minutes]:
            return 0
        minutes[total_minutes] = True

    first_index, last_index, ans = -1, -1, float("inf")
    for i in range(1440):
        if minutes[i]:
            if last_index != -1:
                ans = min(ans, i - last_index)
            if first_index == -1:
                first_index = i
            last_index = i
    return min(ans, 1440 - last_index + first_index)

def findMinDifferenceSort(timePoints):
    # Sorting Solution
    minutes = []
    for time in timePoints:
        h, m = map(int, time.split(":"))
        minutes.append(h * 60 + m)

    minutes.sort() # Sort times in ascending order
    ans = float("inf")
    for i in range(len(minutes) - 1):
        ans = min(ans, minutes[i + 1] - minutes[i])
    return min(ans, 1440 - minutes[-1] + minutes[0])
                

C++ Implementation:

#include 
#include 
#include 
#include 
using namespace std;

int findMinDifference(vector& timePoints) {
    // Bucket Solution
    vector minutes(1440, false);
    for (const auto& time : timePoints) {
        int h = stoi(time.substr(0, 2));
        int m = stoi(time.substr(3));
        int total_minutes = h * 60 + m;
        if (minutes[total_minutes]) return 0;
        minutes[total_minutes] = true;
    }

    int first_index = -1, last_index = -1, ans = INT_MAX;
    for (int i = 0; i < 1440; i++) {
        if (minutes[i]) {
            if (last_index != -1) ans = min(ans, i - last_index);
            if (first_index == -1) first_index = i;
            last_index = i;
        }
    }
    return min(ans, 1440 - last_index + first_index);
}

int findMinDifferenceSort(vector& timePoints) {
    // Sorting Solution
    vector minutes;
    for (const auto& time : timePoints) {
        int h = stoi(time.substr(0, 2));
        int m = stoi(time.substr(3));
        minutes.push_back(h * 60 + m);
    }

    sort(minutes.begin(), minutes.end());
    int ans = INT_MAX;
    for (int i = 0; i < minutes.size() - 1; i++) {
        ans = min(ans, minutes[i + 1] - minutes[i]);
    }
    return min(ans, 1440 - minutes.back() + minutes.front());
}