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.
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); }}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.