Largest Time for Given Digits

Medium
1747.

Largest Time for Given Digits

Largest Time for Given Digits is a medium coding problem on arrays, strings and enumeration, asked in Amazon and Google interviews.

You are given four digits in arr. Using each digit exactly once, form a 24-hour time "HH:MM", where HH is between 00 and 23 and MM is between 00 and 59.

Return the latest valid time you can form, as a string of the form "HH:MM". If no valid time can be formed, return the empty string.

Example 1

Input
arr = [2,0,6,6]
Output
06:26
Explanation
Any hour starting with 2 would need two digits from {0, 6, 6} for minutes, and 66 is too large.

Example 2

Input
arr = [1,9,4,7]
Output
19:47

Example 3

Input
arr = [5,5,5,5]
Output
Explanation
55 is not an hour, so nothing is valid (the expected output is an empty line).

Constraints

  • arr.length == 4
  • 0 <= arr[i] <= 9
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} arr
 * @return {string}
 */
var largestTimeFromDigits = function(arr) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Largest Time for Given Digits — Problem & Solution

Largest Time for Given Digits solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Largest Time for Given Digits is a medium coding problem on arrays, strings and enumeration, asked in Amazon and Google interviews.

  • Difficulty: Medium
  • Topics: Arrays, Strings, Enumeration
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You are given four digits in arr. Using each digit exactly once, form a 24-hour time "HH:MM", where HH is between 00 and 23 and MM is between 00 and 59.

Return the latest valid time you can form, as a string of the form "HH:MM". If no valid time can be formed, return the empty string.

Example 1

Input: arr = [2,0,6,6]
Output: 06:26
Explanation: Any hour starting with 2 would need two digits from {0, 6, 6} for minutes, and 66 is too large.

Example 2

Input: arr = [1,9,4,7]
Output: 19:47

Example 3

Input: arr = [5,5,5,5]
Output: 
Explanation: 55 is not an hour, so nothing is valid (the expected output is an empty line).

Constraints

  • arr.length == 4
  • 0 <= arr[i] <= 9

Hints for Largest Time for Given Digits

  1. Hint 1

    There are only 4! = 24 ways to order four digits.

  2. Hint 2

    For each ordering, the first two digits form the hour and the last two the minutes; keep it if the hour is below 24 and the minutes below 60.

  3. Hint 3

    Compare candidates by hour * 60 + minutes and format the best one with leading zeros.

How to solve Largest Time for Given Digits

With four digits there are 24 orderings — try them all, keep the valid ones, and pick the latest.

Approach

  1. Loop over every choice of distinct positions i, j, k for the hour's tens, the hour's ones and the minutes' tens; the remaining position l = 6 - i - j - k is the minutes' ones.
  2. Let h = 10·arr[i] + arr[j] and m = 10·arr[k] + arr[l]. Skip unless h < 24 and m < 60.
  3. Track the largest h * 60 + m.
  4. If nothing was valid return ""; otherwise format it as "HH:MM" with leading zeros.

Why it works

Every assignment of the four digits to the four time positions is one of the 24 orderings, and comparing minutes since midnight orders times correctly.

Complexity

  • Time — O(1) — 24 candidates
  • Space — O(1)

Pitfalls

  • Greedily taking the largest digit first fails: for [2,0,6,6] an hour of 2x leaves 66 for the minutes.
  • Keep the leading zeros: 6:26 must be written 06:26.
  • 00:00 is a valid answer, distinct from the empty string.

Reference solution

Python

from typing import List
from itertools import permutations

def largestTimeFromDigits(arr: List[int]) -> str:
    best = -1
    for a, b, c, d in permutations(arr):
        h, m = a * 10 + b, c * 10 + d
        if h < 24 and m < 60:
            best = max(best, h * 60 + m)
    if best < 0:
        return ""
    return "%02d:%02d" % (best // 60, best % 60)

Java

public static String largestTimeFromDigits(int[] arr) {
    int best = -1;
    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 h = arr[i] * 10 + arr[j], m = arr[k] * 10 + arr[l];
                if (h < 24 && m < 60) best = Math.max(best, h * 60 + m);
            }
    if (best < 0) return "";
    return String.format("%02d:%02d", best / 60, best % 60);
}

C++

string largestTimeFromDigits(vector<int>& arr) {
    int best = -1;
    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 h = arr[i] * 10 + arr[j], m = arr[k] * 10 + arr[l];
                if (h < 24 && m < 60) best = max(best, h * 60 + m);
            }
    if (best < 0) return "";
    char buf[8];
    snprintf(buf, sizeof(buf), "%02d:%02d", best / 60, best % 60);
    return string(buf);
}

JavaScript

var largestTimeFromDigits = function(arr) {
    var best = -1;
    for (var i = 0; i < 4; i++) {
        for (var j = 0; j < 4; j++) {
            for (var k = 0; k < 4; k++) {
                if (i === j || j === k || i === k) continue;
                var l = 6 - i - j - k;
                var h = arr[i] * 10 + arr[j], m = arr[k] * 10 + arr[l];
                if (h < 24 && m < 60 && h * 60 + m > best) best = h * 60 + m;
            }
        }
    }
    if (best < 0) return "";
    var hh = Math.floor(best / 60), mm = best % 60;
    return (hh < 10 ? "0" : "") + hh + ":" + (mm < 10 ? "0" : "") + mm;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Strings