Leetcode 949. Largest Time for Given Digits

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.

URL: [https://leetcode.com/problems/largest-time-for-given-digits/)

My answer:

This question is really asking which permutations of the 4 digit number can be valid times. Of those valid times, which one is the maximum value. The difficult part of the problem is to generate the permutations. The algorithm used for this involves swapping the initial index with target index and recursively solving the rest of the array. Afterwards, the initial index and target index values are swapped again and a new target index is is chosen to be swapped and the algorithm repeats. An explanation of the code is below.

My solution:

class Solution {
    private int maxTime;
    
    public String largestTimeFromDigits(int[] arr) {
        this.maxTime = -1;
        this.permute(arr,0);
        if (this.maxTime == -1) {
            return "";
        }
        return String.format("%02d:%02d",this.maxTime / 60,this.maxTime % 60);
    }
    
    private void swap(int[] arr, int i, int j) {
        if (i == j) {
            return;
        }
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
    
    private void permute(int[] arr, int i) {
        int n = arr.length;
        if (i == n) {
            this.calcTime(arr);
            return;
        }
        for (int idx = i; idx < n; idx++) {
            
            this.swap(arr,i,idx);
            this.permute(arr,i+1);
            this.swap(arr,i, idx);
            
        }
    }
    
    private void calcTime(int[] arr) {
        int hour = arr[0]*10 + arr[1];
        if (hour > 23) {
            return;
        }
        int minute = arr[2] * 10 + arr[3];
        if (minute > 59) {
            return;
        }
        int time = hour * 60 + minute;
        this.maxTime = Math.max(this.maxTime, time);
    }
}

Explanation: Lines 2 and 5 declare and initialize the maximum time to -1 so that the first time is guaranteed to be stored.

Line 6 calls the permute function which will generate each permutation and calls a procedure to verify and store the maximum time seen so far.

Line 22 is the permute function. The function takes an array and a starting index(i) as arguments. function is called with i = 0 initially.

Line 24 is the base case of the algorithm. When the starting index is out of bounds, arr is a completed permutation and the calcTime function is called.

Line 28 is the main loop for the algorithm. This loop swaps the value index i with the value at index idx.

Line 37 is the calcTime function. The function first verifies if the minute and hour are valid, then it calculates the time in minutes and stores the maximum time seen so far in maxTime.

Line 30 calls the swap procedure.

Line 31 recursively calls the permute function for the rest of the array.

Line 32 resets the positions from the swap on Line 30. idx now points to the next index which will be swapped with the initial position and the algorithm repeats until there are no more values to swap. Once the loop finishes, all n-1-i swaps have occured.