Largest Time for Given Digits — Problem & Solution
Largest Time for Given Digits solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Largest Time for Given Digits is a medium coding problem on arrays, strings and enumeration, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Arrays, Strings, Enumeration
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given four digits in arr. Using each digit exactly once, form a 24-hour time "HH:MM", where HH is between 00 and 23 and MM is between 00 and 59.
Return the latest valid time you can form, as a string of the form "HH:MM". If no valid time can be formed, return the empty string.
Example 1
Input: arr = [2,0,6,6]
Output: 06:26
Explanation: Any hour starting with 2 would need two digits from {0, 6, 6} for minutes, and 66 is too large.
Example 2
Input: arr = [1,9,4,7]
Output: 19:47
Example 3
Input: arr = [5,5,5,5]
Output:
Explanation: 55 is not an hour, so nothing is valid (the expected output is an empty line).
Constraints
arr.length == 40 <= arr[i] <= 9
Hints for Largest Time for Given Digits
Hint 1
There are only
4! = 24ways to order four digits.Hint 2
For each ordering, the first two digits form the hour and the last two the minutes; keep it if the hour is below 24 and the minutes below 60.
Hint 3
Compare candidates by
hour * 60 + minutesand format the best one with leading zeros.
How to solve Largest Time for Given Digits
With four digits there are 24 orderings — try them all, keep the valid ones, and pick the latest.
Approach
- Loop over every choice of distinct positions
i, j, kfor the hour's tens, the hour's ones and the minutes' tens; the remaining positionl = 6 - i - j - kis the minutes' ones. - Let
h = 10·arr[i] + arr[j]andm = 10·arr[k] + arr[l]. Skip unlessh < 24andm < 60. - Track the largest
h * 60 + m. - If nothing was valid return
""; otherwise format it as"HH:MM"with leading zeros.
Why it works
Every assignment of the four digits to the four time positions is one of the 24 orderings, and comparing minutes since midnight orders times correctly.
Complexity
- Time —
O(1) — 24 candidates - Space —
O(1)
Pitfalls
- Greedily taking the largest digit first fails: for
[2,0,6,6]an hour of2xleaves66for the minutes. - Keep the leading zeros:
6:26must be written06:26. 00:00is a valid answer, distinct from the empty string.
Reference solution
Python
from typing import List
from itertools import permutations
def largestTimeFromDigits(arr: List[int]) -> str:
best = -1
for a, b, c, d in permutations(arr):
h, m = a * 10 + b, c * 10 + d
if h < 24 and m < 60:
best = max(best, h * 60 + m)
if best < 0:
return ""
return "%02d:%02d" % (best // 60, best % 60)Java
public static String largestTimeFromDigits(int[] arr) {
int best = -1;
for (int i = 0; i < 4; i++)
for (int j = 0; j < 4; j++)
for (int k = 0; k < 4; k++) {
if (i == j || j == k || i == k) continue;
int l = 6 - i - j - k;
int h = arr[i] * 10 + arr[j], m = arr[k] * 10 + arr[l];
if (h < 24 && m < 60) best = Math.max(best, h * 60 + m);
}
if (best < 0) return "";
return String.format("%02d:%02d", best / 60, best % 60);
}C++
string largestTimeFromDigits(vector<int>& arr) {
int best = -1;
for (int i = 0; i < 4; i++)
for (int j = 0; j < 4; j++)
for (int k = 0; k < 4; k++) {
if (i == j || j == k || i == k) continue;
int l = 6 - i - j - k;
int h = arr[i] * 10 + arr[j], m = arr[k] * 10 + arr[l];
if (h < 24 && m < 60) best = max(best, h * 60 + m);
}
if (best < 0) return "";
char buf[8];
snprintf(buf, sizeof(buf), "%02d:%02d", best / 60, best % 60);
return string(buf);
}JavaScript
var largestTimeFromDigits = function(arr) {
var best = -1;
for (var i = 0; i < 4; i++) {
for (var j = 0; j < 4; j++) {
for (var k = 0; k < 4; k++) {
if (i === j || j === k || i === k) continue;
var l = 6 - i - j - k;
var h = arr[i] * 10 + arr[j], m = arr[k] * 10 + arr[l];
if (h < 24 && m < 60 && h * 60 + m > best) best = h * 60 + m;
}
}
}
if (best < 0) return "";
var hh = Math.floor(best / 60), mm = best % 60;
return (hh < 10 ? "0" : "") + hh + ":" + (mm < 10 ? "0" : "") + mm;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.