How to Solve Largest Time for Given Digits

Start by generating all permutations of the four digits, applying pruning to skip impossible hour or minute combinations early. Track the maximum valid time in HH:MM format as you explore. Return the latest valid time or an empty string if no valid time exists, ensuring the backtracking search efficiently handles invalid branches.

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

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.

How GhostInterview Helps

• GhostInterview highlights the backtracking pattern and guides pruning logic for invalid digit sequences.
• It tracks the maximum valid time during permutation exploration, preventing manual miscalculations.
• It demonstrates early branch elimination, reinforcing efficient enumeration over all possible digit combinations.

Topic Pages

• Array
• String
• Backtracking
• Enumeration

Related GhostInterview Pages

• LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
• Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
• How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.

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.