LeetCode 949 - Largest Time for Given Digits

The problem provides an array of exactly four digits. Using each digit exactly once, we must construct the latest possible valid 24-hour time in the format "HH:MM".

leetcodemediumarraystringbacktrackingenumeration

LeetCode Problem 949

Difficulty: 🟡 Medium
Topics: Array, String, Backtracking, Enumeration

Solution

Problem Understanding

The problem provides an array of exactly four digits. Using each digit exactly once, we must construct the latest possible valid 24-hour time in the format "HH:MM".

A valid 24-hour time has two important constraints:

  • The hour portion, HH, must be between 00 and 23
  • The minute portion, MM, must be between 00 and 59

The task is not simply to arrange the digits into the largest four-digit number. The arrangement must satisfy the rules of time formatting. For example, 29:99 is numerically large, but completely invalid as a time.

The input array contains only four digits, and each digit must be used exactly once. No digit can be skipped, and no digit can be reused. If it is impossible to form a valid time, the function must return an empty string.

The constraints are extremely small:

  • arr.length == 4
  • Each digit is between 0 and 9

Because there are only four digits, the total number of possible arrangements is very limited. Specifically, there are at most 4! = 24 permutations. This small search space strongly suggests that a complete enumeration solution is feasible and efficient.

Several edge cases are important to recognize early:

  • All digits may be invalid for time creation, such as [5,5,5,5]
  • Leading zeros are allowed, such as "01:23"
  • Duplicate digits may appear, which can create repeated permutations
  • The numerically largest arrangement may not produce the largest valid time
  • The optimal solution may require carefully balancing hour and minute validity

For example, with [2,4,0,0], the arrangement "24:00" is invalid because the hour cannot exceed 23, but "20:40" is valid.

Approaches

Brute Force Approach

The brute-force approach generates every possible arrangement of the four digits. Since there are only four digits, this means generating all 24 permutations.

For each permutation:

  • Use the first two digits as the hour
  • Use the last two digits as the minute
  • Check whether the resulting time is valid
  • If valid, compare it against the best time found so far

Because every possible arrangement is examined, this approach is guaranteed to find the latest valid time if one exists.

Although brute force is often considered inefficient, the input size here is so small that the method is perfectly acceptable. Evaluating 24 permutations is effectively constant time.

Key Insight Behind the Optimal Solution

The key observation is that the search space is tiny. With only four digits, exhaustive enumeration is not only feasible but actually the cleanest and safest strategy.

Instead of attempting a complicated greedy construction, we can simply evaluate every possible valid time and keep the maximum.

A greedy approach can easily fail because choosing the largest possible digit for the hour may block a better overall time later. For example:

  • Choosing 2 as the first digit may force an invalid second digit
  • A slightly smaller hour may allow a much larger minute value

Because the total number of permutations is only 24, exhaustive search provides both simplicity and correctness.

Approach Time Complexity Space Complexity Notes
Brute Force O(4!) O(1) Generates all permutations and checks validity
Optimal O(4!) O(1) Same enumeration idea, but tracks the maximum efficiently

Algorithm Walkthrough

  1. Generate all possible permutations of the four digits.

Since there are only four digits, there are at most 24 possible orderings. Each ordering represents one candidate time. 2. Interpret each permutation as a time.

For a permutation [a, b, c, d]:

  • Hour becomes 10 * a + b
  • Minute becomes 10 * c + d

This directly converts the digits into "HH:MM" format. 3. Validate the candidate time.

A valid time must satisfy:

  • 0 <= hour < 24
  • 0 <= minute < 60

Invalid permutations are discarded immediately. 4. Convert the valid time into total minutes.

Using:

total_minutes = hour * 60 + minute

Comparing times as total minutes makes it easy to determine which time is later. 5. Track the largest valid time found so far.

Maintain a variable storing the maximum total minutes encountered.

Whenever a larger valid time appears, update the answer. 6. Format the final answer.

If a valid time was found:

  • Convert the best hour and minute back into "HH:MM"
  • Use zero-padding for single-digit values

Otherwise, return an empty string.

Why it works

The algorithm checks every possible arrangement of the digits exactly once. Since every valid time must correspond to one of these permutations, the algorithm cannot miss the optimal answer.

By comparing all valid times and keeping the largest one, the final result is guaranteed to be the latest valid 24-hour time constructible from the given digits.

Python Solution

from itertools import permutations
from typing import List

class Solution:
    def largestTimeFromDigits(self, arr: List[int]) -> str:
        best_minutes = -1
        best_time = ""

        for perm in permutations(arr):
            hour = perm[0] * 10 + perm[1]
            minute = perm[2] * 10 + perm[3]

            if hour < 24 and minute < 60:
                total_minutes = hour * 60 + minute

                if total_minutes > best_minutes:
                    best_minutes = total_minutes
                    best_time = f"{hour:02d}:{minute:02d}"

        return best_time

The implementation begins by generating all permutations using Python's itertools.permutations. This avoids manually writing recursive backtracking logic and keeps the solution concise.

For each permutation, the first two digits are combined into the hour and the last two digits into the minute. This mirrors the exact structure of a 24-hour time.

The validation step ensures the hour is less than 24 and the minute is less than 60. Invalid arrangements are ignored immediately.

To compare times efficiently, the code converts each valid time into total minutes since midnight. This transforms time comparison into simple integer comparison.

Whenever a larger valid time is found, both the best minute count and formatted time string are updated.

Finally, if no valid permutation exists, the initial empty string remains unchanged and is returned.

Go Solution

package main

import "fmt"

func largestTimeFromDigits(arr []int) string {
	bestMinutes := -1
	bestTime := ""

	for i := 0; i < 4; i++ {
		for j := 0; j < 4; j++ {
			if j == i {
				continue
			}

			for k := 0; k < 4; k++ {
				if k == i || k == j {
					continue
				}

				for l := 0; l < 4; l++ {
					if l == i || l == j || l == k {
						continue
					}

					hour := arr[i]*10 + arr[j]
					minute := arr[k]*10 + arr[l]

					if hour < 24 && minute < 60 {
						totalMinutes := hour*60 + minute

						if totalMinutes > bestMinutes {
							bestMinutes = totalMinutes
							bestTime = fmt.Sprintf("%02d:%02d", hour, minute)
						}
					}
				}
			}
		}
	}

	return bestTime
}

The Go implementation uses four nested loops instead of a built-in permutation utility because Go does not provide one in the standard library.

Each loop selects a unique index, ensuring every digit is used exactly once. The rest of the logic is identical to the Python solution.

Go strings are immutable just like Python strings, so formatting the result with fmt.Sprintf is straightforward.

There are no concerns about integer overflow because all values remain extremely small.

Worked Examples

Example 1

Input:

arr = [1,2,3,4]

The algorithm evaluates all permutations.

Permutation Hour Minute Valid? Total Minutes Best So Far
[1,2,3,4] 12 34 Yes 754 12:34
[1,2,4,3] 12 43 Yes 763 12:43
[1,3,2,4] 13 24 Yes 804 13:24
[2,3,4,1] 23 41 Yes 1421 23:41
[2,4,3,1] 24 31 No - 23:41

Eventually, the largest valid time discovered is:

23:41

Example 2

Input:

arr = [5,5,5,5]

Every permutation produces:

55:55

Validation fails because:

  • 55 >= 24
  • 55 >= 60
Permutation Hour Minute Valid?
[5,5,5,5] 55 55 No

No valid time is found, so the result is:

""

Complexity Analysis

Measure Complexity Explanation
Time O(4!) There are at most 24 permutations to evaluate
Space O(1) Only a few variables are used

Although the algorithm enumerates permutations, the input size is fixed at four digits. Therefore, the total number of operations is bounded by a small constant.

Even in the worst case, only 24 candidate times are checked, making the solution extremely efficient in practice.

Test Cases

from typing import List

class Solution:
    def largestTimeFromDigits(self, arr: List[int]) -> str:
        from itertools import permutations

        best_minutes = -1
        best_time = ""

        for perm in permutations(arr):
            hour = perm[0] * 10 + perm[1]
            minute = perm[2] * 10 + perm[3]

            if hour < 24 and minute < 60:
                total_minutes = hour * 60 + minute

                if total_minutes > best_minutes:
                    best_minutes = total_minutes
                    best_time = f"{hour:02d}:{minute:02d}"

        return best_time

sol = Solution()

assert sol.largestTimeFromDigits([1,2,3,4]) == "23:41"  # standard example
assert sol.largestTimeFromDigits([5,5,5,5]) == ""  # impossible case
assert sol.largestTimeFromDigits([0,0,0,0]) == "00:00"  # all zeros
assert sol.largestTimeFromDigits([2,4,0,0]) == "20:40"  # 24:00 invalid
assert sol.largestTimeFromDigits([2,3,5,9]) == "23:59"  # maximum possible valid time
assert sol.largestTimeFromDigits([0,1,2,3]) == "23:10"  # leading zero handling
assert sol.largestTimeFromDigits([1,9,6,0]) == "19:06"  # valid minute restriction
assert sol.largestTimeFromDigits([7,8,9,9]) == ""  # no valid hour
assert sol.largestTimeFromDigits([2,0,6,6]) == "06:26"  # best arrangement not starting with 2
assert sol.largestTimeFromDigits([0,4,0,0]) == "04:00"  # multiple zeros
Test Why
[1,2,3,4] Basic valid example
[5,5,5,5] No valid time possible
[0,0,0,0] Minimum valid time
[2,4,0,0] Checks invalid hour handling
[2,3,5,9] Maximum valid time possible
[0,1,2,3] Verifies leading zero formatting
[1,9,6,0] Ensures minute validation
[7,8,9,9] Impossible due to invalid hour digits
[2,0,6,6] Best solution may use smaller hour
[0,4,0,0] Duplicate digits and formatting

Edge Cases

One important edge case occurs when no valid time can be formed. Inputs like [5,5,5,5] produce only invalid hours and minutes. A naive implementation might accidentally return the numerically largest arrangement even though it is invalid. This implementation prevents that by validating every candidate before considering it as an answer. If no valid candidate is ever found, the function correctly returns an empty string.

Another important case involves leading zeros. Times such as "01:23" and "04:00" are completely valid in 24-hour format. Some implementations mistakenly reject leading zeros or fail to format them properly. This solution uses formatted output with zero-padding, ensuring that hours and minutes always contain exactly two digits.

Duplicate digits can also create subtle issues. For example, [0,0,1,0] generates many repeated permutations. A flawed implementation might accidentally reuse indices incorrectly or fail to consider all possibilities. Since the algorithm explicitly generates permutations using positions, every valid arrangement is examined correctly, even when multiple digits are identical.

A final tricky case is when the largest numerical arrangement is invalid. For example, [2,4,0,0] could tempt a greedy strategy into producing "24:00", which is not a valid 24-hour time. The exhaustive permutation approach avoids this problem entirely because it evaluates every candidate and selects the largest valid one rather than assuming locally optimal digit choices lead to the global optimum.