Problem Breakdown
We are given an array of exactly four digits (arr). The goal is to rearrange these digits into a valid 24-hour timestamp in "HH:MM" format using each digit exactly once. We must return the latest possible time, or an empty string if no combination forms a valid time.
Key Constraints:
0 <= arr[i] <= 9(Digits only).- Valid Hours (
HH): Range from00to23. This restricts the first digit of hours to be at most2, and if it is2, the second must be<= 3. - Valid Minutes (
MM): Range from00to59. The tens place for minutes cannot exceed5.
Edge Cases:
- No Solution: If digits like
[5, 5, 5, 5]are provided, no valid hour can be formed (e.g., “23” requires a ‘2’ and ‘3’). Return "". - All Zeros: Input
[0, 0, 0, 0]should return"00:00".
Intuition
Since the input size is fixed at N=4, we can afford to check every possible arrangement of these digits without performance penalty in a general sense (though technically ).
Brute Force Logic:
- Generate all unique orderings of the four digits ( permutations max).
- For each ordering, interpret it as
d[0] d[1] : d[2] d[3]. - Check if this forms a valid time (Hour < 24 and Minute < 60).
- Keep track of the maximum valid integer value found so far to ensure we return the “latest” time.
Why not optimize further? Since N is constant, any approach checking permutations runs in relative to input growth (bounded by fixed constraints). Attempting to construct times directly without generating all perms would add unnecessary complexity for such a small search space. The key insight here is that we can simply iterate and validate rather than trying to mathematically derive the max time, which becomes error-prone with digit permutations.
Approach
- Initialize: Set
max_minutesto-1. This acts as our sentinel value indicating no valid time has been found yet (since a real minute count is ). - Permute: Use an iterator or recursive logic to generate all permutations of the input array digits. In Python, we can use
itertools.permutationsfor conciseness and efficiency in handling duplicates naturally via tuple generation. - Validate & Convert: For each permutation
(h1, h0, m1, m0):- Calculate Hour: .
- Calculate Minute: .
- Check if
H <= 23andM <= 59.
- Update Max: If valid, calculate total minutes from midnight (). Update
max_minutesif this value is greater than the current maximum. - Format Output: After checking all permutations:
- If
max_minutes == -1, return empty string. - Otherwise, convert back to
"HH:MM"format using zero-padding (e.g., hour9becomes"09").
- If
Complexity Analysis
- Time Complexity: . Although the logic involves permutations (), since
arr.length == 4, there are at most 24 iterations. This is a constant bound regardless of input values, making it effectively constant time for this specific problem constraint. If generalized to variable N, it would be . - Space Complexity: . We use minimal auxiliary space (variables for digits and max value). The permutation generator uses stack/recursion depth proportional to the fixed input size 4.
Solution
import itertools
def largestTimeFromDigits(arr):
# Sentinel value indicating no valid time found yet (-1 is safe since min minutes >= 0)
max_minutes = -1
# Generate all permutations of the digits (handles duplicates automatically via position logic,
# though we only care about unique values for validity check which this covers implicitly).
for p in itertools.permutations(arr):
h1, h0, m1, m0 = map(int, p)
hours_val = h1 * 10 + h0
minutes_val = m1 * 10 + m0
# Check validity constraints: HH must be < 24 and MM must be < 60
if hours_val <= 23 and minutes_val <= 59:
current_minutes_from_midnight = hours_val * 60 + minutes_val
# Update the maximum valid time found so far (in total minutes)
max_minutes = max(max_minutes, current_minutes_from_midnight)
if max_minutes == -1:
return ""
# Convert integer back to HH:MM format with zero-padding for single digits
h_final = (max_minutes // 60) % 24
m_final = max_minutes % 60
return f"{h_final:02d}:{m_final:02d}"
# Example usage tests
print(largestTimeFromDigits([1, 2, 3, 4])) # "23:41"
print(largestTimeFromDigits([5, 5, 5, 5])) # ""
print(largestTimeFromDigits([0, 0, 0, 0])) # "00:00"
Edge Cases Handled
- No Valid Time: If
max_minutesremains-1, the function returns an empty string (e.g., input[5,5,5,5]). - Zero Padding: The f-string formatting
{h_final:02d}ensures single-digit hours/minutes are padded with a leading zero (e.g., “9” becomes “09”). - Duplicate Digits:
itertools.permutationsgenerates tuples based on index, so if input is[1, 1], it treats them as distinct positions initially. However, since we only care about the value of digits for validity and maximization, duplicate permutations (like(1a, 2) vs (1b, 2)where values are same) result in identicalmax_minutesupdates without affecting correctness or performance significantly given N=4. - Invalid Hour Tens: The check
hours_val <= 23implicitly handles cases like[9, ...]which would make hour >= 90 (invalid).