Problem Description
Given an array of 4 digits, determine the largest possible 24-hour time (formatted as "HH:MM") that can be constructed using each digit exactly once. The hours "HH" must lie between 00 and 23 and the minutes "MM" between 00 and 59. If no valid time can be formed, return an empty string.
Key Insights
- Generate all permutations of the 4 digits since the array is small.
- Construct hours and minutes from each permutation and validate if they form a correct time.
- Track the maximum valid time by comparing the numerical values.
- Return the result in "HH:MM" format or an empty string if none exists.
Space and Time Complexity
Time Complexity: O(1) since the input size is fixed at 4 digits leading to 4! = 24 permutations. Space Complexity: O(1) extra space used for storing permutations and intermediate variables.
Solution
We use a brute-force permutation approach by generating all possible orders of the four digits. For each permutation, the first two digits form the hour and the last two digits form the minute. We validate if the hour is between 0 and 23 and the minute is between 0 and 59. We convert these validations into a numerical comparison (e.g., hour * 60 + minute) to easily determine the largest time. This method uses simple arithmetic and string manipulation and is efficient due to the very limited number of permutations. Edge cases where no valid time exists result in returning an empty string.