Problem

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.

Examples

Example 1:

1
2
3

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:

1
2
3

Input: arr = [5,5,5,5]
Output: ""
Explanation: There are no valid 24-hour times as "55:55" is not valid.

Solution

Method 1 - Generate all permutations

To solve this problem, we need to find the latest valid 24-hour time that can be made using all four digits exactly once. We can achieve this through the following steps:

  1. Generate Permutations:
    • Generate all possible permutations of the four digits.
  2. Validate Time:
    • For each permutation, verify if it can represent a valid 24-hour time.
  3. Track Latest Time:
    • Keep track of the maximum time that meets the validation criteria in terms of hours and minutes.
  4. Return Result:
    • Format and return the maximum valid time we found. If none is valid, return an empty string.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

public class Solution {
    public String largestTimeFromDigits(int[] arr) {
        Arrays.sort(arr);
        String ans = "";
        for (int i = 3; i >= 0; i--) {
            for (int j = 3; j >= 0; j--) {
                if (j == i) continue;
                for (int k = 3; k >= 0; k--) {
                    if (k == i || k == j) continue;
                    int l = 6 - i - j - k;
                    int hours = arr[i] * 10 + arr[j];
                    int mins = arr[k] * 10 + arr[l];
                    if (hours < 24 && mins < 60) {
                        String time = String.format("%02d:%02d", hours, mins);
                        if (time.compareTo(ans) > 0) ans = time;
                    }
                }
            }
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution:
    def largestTimeFromDigits(self, arr: List[int]) -> str:
        max_time = -1
        
        # Generate all permutations of the array
        for perm in permutations(arr):
            h1, h2, m1, m2 = perm
            hours = h1 * 10 + h2
            minutes = m1 * 10 + m2
            
            if hours < 24 and minutes < 60:
                total_minutes = hours * 60 + minutes
                max_time = max(max_time, total_minutes)
        
        if max_time == -1:
            return ""
        
        return f"{max_time // 60:02d}:{max_time % 60:02d}"

Complexity

  • ⏰ Time complexity: O(1)
    • Generating permutations (n! where n is 4) leads to a time complexity of O(24) (since 4! = 24 permutations).
    • Validating each permutation takes constant time O(1).
    • Overall, the approach runs in constant time O(1).
  • 🧺 Space complexity: O(1)  for storing the permutations and the calculations.