Largest Time for Given Digits

medium permutation brute force enumeration

Problem

Given an array of exactly four digits (each 0–9), return the latest 24-hour time that can be formed using every digit once, in the format "HH:MM". The largest valid time is between 00:00 and 23:59. If no valid time can be made, return an empty string.

Inputarr = [1, 2, 3, 4]

Output"23:41"

Among all arrangements, 23:41 is the latest valid time; 23:14 is also valid but earlier.

arr (exactly 4 digits, comma-separated)

from itertools import permutations

def largest_time_from_digits(arr):
    best = -1
    for h1, h2, m1, m2 in permutations(arr):
        hour = h1 * 10 + h2
        minute = m1 * 10 + m2
        if hour < 24 and minute < 60:
            best = max(best, hour * 60 + minute)
    if best == -1:
        return ""
    return "{:02d}:{:02d}".format(best // 60, best % 60)

function largestTimeFromDigits(arr) {
  let best = -1;
  const perms = permutations(arr);
  for (const [h1, h2, m1, m2] of perms) {
    const hour = h1 * 10 + h2;
    const minute = m1 * 10 + m2;
    if (hour < 24 && minute < 60) {
      best = Math.max(best, hour * 60 + minute);
    }
  }
  if (best === -1) return "";
  const h = Math.floor(best / 60), m = best % 60;
  return String(h).padStart(2, "0") + ":" + String(m).padStart(2, "0");
}

class Solution {
    public String largestTimeFromDigits(int[] arr) {
        int best = -1;
        int[] p = {0, 1, 2, 3};
        for (int i = 0; i < 4; i++)
            for (int j = 0; j < 4; j++)
                for (int k = 0; k < 4; k++) {
                    if (i == j || j == k || i == k) continue;
                    int l = 6 - i - j - k;
                    int hour = arr[i] * 10 + arr[j];
                    int minute = arr[k] * 10 + arr[l];
                    if (hour < 24 && minute < 60)
                        best = Math.max(best, hour * 60 + minute);
                }
        return best == -1 ? "" : String.format("%02d:%02d", best / 60, best % 60);
    }
}

string largestTimeFromDigits(vector<int>& arr) {
    int best = -1;
    sort(arr.begin(), arr.end());
    do {
        int hour = arr[0] * 10 + arr[1];
        int minute = arr[2] * 10 + arr[3];
        if (hour < 24 && minute < 60)
            best = max(best, hour * 60 + minute);
    } while (next_permutation(arr.begin(), arr.end()));
    if (best == -1) return "";
    char buf[6];
    sprintf(buf, "%02d:%02d", best / 60, best % 60);
    return string(buf);
}

Explanation

With only four digits there are at most 4! = 24 ways to arrange them, which is tiny. So the cleanest approach is plain brute force: try every arrangement as HH:MM, keep only the valid ones, and remember the latest.

For each permutation (h1, h2, m1, m2) we form hour = h1*10 + h2 and minute = m1*10 + m2. A time is valid only when hour < 24 and minute < 60, which filters out impossible clock readings.

To compare times easily we convert each valid one into total minutes (hour*60 + minute) and track the maximum in best. Using a single number avoids fiddly string comparisons.

At the end, if best is still -1 no arrangement worked, so we return an empty string. Otherwise we convert best back into HH:MM, padding with zeros.

Example: [1, 2, 3, 4]. Many permutations are valid, like 23:14 and 23:41, but 23:41 is the latest, so it wins.

Time: O(1) (at most 24 permutations) Space: O(1)