Largest Time for Given Digits
MedPrompt
Given an array arr of 4 digits, find the latest 24-hour time that can be made using each digit exactly once.
24-hour times are formatted as "HH:MM", where HH is between 00 and 23, and MM is between 00 and 59. The earliest 24-hour time is 00:00, and the latest is 23:59.
Return the latest 24-hour time in "HH:MM" format. If no valid time can be made, return an empty string.
Example 1:
Input: arr = [1,2,3,4]
Output: "23:41"
Explanation: The valid 24-hour times are "12:34", "12:43", "13:24", "13:42", "14:23", "14:32", "21:34", "21:43", "23:14", and "23:41". Of these times, "23:41" is the latest.Example 2:
Input: arr = [5,5,5,5]
Output: ""
Explanation: There are no valid 24-hour times as "55:55" is not valid.
Constraints:
arr.length == 40 <= arr[i] <= 9
Approaches
2 approaches with complexity analysis and trade-offs.
This approach iterates through all possible 24-hour times, from the latest (23:59) to the earliest (00:00). For each time, it checks if the digits required to form that time can be constructed from the given input digits. The first valid time found is guaranteed to be the latest possible one because of the descending order of iteration.
Algorithm
- Create a frequency count (e.g., an array of size 10) of the digits in the input array
arr. - Loop for hours
hfrom 23 down to 0. - Inside the hour loop, loop for minutes
mfrom 59 down to 0. - For the current time
h:m, determine the four digits required:d1 = h/10,d2 = h%10,d3 = m/10,d4 = m%10. - Create a frequency count of these four required digits.
- Compare the frequency count of the required digits with the frequency count of the input
arr. - If the counts match, it means this time can be formed. Since we are iterating downwards from the latest possible time, this is our answer. Format the time as
String.format("%02d:%02d", h, m)and return it. - If the loops complete without finding any match, it means no valid time can be constructed. Return an empty string
"".
Walkthrough
The algorithm iterates through hours from 23 down to 0, and for each hour, it iterates through minutes from 59 down to 0. For a given time HH:MM, we determine the four digits required: H/10, H%10, M/10, and M%10. We then check if this set of four digits is a permutation of the input arr. This check can be done efficiently by using frequency counts. We first create a frequency map (or an array of size 10) for the digits in the input arr. Then, for the current time HH:MM, we create a frequency map of its constituent digits. If the two frequency maps are identical, it means we can form this time. Since we are iterating downwards, this is the latest possible time. We format it as "HH:MM" and return. If the loops complete without finding a match, it means no valid time can be formed, so we return an empty string.
import java.util.Arrays; class Solution { public String largestTimeFromDigits(int[] arr) { int[] counts = new int[10]; for (int digit : arr) { counts[digit]++; } for (int h = 23; h >= 0; h--) { for (int m = 59; m >= 0; m--) { int[] requiredCounts = new int[10]; requiredCounts[h / 10]++; requiredCounts[h % 10]++; requiredCounts[m / 10]++; requiredCounts[m % 10]++; if (Arrays.equals(counts, requiredCounts)) { return String.format("%02d:%02d", h, m); } } } return ""; }}Complexity
Time
O(1). The loops run a fixed number of times (24 * 60 = 1440). Inside the loop, the operations (creating and comparing frequency arrays) take constant time.
Space
O(1). We use a constant amount of extra space for the frequency arrays (e.g., an integer array of size 10).
Trade-offs
Pros
Simple to understand and implement.
Correctly finds the latest time by its nature of iterating downwards.
Cons
Performs a relatively large number of checks (up to 24 * 60 = 1440), which is less efficient than exploring the small search space of permutations of the input digits.
Since the input is a small, fixed-size array of 4 digits, we can generate all possible arrangements (permutations) of these digits. There are 4! = 24 such permutations. For each permutation, we form a time and check if it's valid. We keep track of the latest valid time found across all permutations.
Algorithm
- Initialize a variable
maxTimeto -1 to store the maximum time found so far, represented in total minutes from midnight. - Generate all permutations of the input
arr. A simple way is to use four nested loops with indicesi, j, k, lfrom 0 to 3, ensuringi, j, k, lare all distinct. - For each permutation
(arr[i], arr[j], arr[k], arr[l]):- Form hours
h = arr[i] * 10 + arr[j]. - Form minutes
m = arr[k] * 10 + arr[l]. - Check if the time is valid:
h < 24andm < 60. - If valid, update
maxTime = max(maxTime, h * 60 + m).
- Form hours
- After checking all permutations, if
maxTimeis still -1, no valid time was found, so return"". - Otherwise, convert
maxTimeback to"HH:MM"format and return it.HH = maxTime / 60,MM = maxTime % 60.
Walkthrough
The core of this approach is to generate all 24 permutations of the input array arr. This can be done using four nested loops or a recursive backtracking algorithm. For each permutation, say [d1, d2, d3, d4], we construct the hours HH = d1 * 10 + d2 and minutes MM = d3 * 10 + d4. We then validate this time: HH must be in the range [0, 23] and MM must be in the range [0, 59]. If the time is valid, we compare it with the latest valid time found so far. We can store the time as a string "HH:MM" and use string comparison, or as an integer representing the total minutes (HH * 60 + MM) for easier comparison. We initialize our "best time" to a sentinel value (e.g., an empty string). After checking all 24 permutations, if we have found a valid time, we format and return it. Otherwise, we return an empty string.
class Solution { public String largestTimeFromDigits(int[] arr) { String result = ""; // Iterate through all 4! = 24 permutations for (int i = 0; i < 4; i++) { for (int j = 0; j < 4; j++) { if (j == i) continue; for (int k = 0; k < 4; k++) { if (k == i || k == j) continue; // The last index l is the one not used yet. // The sum of indices 0,1,2,3 is 6. So l = 6 - i - j - k. int l = 6 - i - j - k; int h = arr[i] * 10 + arr[j]; int m = arr[k] * 10 + arr[l]; if (h < 24 && m < 60) { String currentTime = String.format("%02d:%02d", h, m); if (result.isEmpty() || currentTime.compareTo(result) > 0) { result = currentTime; } } } } } return result; }}Complexity
Time
O(1). The number of permutations is fixed at 4! = 24. For each permutation, we perform a constant number of operations. Thus, the complexity is constant.
Space
O(1). We only use a few variables to store the current permutation and the best time found so far.
Trade-offs
Pros
Very efficient as it explores the minimal search space of 24 possibilities.
Conceptually straightforward for a fixed small number of items.
Cons
The implementation with nested loops can look a bit verbose. A recursive permutation generator might be cleaner but adds recursion overhead.
This approach does not scale well if the number of digits were larger (e.g., for
ndigits, it would be O(n!)). However, for this problem's constraints, it's perfect.
Solutions
Solution
class Solution {public String largestTimeFromDigits(int[] arr) { int ans = -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) { int h = arr[i] * 10 + arr[j]; int m = arr[k] * 10 + arr[6 - i - j - k]; if (h < 24 && m < 60) { ans = Math.max(ans, h * 60 + m); } } } } } return ans < 0 ? "" : String.format("%02d:%02d", ans / 60, ans % 60); }}class Solution {public: string largestTimeFromDigits(vector<int> &arr) { int ans = -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) { int h = arr[i] * 10 + arr[j]; int m = arr[k] * 10 + arr[6 - i - j - k]; if (h < 24 && m < 60) { ans = max(ans, h * 60 + m); } } } } } if (ans < 0) return ""; int h = ans / 60, m = ans % 60; return to_string(h / 10) + to_string(h % 10) + ":" + to_string(m / 10) + to_string(m % 10); }};class Solution: def largestTimeFromDigits(self, arr: List[int]) -> str: ans = - 1 for i in range(4): for j in range(4): for k in range(4): if i != j and i != k and j != k: h = arr[i] * 10 + arr[j] m = arr[k] * 10 + arr[6 - i - j - k] if h < 24 and m < 60: ans = max(ans, h * 60 + m) return '' if ans < 0 else f ' { ans // 60 : 02 } : { ans % 60 : 02 } 'Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.