You are given an array of exactly four digits (each between 0 and 9). Your task:

Construct the largest valid 24-hour time in the format "HH:MM" using all four digits exactly once.

If it is not possible to form any valid time, return:

""

Examples:

Input: [1,2,3,4]
Output: "23:41"

Input: [5,5,5,5]
Output: ""

---

Problem Understanding

A valid 24-hour time must satisfy:

00 ≤ HH ≤ 23
00 ≤ MM ≤ 59

Because digits must be reused exactly once:

• We cannot fabricate digits
• Order matters
• We must try different permutations

Key constraints:

• Only 4 digits → total permutations = 4! = 24
• Very small search space → brute force is acceptable

The challenge is:

among all valid permutations, return the one representing the latest possible time.

---

Logic Explained in Simple English

The simplest way to solve this:

1. Generate all possible permutations of the 4 digits.
2. For each permutation:
   • Convert first two digits into hours
   • Convert last two digits into minutes
3. Check if hours and minutes form a valid time
4. Track the maximum valid time found
5. Return it formatted as "HH:MM"

Why brute force works?

• Only 24 permutations → extremely fast
• Avoids tricky conditional pruning

Alternative thinking:

Instead of generating times and checking validity, you could choose digits greedily — but greedy fails in several edge cases. Brute force avoids logical pitfalls.

---

Step-by-Step Approach

1. Use recursion or iteration to generate all permutations
2. For each permutation d0, d1, d2, d3:
   • hour = d0*10 + d1
   • minute = d2*10 + d3
3. Check: hour < 24 and minute < 60
4. Convert total time into minutes: total = hour * 60 + minute
5. Track the permutation with the highest total
6. If none valid → return empty string
7. Otherwise format result properly with leading zeroes

---

Java Implementation

class Solution {
    public String largestTimeFromDigits(int[] arr) {
        List<List<Integer>> perms = new ArrayList<>();
        permute(arr, 0, perms);

        int maxTime = -1;
        int bestH = 0, bestM = 0;

        for (List<Integer> p : perms) {
            int hour = p.get(0) * 10 + p.get(1);
            int minute = p.get(2) * 10 + p.get(3);

            if (hour < 24 && minute < 60) {
                int total = hour * 60 + minute;
                if (total > maxTime) {
                    maxTime = total;
                    bestH = hour;
                    bestM = minute;
                }
            }
        }

        if (maxTime == -1) {
            return "";
        }

        return String.format("%02d:%02d", bestH, bestM);
    }

    private void permute(int[] arr, int start, List<List<Integer>> result) {
        if (start == arr.length) {
            List<Integer> temp = new ArrayList<>();
            for (int num : arr) temp.add(num);
            result.add(temp);
            return;
        }

        for (int i = start; i < arr.length; i++) {
            swap(arr, start, i);
            permute(arr, start + 1, result);
            swap(arr, start, i);
        }
    }

    private void swap(int[] arr, int i, int j) {
        int t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }
}

---

Dry Run Example

Input:

[1, 2, 3, 4]

Permutations evaluated (showing only valid ones):

12:34
12:43
13:24
13:42
14:23
14:32
21:34
21:43
23:14
23:41   <-- largest

Maximum time found:

23:41

Output:

"23:41"

---

Time and Space Complexity

Time Complexity

O(1)

Why?

• Maximum permutations = 24
• Constant upper bound regardless of input values

Space Complexity

O(1)

Aside from storing permutations, which is also constant-bound.

---

Common Mistakes and How to Avoid Them

Mistake 1: Trying greedy digit selection

Fails on cases like:

[2,3,5,9]

Greedy may pick 2 first, but best is 23:59.

Mistake 2: Forgetting leading zero formatting

Must output "01:09", not "1:9".

Mistake 3: Treating any 2 digits as hour

Hours must be < 24

Mistake 4: Treating any 2 digits as minute

Minutes must be < 60

Mistake 5: Returning first valid instead of largest

Must compare and track max.