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] <= 9Problem Overview: You get an array of four digits. Your goal is to arrange them into the largest possible valid 24‑hour time in HH:MM format. Hours must be between 00–23 and minutes between 00–59. If no valid time can be formed, return an empty string.
Approach 1: Brute Force with Permutations (Time: O(4!) ≈ O(1), Space: O(1))
The simplest strategy is to generate every possible ordering of the four digits. Since there are only 4! = 24 permutations, the search space is tiny. For each permutation, interpret the first two digits as the hour and the last two as the minute. Check validity using conditions like hour < 24 and minute < 60. Track the maximum valid time by converting each candidate into total minutes (hour * 60 + minute) and keeping the largest value. This approach relies on straightforward enumeration and works well because the input size is fixed.
Approach 2: Greedy Construction of Time (Time: O(1), Space: O(1))
A more interview‑friendly approach builds the time digit by digit while respecting constraints. Start by selecting the largest possible digit for the first hour position (H1) that does not exceed 2. Then choose the largest remaining digit for the second hour position (H2) based on whether H1 is 2 (limit becomes 3) or less than 2 (limit becomes 9). Continue similarly for the minute digits: the first minute digit must be ≤5 and the last digit can be anything remaining. This process treats the digits like a small multiset stored in an array. By always choosing the largest valid digit at each step, you construct the lexicographically largest valid time without testing every permutation.
Even though both approaches run in constant time due to the fixed input size, the greedy construction demonstrates stronger reasoning about constraints and digit placement. The brute force method proves correctness quickly, but the greedy method shows deeper understanding of how time formatting rules interact with digit choices. Both techniques involve simple digit manipulation and string formatting when producing the final HH:MM result.
Recommended for interviews: Start with the permutation approach to establish a correct baseline. The input size makes it perfectly acceptable and easy to implement. If the interviewer pushes for optimization or reasoning about constraints, transition to the greedy construction strategy, which demonstrates stronger problem‑solving skills and control over digit selection.
Generate all possible permutations of the given 4 digits and check each permutation to see if it forms a valid time in the 24-hour format. Maintain the latest valid time found during this process.
This Python solution uses the permutations function from the itertools module to generate all possible permutations of the digits. It checks each permutation to see if it forms a valid time, computing the hours and minutes separately with the first two and last two digits respectively. If it forms a valid time, it calculates its total minutes and compares it against the maximum found so far. Finally, it formats the maximum found time (if any) as 'HH:MM' for output or returns an empty string if no valid time was found.
Time Complexity: O(24), because there are 4! (24) permutations to check.
Space Complexity: O(1), additional space relative to input size is constant (ignores permutations' storage).
Sort the digits in descending order and attempt to form the largest possible hour and minute values by greedily assigning the largest permissible value to each time unit, reducing failures due to invalid hours or minutes promptly.
This Python solution iteratively attempts to create valid times by testing every potential hour and minute combination from the largest possible (23:59) down to (00:00). For each valid time, it reverse sorts and compares the formed digits with the sorted input array. If they match, it returns that time formatted as 'HH:MM'. The greedy reduction of the time possibilities prevents unnecessary permutations.
Time Complexity: O(1440) at maximum since it iterates through all minute combinations before valid time finding prematurely.
Space Complexity: O(1), as the only additional space use is from baselines and temporary variables.
| Approach | Complexity |
|---|---|
| Brute Force with Permutations | Time Complexity: O(24), because there are 4! (24) permutations to check. |
| Greedy Approach by Constructing Time | Time Complexity: O(1440) at maximum since it iterates through all minute combinations before valid time finding prematurely. |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force with Permutations | O(4!) ≈ O(1) | O(1) | Best for clarity and quick implementation since only 24 permutations exist |
| Greedy Construction of Time | O(1) | O(1) | Preferred in interviews when reasoning about constraints and digit placement |
Largest Time for Given Digits | LeetCode 949 | C++, Java, Python • Knowledge Center • 6,581 views views
Watch 9 more video solutions →Practice Largest Time for Given Digits with our built-in code editor and test cases.
Practice on FleetCode