algoadvance

Leetcode 539. Minimum Time Difference

Problem Statement

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.

Clarifying Questions

1. Input Constraints:
   • Do the time points always include valid times, i.e., formatted properly and within the 24-hour bounds?
   • How large can the list of time points be?
2. Output Requirements:
   • Should the result strictly be an integer representing the minimum difference in minutes?

For simplicity, let’s assume:

• Time points are always valid and formatted correctly.
• The maximum number of time points is reasonably small, within a few thousand.

Strategy

1. Convert Time Points to Minutes: Each time is in “HH:MM” format. Convert each time to the total number of minutes since 00:00.

2. Sort Time Points: Sort the list of times represented in minutes.

3. Calculate Differences: Iterate through the sorted list and calculate the difference between consecutive time points.

4. Consider Circular Difference: Since the clock wraps around, also consider the difference between the first and the last time (plus a wrap-around).

Code

Here’s the C++ code to solve the problem:

#include <vector>
#include <string>
#include <algorithm>
#include <climits>

using namespace std;

class Solution {
public:
    int findMinDifference(vector<string>& timePoints) {
        auto getMinutes = [](const string &time) -> int {
            int hours = stoi(time.substr(0, 2));
            int minutes = stoi(time.substr(3, 2));
            return hours * 60 + minutes;
        };

        vector<int> minutes;
        for (const auto& time : timePoints) {
            minutes.push_back(getMinutes(time));
        }

        sort(minutes.begin(), minutes.end());
        
        int minDiff = INT_MAX;
        for (size_t i = 1; i < minutes.size(); ++i) {
            minDiff = min(minDiff, minutes[i] - minutes[i - 1]);
        }

        // Circular difference (first and last elements wrap)
        int wrapAroundDiff = (1440 - minutes.back()) + minutes.front();
        minDiff = min(minDiff, wrapAroundDiff);

        return minDiff;
    }
};

Time Complexity

• Conversion of times to minutes: O(n)
• Sorting: O(n log n)
• Calculating minimum differences: O(n)

Overall, the algorithm runs in O(n log n) time due to the sorting step. The space complexity is O(n) for storing the minute representations of the times.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?