Largest Time for Given Digits

Problem Description

Given an array arr of 4 digits, find the latest 24-hour time that can be made using each digit exactly once. Return the latest 24-hour time in "HH:MM" format. If no valid time can be made, return an empty string.

Key Insights

• A valid time in 24-hour format must have hours (HH) between 00 and 23, and minutes (MM) between 00 and 59.
• All permutations of the 4 digits need to be generated to find possible valid times.
• The latest valid time can be determined by comparing valid times generated from the permutations.

Space and Time Complexity

Time Complexity: O(1) - There are a fixed number of permutations (4!) to check, which is constant. Space Complexity: O(1) - The space used is for storing the valid times, which is also constant due to the fixed size.

Solution

To solve this problem, we can use the following approach:

1. Generate all permutations of the 4 digits.
2. For each permutation, construct a time in the format "HH:MM".
3. Check if the constructed time is valid based on the conditions for hours and minutes.
4. Keep track of the maximum valid time found.
5. Return the maximum valid time or an empty string if no valid time was found.

The algorithm primarily relies on generating permutations and validating the time format, ensuring that we explore all possible combinations of the digits.

Code Solutions