#949

Medium

auto_awesomeBacktracking search with pruning

LeetCode Problem Workspace

Largest Time for Given Digits

Given four digits, determine the latest valid 24-hour time possible using each digit exactly once with backtracking.

Problem Statement

You are given an array of four digits. Using each digit exactly once, construct the latest valid 24-hour time in HH:MM format. Hours must be between 00 and 23 and minutes between 00 and 59.

Return the latest possible time as a string in "HH:MM" format. If no valid combination exists that forms a valid 24-hour time, return an empty string. Focus on leveraging backtracking with pruning to avoid unnecessary exploration of invalid digit permutations.

Examples

Example 1

Input: arr = [1,2,3,4]

Output: "23:41"

The valid 24-hour times are "12:34", "12:43", "13:24", "13:42", "14:23", "14:32", "21:34", "21:43", "23:14", and "23:41". Of these times, "23:41" is the latest.

Example 2

Input: arr = [5,5,5,5]

Output: ""

There are no valid 24-hour times as "55:55" is not valid.

Constraints

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

Solution Approach

Generate all digit permutations

Use a recursive backtracking function to explore all permutations of the four digits. At each recursive call, choose a digit not yet used and append it to the current sequence, tracking used digits to avoid repetition.

Prune invalid hour and minute combinations early

Check partial sequences to eliminate branches that cannot form valid hours or minutes. For example, if the first digit is greater than 2 or the hour formed exceeds 23, stop exploring that branch. Similarly, prune minute sequences exceeding 59.

Track the maximum valid time

Convert each valid HHMM sequence to minutes or string format and update a variable holding the latest valid time found. After exploring all permutations, return this maximum time in HH:MM format or an empty string if none exist.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(1) since the number of digit permutations is fixed at 4! = 24, and space complexity is also O(1) for storing permutations and tracking the maximum time. Pruning reduces unnecessary exploration, making backtracking efficient even though the theoretical complexity is constant due to fixed input size.

What Interviewers Usually Probe

Candidate attempts all permutations without pruning, showing incomplete backtracking strategy.
Candidate correctly identifies pruning opportunities for invalid hours and minutes early in recursion.
Candidate efficiently returns the latest valid time, demonstrating understanding of enumeration with constraints.

Common Pitfalls or Variants

Common pitfalls

Failing to prune sequences that cannot form valid hours or minutes, leading to unnecessary recursion.
Incorrectly formatting time, e.g., missing leading zeros for hours or minutes.
Assuming any permutation of digits forms a valid 24-hour time, ignoring constraints for HH and MM ranges.

Follow-up variants

Find the earliest valid 24-hour time instead of the latest using the same digits.
Determine the latest valid 12-hour time with AM/PM from four digits, requiring additional constraints.
Handle arrays of 6 digits and find the latest valid time including seconds in HH:MM:SS format.

FAQ

What pattern does Largest Time for Given Digits use?

This problem primarily uses backtracking search with pruning, exploring permutations of digits while skipping invalid hour or minute sequences.

Can I solve Largest Time for Given Digits without backtracking?

Yes, you can generate all 24 permutations directly and filter valid times, but backtracking with pruning is more efficient and matches the intended pattern.

How do I handle leading zeros in HH:MM format?

Always format hours and minutes as two digits, using leading zeros when necessary, e.g., 03:07 instead of 3:7.

What if no valid 24-hour time can be formed?

Return an empty string to indicate that no permutation of the digits satisfies the 24-hour time constraints.

Does pruning improve performance in this problem?

Yes, pruning eliminates impossible hour or minute combinations early, reducing the number of permutations explored and simplifying the search for the maximum valid time.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

class Solution:
    def largestTimeFromDigits(self, arr: List[int]) -> str:
        cnt = [0] * 10
        for v in arr:
            cnt[v] += 1
        for h in range(23, -1, -1):
            for m in range(59, -1, -1):
                t = [0] * 10
                t[h // 10] += 1
                t[h % 10] += 1
                t[m // 10] += 1
                t[m % 10] += 1
                if cnt == t:
                    return f'{h:02}:{m:02}'
        return ''

Solution 2

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

class Solution:
    def largestTimeFromDigits(self, arr: List[int]) -> str:
        cnt = [0] * 10
        for v in arr:
            cnt[v] += 1
        for h in range(23, -1, -1):
            for m in range(59, -1, -1):
                t = [0] * 10
                t[h // 10] += 1
                t[h % 10] += 1
                t[m // 10] += 1
                t[m % 10] += 1
                if cnt == t:
                    return f'{h:02}:{m:02}'
        return ''

Continue Practicing

#816 ambiguous coordinates #691 stickers to spell word #1239 maximum length of a concatenated string with unique characters