Largest Time for Given Digits - Video Solutions

Problem Overview: You get an array of four digits. Your goal is to arrange them into the largest possible valid 24‑hour time in HH:MM format. Hours must be between 00–23 and minutes between 00–59. If no valid time can be formed, return an empty string.

Approach 1: Brute Force with Permutations (Time: O(4!) ≈ O(1), Space: O(1))

The simplest strategy is to generate every possible ordering of the four digits. Since there are only 4! = 24 permutations, the search space is tiny. For each permutation, interpret the first two digits as the hour and the last two as the minute. Check validity using conditions like hour < 24 and minute < 60. Track the maximum valid time by converting each candidate into total minutes (hour * 60 + minute) and keeping the largest value. This approach relies on straightforward enumeration and works well because the input size is fixed.

Approach 2: Greedy Construction of Time (Time: O(1), Space: O(1))

A more interview‑friendly approach builds the time digit by digit while respecting constraints. Start by selecting the largest possible digit for the first hour position (H1) that does not exceed 2. Then choose the largest remaining digit for the second hour position (H2) based on whether H1 is 2 (limit becomes 3) or less than 2 (limit becomes 9). Continue similarly for the minute digits: the first minute digit must be ≤5 and the last digit can be anything remaining. This process treats the digits like a small multiset stored in an array. By always choosing the largest valid digit at each step, you construct the lexicographically largest valid time without testing every permutation.

Even though both approaches run in constant time due to the fixed input size, the greedy construction demonstrates stronger reasoning about constraints and digit placement. The brute force method proves correctness quickly, but the greedy method shows deeper understanding of how time formatting rules interact with digit choices. Both techniques involve simple digit manipulation and string formatting when producing the final HH:MM result.

Recommended for interviews: Start with the permutation approach to establish a correct baseline. The input size makes it perfectly acceptable and easy to implement. If the interviewer pushes for optimization or reasoning about constraints, transition to the greedy construction strategy, which demonstrates stronger problem‑solving skills and control over digit selection.