LeetCode 949: Largest Time for Given Digits

Problem Restatement

We are given an array arr containing exactly four digits.

We need to use each digit exactly once to form a valid 24-hour time in this format:

HH:MM

The hour must be between:

00 and 23

The minute must be between:

00 and 59

Return the latest valid time that can be made.

If no valid time can be made, return an empty string. The official statement defines the same requirement: use all four digits exactly once and return the largest valid 24-hour time, or "" if impossible.

Input and Output

Function shape:

class Solution:
    def largestTimeFromDigits(self, arr: list[int]) -> str:
        ...

Examples

Example 1:

arr = [1, 2, 3, 4]

A valid latest time is:

23:41

So the answer is:

"23:41"

Example 2:

arr = [5, 5, 5, 5]

No valid hour can be formed, because every possible hour starts with 5.

So the answer is:

""

Example 3:

arr = [0, 0, 0, 0]

The only possible time is:

"00:00"

So the answer is:

"00:00"

First Thought

There are only four digits.

The number of possible arrangements is:

4! = 24

That is very small.

So we can simply try every permutation, check whether it forms a valid time, and keep the largest one.

Key Insight

A time string has this structure:

h1 h2 : m1 m2

For a permutation (a, b, c, d):

hour = 10 * a + b
minute = 10 * c + d

It is valid if:

hour < 24
minute < 60

Among valid times, a larger hour is better.

If hours are equal, a larger minute is better.

So we can compare total minutes since midnight:

hour * 60 + minute

Algorithm

Initialize:

best_minutes = -1
best_time = ""

For every permutation of arr:

1. Compute hour.
2. Compute minute.
3. Check whether the time is valid.
4. Convert it to total minutes.
5. If it is larger than the best seen so far, update the answer.

Return best_time.

Walkthrough

Use:

arr = [1, 2, 3, 4]

Some permutations:

Among all valid times, the latest is:

"23:41"

Correctness

The algorithm checks every possible ordering of the four digits.

Every valid time using the four digits exactly once corresponds to one of these permutations.

For each permutation, the algorithm computes the corresponding hour and minute and accepts it only if the hour is less than 24 and the minute is less than 60. Therefore, every accepted candidate is a valid 24-hour time.

The algorithm compares valid candidates by total minutes since midnight. This ordering is exactly the chronological ordering of times within one day.

Since every possible valid time is considered and the algorithm keeps the largest one, the returned string is the latest valid time.

If no permutation forms a valid time, no valid answer exists, and the algorithm correctly returns an empty string.

Complexity

Even though we use permutations, the input size is fixed at four digits.

Implementation

from itertools import permutations

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

        for a, b, c, d in permutations(arr):
            hour = 10 * a + b
            minute = 10 * c + d

            if hour >= 24 or minute >= 60:
                continue

            total = hour * 60 + minute

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

        return best_time

Code Explanation

We generate every ordering of the four digits:

for a, b, c, d in permutations(arr):

The first two digits form the hour:

hour = 10 * a + b

The last two digits form the minute:

minute = 10 * c + d

Invalid times are skipped:

if hour >= 24 or minute >= 60:
    continue

For valid times, compare by total minutes:

total = hour * 60 + minute

When a better time is found, format it with two digits for hour and minute:

best_time = f"{hour:02d}:{minute:02d}"

This correctly produces values like:

00:00
01:09
23:41

Testing

def run_tests():
    s = Solution()

    assert s.largestTimeFromDigits([1, 2, 3, 4]) == "23:41"
    assert s.largestTimeFromDigits([5, 5, 5, 5]) == ""
    assert s.largestTimeFromDigits([0, 0, 0, 0]) == "00:00"
    assert s.largestTimeFromDigits([0, 0, 1, 0]) == "10:00"
    assert s.largestTimeFromDigits([2, 0, 6, 6]) == "06:26"
    assert s.largestTimeFromDigits([2, 3, 5, 9]) == "23:59"

    print("all tests passed")

run_tests()