Domain 2MediumMEDIUM

Largest Time from Digits

Uses permutations to check all valid time combinations and tracks the maximum minutes from midnight.

Domain: medium•Updated: 2026-09-04
#permutation#brute force#O(1)#constant space

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 from 00 to 23. This restricts the first digit of hours to be at most 2, and if it is 2, the second must be <= 3.
  • Valid Minutes (MM): Range from 00 to 59. The tens place for minutes cannot exceed 5.

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 O(N!)O(N!)).

Brute Force Logic:

  1. Generate all unique orderings of the four digits (4!=244! = 24 permutations max).
  2. For each ordering, interpret it as d[0] d[1] : d[2] d[3].
  3. Check if this forms a valid time (Hour < 24 and Minute < 60).
  4. 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 O(1)O(1) 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

  1. Initialize: Set max_minutes to -1. This acts as our sentinel value indicating no valid time has been found yet (since a real minute count is ≥0\ge 0).
  2. Permute: Use an iterator or recursive logic to generate all permutations of the input array digits. In Python, we can use itertools.permutations for conciseness and efficiency in handling duplicates naturally via tuple generation.
  3. Validate & Convert: For each permutation (h1, h0, m1, m0):
    • Calculate Hour: H=h1×10+h0H = h1 \times 10 + h0.
    • Calculate Minute: M=m1×10+m0M = m1 \times 10 + m0.
    • Check if H <= 23 and M <= 59.
  4. Update Max: If valid, calculate total minutes from midnight (H×60+MH \times 60 + M). Update max_minutes if this value is greater than the current maximum.
  5. 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., hour 9 becomes "09").

Complexity Analysis

  • Time Complexity: O(1)O(1). Although the logic involves permutations (N!N!), 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 O(N!)O(N!).
  • Space Complexity: O(1)O(1). 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_minutes remains -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.permutations generates 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 identical max_minutes updates without affecting correctness or performance significantly given N=4.
  • Invalid Hour Tens: The check hours_val <= 23 implicitly handles cases like [9, ...] which would make hour >= 90 (invalid).