Minimum Time Difference
Minimum Time Difference is a medium arrays & hashing problem solved with the sorting pattern.
The best approach, optimal (minute buckets), runs in O(n + 1440) time and O(1440) space.
Below are 3 approaches in Java, Python, C++ and JavaScript, from brute force (compare every pair) up.
Problem
You are given a list of clock times timePoints in 24-hour "HH:MM" format. Return the smallest number of minutes between any two of the times.
The clock is circular: after 23:59 comes 00:00, so the gap between two times can be measured going either way around the day.
Examples
Example 1
- Input
timePoints = ["09:15", "21:40", "09:05"]- Output
10- Why
- 09:05 and 09:15 are 10 minutes apart, closer than any other pair.
Example 2
- Input
timePoints = ["23:50", "00:20"]- Output
30- Why
- Going forward from 23:50 past midnight reaches 00:20 after 30 minutes, which beats the 1410-minute gap the other way.
Example 3
- Input
timePoints = ["12:00", "07:30", "12:00"]- Output
0- Why
- The same time appears twice.
Constraints
2 <= timePoints.length <= 2 * 10^4- Every entry has the form
"HH:MM"with00 <= HH <= 23and00 <= MM <= 59
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 11 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (compare every pair) | O(n²) | O(n) |
| Better (sort minutes) | O(n log n) | O(n) |
| Optimal (minute buckets) | O(n + 1440) | O(1440) |
1Brute force (compare every pair)
O(n²)All n(n - 1) / 2 pairs are compared.O(n)The array of minutes.Convert each time to minutes and compute the circular difference of every pair, keeping the smallest.
- Convert "HH:MM" to HH * 60 + MM for every entry.
- For every pair i < j, d = |m[i] - m[j]|, gap = min(d, 1440 - d).
- Return the smallest gap.
class Solution {
public int findMinDifference(List<String> timePoints) {
int n = timePoints.size();
int[] m = new int[n];
for (int i = 0; i < n; i++) {
String t = timePoints.get(i);
m[i] = Integer.parseInt(t.substring(0, 2)) * 60 + Integer.parseInt(t.substring(3));
}
int best = 1440;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
int d = Math.abs(m[i] - m[j]);
best = Math.min(best, Math.min(d, 1440 - d));
}
}
return best;
}
}class Solution:
def findMinDifference(self, timePoints: List[str]) -> int:
m = [int(t[:2]) * 60 + int(t[3:]) for t in timePoints]
n = len(m)
best = 1440
for i in range(n):
for j in range(i + 1, n):
d = abs(m[i] - m[j])
best = min(best, d, 1440 - d)
return bestclass Solution {
public:
int findMinDifference(vector<string>& timePoints) {
int n = timePoints.size();
vector<int> m(n);
for (int i = 0; i < n; i++) {
const string& t = timePoints[i];
m[i] = stoi(t.substr(0, 2)) * 60 + stoi(t.substr(3));
}
int best = 1440;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
int d = abs(m[i] - m[j]);
best = min(best, min(d, 1440 - d));
}
}
return best;
}
};function findMinDifference(timePoints) {
const m = timePoints.map((t) => Number(t.slice(0, 2)) * 60 + Number(t.slice(3)));
let best = 1440;
for (let i = 0; i < m.length; i++) {
for (let j = i + 1; j < m.length; j++) {
const d = Math.abs(m[i] - m[j]);
best = Math.min(best, d, 1440 - d);
}
}
return best;
}2Better (sort minutes)
O(n log n)Sorting dominates; the scan is linear.O(n)The array of minutes.Sort the minute values. On a sorted circle, the closest pair must be neighbours, so check each adjacent difference plus the wrap-around gap from the last time to the first time of the next day.
- Convert every time to minutes and sort.
- best = min over i of m[i] - m[i - 1].
- Also consider m[0] + 1440 - m[n - 1] (the wrap past midnight).
- Return best.
class Solution {
public int findMinDifference(List<String> timePoints) {
int n = timePoints.size();
int[] m = new int[n];
for (int i = 0; i < n; i++) {
String t = timePoints.get(i);
m[i] = Integer.parseInt(t.substring(0, 2)) * 60 + Integer.parseInt(t.substring(3));
}
Arrays.sort(m);
int best = m[0] + 1440 - m[n - 1];
for (int i = 1; i < n; i++) best = Math.min(best, m[i] - m[i - 1]);
return best;
}
}class Solution:
def findMinDifference(self, timePoints: List[str]) -> int:
m = sorted(int(t[:2]) * 60 + int(t[3:]) for t in timePoints)
best = m[0] + 1440 - m[-1]
for i in range(1, len(m)):
best = min(best, m[i] - m[i - 1])
return bestclass Solution {
public:
int findMinDifference(vector<string>& timePoints) {
int n = timePoints.size();
vector<int> m(n);
for (int i = 0; i < n; i++) {
const string& t = timePoints[i];
m[i] = stoi(t.substr(0, 2)) * 60 + stoi(t.substr(3));
}
sort(m.begin(), m.end());
int best = m[0] + 1440 - m[n - 1];
for (int i = 1; i < n; i++) best = min(best, m[i] - m[i - 1]);
return best;
}
};function findMinDifference(timePoints) {
const m = timePoints.map((t) => Number(t.slice(0, 2)) * 60 + Number(t.slice(3)));
m.sort((a, b) => a - b);
let best = m[0] + 1440 - m[m.length - 1];
for (let i = 1; i < m.length; i++) best = Math.min(best, m[i] - m[i - 1]);
return best;
}3Optimal (minute buckets)
O(n + 1440)One pass over the input and one pass over the fixed-size array; no sorting.O(1440)A boolean array of 1440 slots, independent of n.A day has only 1440 minutes. Mark each minute in a boolean array; if a minute is marked twice the answer is 0 (and with more than 1440 entries a repeat is guaranteed). Then walk the 1440 slots in order, measuring the gap between consecutive marked minutes and the wrap-around gap from the last to the first.
- If n > 1440, return 0.
- For each time, compute its minute; if seen[minute] is already true return 0, else set it.
- Scan minutes 0..1439, tracking first, prev and the smallest gap between consecutive marked minutes.
- Return min(best, first + 1440 - prev).
class Solution {
public int findMinDifference(List<String> timePoints) {
if (timePoints.size() > 1440) return 0;
boolean[] seen = new boolean[1440];
for (String t : timePoints) {
int m = Integer.parseInt(t.substring(0, 2)) * 60 + Integer.parseInt(t.substring(3));
if (seen[m]) return 0;
seen[m] = true;
}
int first = -1, prev = -1, best = 1440;
for (int m = 0; m < 1440; m++) {
if (!seen[m]) continue;
if (first == -1) first = m;
else best = Math.min(best, m - prev);
prev = m;
}
return Math.min(best, first + 1440 - prev);
}
}class Solution:
def findMinDifference(self, timePoints: List[str]) -> int:
if len(timePoints) > 1440:
return 0
seen = [False] * 1440
for t in timePoints:
m = int(t[:2]) * 60 + int(t[3:])
if seen[m]:
return 0
seen[m] = True
first = prev = -1
best = 1440
for m in range(1440):
if not seen[m]:
continue
if first == -1:
first = m
else:
best = min(best, m - prev)
prev = m
return min(best, first + 1440 - prev)class Solution {
public:
int findMinDifference(vector<string>& timePoints) {
if (timePoints.size() > 1440) return 0;
vector<bool> seen(1440, false);
for (const string& t : timePoints) {
int m = stoi(t.substr(0, 2)) * 60 + stoi(t.substr(3));
if (seen[m]) return 0;
seen[m] = true;
}
int first = -1, prev = -1, best = 1440;
for (int m = 0; m < 1440; m++) {
if (!seen[m]) continue;
if (first == -1) first = m;
else best = min(best, m - prev);
prev = m;
}
return min(best, first + 1440 - prev);
}
};function findMinDifference(timePoints) {
if (timePoints.length > 1440) return 0;
const seen = new Array(1440).fill(false);
for (const t of timePoints) {
const m = Number(t.slice(0, 2)) * 60 + Number(t.slice(3));
if (seen[m]) return 0;
seen[m] = true;
}
let first = -1, prev = -1, best = 1440;
for (let m = 0; m < 1440; m++) {
if (!seen[m]) continue;
if (first === -1) first = m;
else best = Math.min(best, m - prev);
prev = m;
}
return Math.min(best, first + 1440 - prev);
}Edge cases to test
- Duplicate times (answer 0)
- The closest pair wraps around midnight
- Exactly two time points
- More than 1440 entries, which forces a duplicate
Hints
Hint 1
Convert every time to minutes since midnight. The gap between a and b on a 24-hour clock is min(|a - b|, 1440 - |a - b|).
Hint 2
After sorting, the closest pair is always next to each other, except for the pair (last, first) that wraps past midnight.
Hint 3
There are only 1440 possible minutes, so you can mark them in a boolean array instead of sorting.
FAQ
What is the best time complexity for Minimum Time Difference?
Optimal (minute buckets) runs in O(n + 1440) time and O(1440) extra space. One pass over the input and one pass over the fixed-size array; no sorting.
Which pattern does Minimum Time Difference use?
It is a arrays & hashing problem that uses the sorting pattern.
Is there a brute force solution for Minimum Time Difference?
Yes. Brute force (compare every pair) takes O(n²) time and O(n) space. Convert each time to minutes and compute the circular difference of every pair, keeping the smallest.
Which edge cases should I test for Minimum Time Difference?
Duplicate times (answer 0); The closest pair wraps around midnight; Exactly two time points; More than 1440 entries, which forces a duplicate.