• Posts

Problem 539 Minimum Time Difference

Problem Statement

Link - Problem 539

Question

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.

Example 1:

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

Example 2:

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

Constraints:

• 2 <= timePoints.length <= 2 * 104
• timePoints[i] is in the format "HH:MM".

Solution

class Solution {
public:
    int findMinDifference(vector<string>& timePoints) {
        vector<int> minutes(timePoints.size());
        for (int i = 0; i < timePoints.size(); i++) {
            string time = timePoints[i];
            int h = stoi(time.substr(0, 2));
            int m = stoi(time.substr(3));
            minutes[i] = 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, 24 * 60 - minutes[minutes.size() - 1] + minutes[0]);
    }
};

Complexity Analysis

| Algorithm        | Time Complexity | Space Complexity |
| ---------------- | --------------- | ---------------- |
| Modified Sorting | O(n log n)      | O(n)             |

Explanation

Intial Thoughts

The problem can be approached by first converting all time points to a common unit, such as minutes. Then, sorting these time points can help identify the closest times. Considering the 24-hour clock, it’s also important to account for times that wrap around from the end of the day to the beginning. Key points to consider are: converting time to minutes, sorting the times, comparing adjacent times, and handling the wrap-around case. Additionally, thinking about the minimum and maximum possible differences can help guide the solution. The problem also involves understanding the concept of time and how it can be represented in a 24-hour format.

Intuitive Analysis

To intuitively solve the problem, think of the time points as points on a circle, where the circle represents the 24-hour clock. The minimum difference between two times is equivalent to finding the shortest distance between two points on the circle. This can be achieved by sorting the times and comparing adjacent points. However, to handle the wrap-around case, it’s necessary to consider the distance between the first and last points on the circle. Key insights include: recognizing that the problem involves finding the minimum distance between points on a circle, understanding how to convert time to a suitable format, and realizing the importance of considering the wrap-around case. The solution also involves using analogies, such as the circle, to simplify the problem and make it easier to understand.

1. Intuition

• The problem requires finding the minimum minutes difference between any two time-points in a list of 24-hour clock time points.
• To approach this problem, we need to first convert the time points from HH:MM format to minutes.
• We should sort the time points in ascending order to easily find the minimum difference between adjacent time points.
• The key insight is to consider the difference between the last and the first time points, taking into account the 24-hour clock.
• This solution works because it covers all possible cases, including when the minimum difference is between two time points that are not adjacent in the sorted list.
• The algorithmic choice of sorting the time points allows for an efficient solution with a time complexity of O(n log n).
• Considering the 24-hour clock, we need to handle the case where the minimum difference is between the last and the first time points, which may be on different days.

2. Implementation

• We use a for loop to iterate over the timePoints vector and convert each time point to minutes using stoi(time.substr(0, 2)) * 60 + stoi(time.substr(3)).
• The sort function is used to sort the minutes vector in ascending order.
• We initialize ans to INT_MAX to ensure that the first difference found is smaller.
• We use a for loop to iterate over the sorted minutes vector and update ans with the minimum difference found.
• We use the expression 24 * 60 - minutes[minutes.size() - 1] + minutes[0] to calculate the difference between the last and the first time points, considering the 24-hour clock.
• The min function is used to update ans with the minimum of the current ans and the difference between the last and the first time points.
• The function returns the minimum difference found, which is stored in ans.

Complexity Analysis

Time Complexity:

• The given algorithm has two dominant operations: the conversion and sorting of time points, and the iteration over the sorted time points to find the minimum difference. The sort(minutes.begin(), minutes.end()) line is the primary contributor to the time complexity, with a Big O classification of O(n log n) due to the use of a comparison-based sorting algorithm.
• The subsequent for loop, which iterates over the sorted time points to find the minimum difference, has a time complexity of O(n). However, this is dominated by the O(n log n) complexity of the sorting operation, resulting in an overall time complexity of O(n log n).
• Mathematically, the time complexity can be represented as T(n) = O(n log n) + O(n) = O(n log n), where n is the number of time points. The worst, average, and best cases all have the same time complexity, as the sorting operation dominates the algorithm’s performance.

Space Complexity:

• The algorithm uses a vector data structure, minutes, to store the time points in minutes, resulting in a space complexity of O(n), where n is the number of time points.
• The space complexity is linear because each time point is stored in the minutes vector, and no additional data structures are used that scale with the input size.
• The justification for the space complexity is based on the fact that the algorithm only uses a single data structure that scales with the input size, and no additional space is allocated that would increase the space complexity beyond O(n).

Footnote

This question is rated as Medium difficulty.

Similar Questions: