Sponsored
Sponsored
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.
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.