Problem Description

You are given an array of exactly 4 digits (each digit is between 0-9). Your task is to find the latest possible 24-hour time that can be formed using each digit exactly once.

The time format should be "HH:MM" where:

• HH represents hours and must be between 00 and 23
• MM represents minutes and must be between 00 and 59

You need to use all 4 digits from the input array, with each digit used exactly once to form a valid time. If it's impossible to form a valid time using all 4 digits exactly once, return an empty string.

For example:

• If given [1, 2, 3, 4], the latest valid time would be "23:41"
• If given [5, 5, 5, 5], no valid time can be formed, so return ""

The solution approach iterates through all possible times starting from the latest (23:59) and going backwards. For each time, it checks if the digits needed to form that time exactly match the digits provided in the input array. The first valid match found is the latest possible time.

The code uses a counting approach:

1. Count the frequency of each digit in the input array
2. For each possible time from 23:59 down to 00:00:
   • Extract the 4 digits needed for that time
   • Count their frequencies
   • If the digit frequencies match the input array's frequencies, return this time
3. If no valid time is found, return an empty string

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• No: The problem involves an array of digits, not nodes and edges as in graph problems.

Need to solve for kth smallest/largest?

• No: We're looking for the maximum valid time, but not the kth element in a sorted order.

Involves Linked Lists?

• No: The problem works with an array of digits, not linked lists.

Does the problem have small constraints?

• Yes: The constraint is very small - we have exactly 4 digits, and need to arrange them to form a valid time. This means we only have 4! = 24 possible permutations to check.

Brute force / Backtracking?

• Yes: With only 24 possible arrangements of 4 digits, we can afford to check all permutations to find which ones form valid times, then select the maximum among them.

Conclusion: The flowchart suggests using a brute force/backtracking approach. This makes sense because:

1. We need to explore all possible arrangements of the 4 digits
2. For each arrangement, we check if it forms a valid time (hours 00-23, minutes 00-59)
3. Among all valid times, we select the latest one
4. The small constraint (only 4 digits) makes exhaustive search feasible

The solution indeed uses a brute force approach, though implemented slightly differently - instead of generating permutations, it iterates through all possible times from 23:59 down to 00:00 and checks if the required digits match the input array.

Intuition

When we need to find the "latest" or "maximum" valid time from 4 digits, we have two main approaches to consider:

1. Generate all permutations of the 4 digits and check which ones form valid times
2. Iterate through all possible times and check if we can form them with our digits

The key insight here is that the search space for valid 24-hour times is actually quite small - there are only 24 × 60 = 1,440 possible times in a day. This is comparable to checking 4! = 24 permutations of our digits.

The solution cleverly chooses the second approach with a twist: instead of checking times from 00:00 upward, it starts from 23:59 and works backward. Why? Because we want the latest valid time, so the first valid time we encounter while going backward will be our answer.

The matching process is elegant - for each candidate time, we:

• Break it down into its 4 digits (e.g., 23:41 becomes [2, 3, 4, 1])
• Count the frequency of each digit needed
• Compare this frequency count with the frequency count of our input digits
• If they match exactly, we've found a valid time using all our digits exactly once

This frequency-counting approach handles duplicate digits naturally. For example, if our input is [1, 1, 2, 3], the frequency count would be {1: 2, 2: 1, 3: 1}, and we'd need to find a time whose digits have the exact same frequency distribution.

By iterating from 23:59 downward and returning immediately upon finding a match, we guarantee we've found the latest possible time without needing to track or compare multiple valid candidates.

Learn more about Backtracking patterns.

Solution Approach

The implementation uses a frequency counting approach to validate whether a given time can be formed from the input digits:

1. Count Input Digit Frequencies: First, create a frequency array cnt of size 10 (for digits 0-9) and count how many times each digit appears in the input array.

   cnt = [0] * 10
   for v in arr:
       cnt[v] += 1

2. Iterate Through Times in Descending Order: Use nested loops to iterate through all possible times from 23:59 down to 00:00:

   • Outer loop: hours from 23 down to 0
   • Inner loop: minutes from 59 down to 0

   for h in range(23, -1, -1):
       for m in range(59, -1, -1):

3. Extract and Count Time Digits: For each candidate time, create a temporary frequency array t and count the digits needed to form this time:

   t = [0] * 10
   t[h // 10] += 1  # tens digit of hour
   t[h % 10] += 1   # ones digit of hour
   t[m // 10] += 1  # tens digit of minute
   t[m % 10] += 1   # ones digit of minute

   For example, if the time is 23:41:

   • h // 10 = 2, h % 10 = 3
   • m // 10 = 4, m % 10 = 1
   • So t would have: t[1]=1, t[2]=1, t[3]=1, t[4]=1

4. Compare Frequency Arrays: If the frequency array of the current time exactly matches the input frequency array, we've found our answer:

   if cnt == t:
       return f'{h:02}:{m:02}'

   The format string f'{h:02}:{m:02}' ensures proper formatting with leading zeros (e.g., 09:05 instead of 9:5).

5. Return Empty String if No Valid Time: If we've checked all possible times and found no match, return an empty string.

The time complexity is O(1) since we check at most 1,440 fixed times, and the space complexity is O(1) as we only use fixed-size arrays of length 10.

Example Walkthrough

Let's walk through the solution with the input array [1, 2, 3, 4].

Step 1: Count Input Frequencies First, we count how many times each digit appears in our input:

• Digit 1 appears 1 time
• Digit 2 appears 1 time
• Digit 3 appears 1 time
• Digit 4 appears 1 time
• All other digits appear 0 times

Our frequency array cnt = [0, 1, 1, 1, 1, 0, 0, 0, 0, 0]

Step 2: Iterate from Latest Time We start checking from 23:59 and work backwards:

• Time 23:59: Digits needed are [2, 3, 5, 9]

  • Frequency: [0, 0, 1, 1, 0, 1, 0, 0, 0, 1]
  • Compare with input: Not a match (we don't have 5 or 9)

• Time 23:58: Digits needed are [2, 3, 5, 8]

  • Frequency: [0, 0, 1, 1, 0, 1, 0, 0, 1, 0]
  • Compare with input: Not a match (we don't have 5 or 8)

• Continue checking... (skipping ahead for brevity)

• Time 23:41: Digits needed are [2, 3, 4, 1]

  • Break down: Hour = 23 → digits 2 and 3, Minute = 41 → digits 4 and 1
  • Frequency: [0, 1, 1, 1, 1, 0, 0, 0, 0, 0]
  • Compare with input: Perfect match!

Step 3: Return Result Since we found a match at 23:41, we immediately return "23:41". This is guaranteed to be the latest valid time because we checked from the latest possible time backwards.

Another Example: Input [5, 5, 5, 5]

Step 1: Count Input Frequencies

• Digit 5 appears 4 times
• Frequency array cnt = [0, 0, 0, 0, 0, 4, 0, 0, 0, 0]

Step 2: Check All Times We need to find a time where exactly 4 digits are all 5s. However:

• The maximum valid hour is 23 (can't use 55)
• The maximum valid minute is 59 (can't use 55)
• No valid time uses the digit 5 four times

After checking all 1,440 possible times from 23:59 down to 00:00, none match our frequency requirement.

Step 3: Return Empty String Since no valid time can be formed, we return "".

Solution Implementation

Time and Space Complexity

Time Complexity: O(1)

The algorithm iterates through all possible valid times from 23:59 down to 00:00. The outer loop runs from hour 23 to 0 (24 iterations), and the inner loop runs from minute 59 to 0 (60 iterations). This gives us 24 × 60 = 1440 iterations in total. Since 1440 is a constant that doesn't depend on the input size, the time complexity is O(1).

Within each iteration, we perform the following constant-time operations:

• Creating array t of size 10: O(1)
• Four increment operations for digits: O(1)
• Comparing two arrays of size 10: O(1)

Space Complexity: O(1)

The algorithm uses:

• Array cnt of size 10 to count digit frequencies: O(1)
• Array t of size 10 (recreated in each iteration) to store the digit frequencies of current time: O(1)
• A few integer variables (h, m, v): O(1)

Since all space usage is constant and independent of the input size (the input is always an array of exactly 4 digits), the space complexity is O(1).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Digit Extraction Using String Conversion

A common mistake is converting the hour and minute to strings to extract individual digits, which can fail for single-digit values:

Incorrect approach:

# This fails for hours < 10 or minutes < 10
hour_str = str(hour)  # "9" instead of "09"
time_digits[int(hour_str[0])] += 1  # IndexError or wrong digit
time_digits[int(hour_str[1])] += 1  # IndexError!

Why it fails: When hour = 9, str(9) gives "9" (length 1), not "09". Trying to access hour_str[1] causes an IndexError.

Correct approach: Use integer division and modulo operations:

time_digits[hour // 10] += 1  # Always gives tens digit (0 for hour < 10)
time_digits[hour % 10] += 1   # Always gives ones digit

2. Not Handling Duplicate Digits Properly

Another pitfall is trying to use a set or simple membership check instead of frequency counting:

Incorrect approach:

# This doesn't account for duplicate digits
input_digits = set(arr)
for hour in range(23, -1, -1):
    for minute in range(59, -1, -1):
        time_str = f'{hour:02d}{minute:02d}'
        if set(time_str) == input_digits:  # Wrong! Ignores counts
            return f'{hour:02d}:{minute:02d}'

Why it fails: Input [2, 2, 1, 1] should form "22:11", but using sets would compare {1, 2} == {1, 2}, which would incorrectly validate times like "21:21" or "12:12".

Correct approach: Use frequency arrays to ensure exact digit counts match:

digit_count = [0] * 10
for digit in arr:
    digit_count[digit] += 1
# Then compare full frequency arrays: digit_count == time_digits

3. Forgetting to Format Output with Leading Zeros

The output must be in "HH:MM" format with leading zeros:

Incorrect:

return f'{hour}:{minute}'  # Returns "9:5" instead of "09:05"

Correct:

return f'{hour:02d}:{minute:02d}'  # Always returns proper "HH:MM" format