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] <= 9In #949 Largest Time for Given Digits, you are given four digits and must arrange them to form the largest possible valid 24-hour time in the format HH:MM. Since there are only four digits, the key idea is to explore all possible permutations of these digits and check which arrangements produce a valid time.
A practical strategy is to generate all permutations of the four digits and treat the first two digits as the hour and the last two as the minutes. For each permutation, verify whether the hour is less than 24 and the minutes are less than 60. Among all valid combinations, track the one that represents the maximum time. Converting the time into total minutes or comparing lexicographically can help determine the largest valid result.
Because the number of digits is fixed, the total permutations are limited. This makes a brute-force enumeration approach both simple and efficient. The algorithm runs in constant time due to the small input size and requires minimal extra space.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Permutation / Enumeration of all digit arrangements | O(1) (at most 4! permutations) | O(1) |
Knowledge Center
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.
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).
1from itertools import permutations
2
3def largestTimeFromDigits(arr):
4 max_time = -1
5 # permutations generates all possible arrangements of the list
6 for perm in permutations(arr):
7 h1, h2, m1, m2 = perm
8 hours = h1 * 10 + h2
9 minutes = m1 * 10 + m2
10 # Check if the hours and minutes form a valid time
11 if 0 <= hours < 24 and 0 <= minutes < 60:
12 max_time = max(max_time, hours * 60 + minutes)
13 if max_time == -1:
14 return ""
15 else:
16 return f"{max_time // 60:02}:{max_time % 60:02}"
17
18# Example Usage:
19# print(largestTimeFromDigits([1,2,3,4])) # Output: "23:41"
20This 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.
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.
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.
1def largestTimeFromDigits(arr):
2 arr.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, variations of this problem appear in coding interviews because it tests permutation generation, validation logic, and careful handling of constraints. It is commonly categorized as a medium-level problem involving arrays and enumeration.
The most effective approach is to generate all permutations of the four digits and check which combinations form valid 24-hour times. Among the valid times, keep track of the maximum one. Since there are only 24 permutations, this enumeration method is efficient and simple.
Arrays or simple lists are sufficient for this problem because the input size is fixed at four digits. Most solutions rely on permutation generation and basic integer comparisons rather than complex data structures.
After forming a permutation, treat the first two digits as the hour and the last two as the minutes. A valid time must satisfy hour < 24 and minute < 60. Only such combinations should be considered when determining the maximum time.
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.