Problem Description

Given an array A of four digits, return the largest 24-hour time that can be made. The time should be returned as a string in the format "HH:MM". If no valid time can be made, return an empty string.

• Each digit in A must be used exactly once.
• The time must be valid in 24-hour format: 00:00 to 23:59.
• If multiple valid times can be made, return the largest one.
• If it is impossible to make a valid time, return "" (empty string).

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

Thought Process

To solve this problem, we need to arrange the four digits into a valid time in HH:MM format, making sure that the hour is between 00 and 23, and the minute is between 00 and 59. We must use each digit exactly once.

The brute-force way is to try every possible ordering (permutation) of the four digits and check if it forms a valid time. Since there are only 24 permutations (4!), this is feasible. For each permutation, we can check if the first two digits form a valid hour and the last two a valid minute.

After checking all possibilities, we should keep track of the largest valid time found. The problem is not about efficiency but about correctness and careful validation.

There is little room for optimization since the input size is so small, but we should make sure our validation logic is correct and that we always return the largest time.

Solution Approach

Let's break down the approach step-by-step:

1. Generate all possible permutations:
   • There are 4 digits, so we generate all 24 possible ways to order them.
2. Check each permutation for validity:
   • Take the first two digits as the hour (HH), and the last two as the minute (MM).
   • Check if 0 <= HH < 24 and 0 <= MM < 60.
3. Track the largest valid time:
   • For each valid time, compare it to the largest found so far (convert HH and MM to minutes since midnight for easy comparison).
   • If it's larger, update our record.
4. Return the result:
   • Format the largest valid time as a string "HH:MM" with leading zeros if necessary.
   • If no valid time is found, return an empty string.

This approach is simple and effective due to the small input size.

Example Walkthrough

Let's walk through the example A = [1,2,3,4]:

1. Generate all permutations of [1,2,3,4]. For example:
   • [1, 2, 3, 4] → 12:34
   • [2, 3, 1, 4] → 23:14
   • [2, 4, 3, 1] → 24:31 (invalid hour)
   • [3, 4, 2, 1] → 34:21 (invalid hour)
2. For each permutation, check if the hour is between 0 and 23 and the minute between 0 and 59.
3. Valid times from all permutations:
   • 12:34
   • 12:43
   • 13:24
   • 13:42
   • 14:23
   • 14:32
   • 21:34
   • 21:43
   • 23:14
   • 23:41
4. The largest valid time is 23:41.
5. Return "23:41".

Time and Space Complexity

Brute-force Approach:

• There are 4! = 24 permutations to check.
• For each permutation, we do constant-time work (checking validity and comparing times).
• Time Complexity: O(1) (since 24 is a constant, this is effectively constant time).
• Space Complexity: O(1) (we only use a fixed number of variables for tracking the best time).

• Since the input size is fixed and small, there is no meaningful optimization beyond brute-force.
• All approaches will be O(1) time and space for this problem.

Summary

The problem asks us to find the largest valid 24-hour time from four digits, using each digit exactly once. The key insight is that the number of possible arrangements is so small that we can simply check every permutation. For each, we validate the time and track the largest. This brute-force approach is both simple and effective, and ensures correctness by exhaustively checking all options.

Code Implementation

from itertools import permutations

class Solution:
    def largestTimeFromDigits(self, A):
        max_time = -1
        for perm in permutations(A):
            h1, h2, m1, m2 = perm
            hour = h1 * 10 + h2
            minute = m1 * 10 + m2
            if 0 <= hour < 24 and 0 <= minute < 60:
                total = hour * 60 + minute
                if total > max_time:
                    max_time = total
        if max_time == -1:
            return ""
        else:
            hour = max_time // 60
            minute = max_time % 60
            return "{:02d}:{:02d}".format(hour, minute)
      

#include <vector>
#include <string>
#include <algorithm>
using namespace std;

class Solution {
public:
    string largestTimeFromDigits(vector<int>& A) {
        string res = "";
        int max_time = -1;
        sort(A.begin(), A.end());
        do {
            int hour = A[0] * 10 + A[1];
            int minute = A[2] * 10 + A[3];
            if (hour >= 0 && hour < 24 && minute >= 0 && minute < 60) {
                int total = hour * 60 + minute;
                if (total > max_time) {
                    max_time = total;
                    char buffer[6];
                    sprintf(buffer, "%02d:%02d", hour, minute);
                    res = buffer;
                }
            }
        } while (next_permutation(A.begin(), A.end()));
        return res;
    }
};
      

import java.util.*;

class Solution {
    public String largestTimeFromDigits(int[] A) {
        int max = -1;
        String res = "";
        List<Integer> list = new ArrayList<>();
        for (int a : A) list.add(a);
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 4; j++) {
                if (j == i) continue;
                for (int k = 0; k < 4; k++) {
                    if (k == i || k == j) continue;
                    int l = 6 - i - j - k;
                    int hour = list.get(i) * 10 + list.get(j);
                    int minute = list.get(k) * 10 + list.get(l);
                    if (hour < 24 && minute < 60) {
                        int total = hour * 60 + minute;
                        if (total > max) {
                            max = total;
                            res = String.format("%02d:%02d", hour, minute);
                        }
                    }
                }
            }
        }
        return res;
    }
}
      

function largestTimeFromDigits(A) {
    let max = -1, res = "";
    function permute(arr, l) {
        if (l === arr.length) {
            let hour = arr[0] * 10 + arr[1];
            let minute = arr[2] * 10 + arr[3];
            if (hour >= 0 && hour < 24 && minute >= 0 && minute < 60) {
                let total = hour * 60 + minute;
                if (total > max) {
                    max = total;
                    res = ("0" + hour).slice(-2) + ":" + ("0" + minute).slice(-2);
                }
            }
            return;
        }
        for (let i = l; i < arr.length; i++) {
            [arr[l], arr[i]] = [arr[i], arr[l]];
            permute(arr, l + 1);
            [arr[l], arr[i]] = [arr[i], arr[l]];
        }
    }
    permute(A, 0);
    return res;
}