Largest Time for Given Digits

Problem Statement

The problem presents an array arr containing exactly four integer digits. The task is to construct the latest possible valid time in a 24-hour format using each of these digits exactly once. The 24-hour time format is structured as "HH:MM", where "HH" represents the hour and must be between 00 and 23, and "MM" represents the minutes and must be between 00 and 59. The solution should return this time as a string in the format "HH:MM". If it is impossible to construct a valid time from the digits provided, the function should return an empty string. This entails a careful permutation of the available digits to maximize the hour and minutes within their respective limits.

Examples

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 == 4
• 0 <= arr[i] <= 9

Approach and Intuition

To determine the latest possible time, we can adopt the following approach:

1. Generate all possible permutations of the array arr.
2. Validate each permutation by fitting it into the time format "HH:MM" to ensure the hours are between 00 and 23 and the minutes are between 00 and 59.
3. Track and update the maximum valid time found during this permutation check.
4. If no valid time is identified during the permuations, return an empty string. Otherwise, return the maximum time found.

Intuition

• The need to generate permutations ensures that we evaluate every possible combination of the digits, ensuring the latest possible time isn't missed.
• Validating each permutation against the time constraints (00 to 23 for hours and 00 to 59 for minutes) ensures only feasible times are considered.
• By always updating the maximum time found during the evaluation, we ensure the result reflects the latest time possible.

With this approach, despite its brute force nature due to the limited size of the input (only 24 permutations), we can efficiently find the correct and latest time according to the given constraints.

Solutions

class Solution {
    private int maxTime = -1;
    
    public String calculateLargestTime(int[] digits) {
        maxTime = -1;
        generatePermutations(digits, 0);
        if (maxTime == -1)
            return "";
        else
            return String.format("%02d:%02d", maxTime / 60, maxTime % 60);
    }
    
    protected void generatePermutations(int[] digits, int index) {
        if (index == digits.length) {
            evaluateTime(digits);
            return;
        }
        for (int idx = index; idx < digits.length; ++idx) {
            exchange(digits, idx, index);
            generatePermutations(digits, index + 1);
            exchange(digits, idx, index);
        }
    }
    
    protected void evaluateTime(int[] permutation) {
        int hours = permutation[0] * 10 + permutation[1];
        int minutes = permutation[2] * 10 + permutation[3];
        if (hours < 24 && minutes < 60)
            maxTime = Math.max(maxTime, hours * 60 + minutes);
    }
    
    protected void exchange(int[] array, int x, int y) {
        if (x != y) {
            int temporary = array[x];
            array[x] = array[y];
            array[y] = temporary;
        }
    }
}