Skip to main content
Talentd

Largest Time for Given Digits - Solution & Explanation

MediumArrayStringEnumeration9 min readAsked at: Microsoft, Zoho, Liveramp
Practice this problem

Problem Statement

Given an array arr of 4 digits, find the latest 24-hour time that can be made using each digit exactly once.

24-hour times are formatted as "HH:MM", where HH is between 00 and 23, and MM is between 00 and 59. The earliest 24-hour time is 00:00, and the latest is 23:59.

Return the latest 24-hour time in "HH:MM" format. If no valid time can be made, return an empty string.

 

Example 1:

Input: arr = [1,2,3,4]
Output: "23:41"
Explanation: 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: ""
Explanation: There are no valid 24-hour times as "55:55" is not valid.

 

Constraints:

  • arr.length == 4
  • 0 <= arr[i] <= 9

Approach Overview

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.

Approach 1: Brute Force with Permutations

Generate all possible permutations of the given 4 digits and check each permutation to see if it forms a valid time in the 24-hour format. Maintain the latest valid time found during this process.

This Python solution uses the permutations function from the itertools module to generate all possible permutations of the digits. It checks each permutation to see if it forms a valid time, computing the hours and minutes separately with the first two and last two digits respectively. If it forms a valid time, it calculates its total minutes and compares it against the maximum found so far. Finally, it formats the maximum found time (if any) as 'HH:MM' for output or returns an empty string if no valid time was found.

Code

PythonC++

Python

C++

Complexity

Time Complexity: O(24), because there are 4! (24) permutations to check.
Space Complexity: O(1), additional space relative to input size is constant (ignores permutations' storage).

Try this approach in the editor →

Approach 2: Greedy Approach by Constructing Time

Sort the digits in descending order and attempt to form the largest possible hour and minute values by greedily assigning the largest permissible value to each time unit, reducing failures due to invalid hours or minutes promptly.

This Python solution iteratively attempts to create valid times by testing every potential hour and minute combination from the largest possible (23:59) down to (00:00). For each valid time, it reverse sorts and compares the formed digits with the sorted input array. If they match, it returns that time formatted as 'HH:MM'. The greedy reduction of the time possibilities prevents unnecessary permutations.

Code

PythonC++

Python

C++

Complexity

Time Complexity: O(1440) at maximum since it iterates through all minute combinations before valid time finding prematurely.
Space Complexity: O(1), as the only additional space use is from baselines and temporary variables.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Brute Force with Permutations

Time Complexity: O(24), because there are 4! (24) permutations to check.
Space Complexity: O(1), additional space relative to input size is constant (ignores permutations' storage).

Greedy Approach by Constructing Time

Time Complexity: O(1440) at maximum since it iterates through all minute combinations before valid time finding prematurely.
Space Complexity: O(1), as the only additional space use is from baselines and temporary variables.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force with PermutationsO(4!) ≈ O(1)O(1)Best for clarity and quick implementation since only 24 permutations exist
Greedy Construction of TimeO(1)O(1)Preferred in interviews when reasoning about constraints and digit placement

Video Solution

Largest Time for Given Digits | LeetCode 949 | C++, Java, Python • Knowledge Center • 6,617 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Largest Time for Given Digits easy or hard?
Largest Time for Given Digits is usually categorized as a Medium problem. The brute force solution is straightforward, but recognizing constraints and implementing a greedy digit-selection strategy requires stronger reasoning about time formatting rules.
Largest Time for Given Digits Python/Java solution
Python and Java solutions typically generate all permutations of the four digits, validate each possible hour and minute pair, and track the largest valid time. Python often uses itertools.permutations, while Java implementations iterate through permutations manually or with nested loops. Both approaches run in constant time because the input size is fixed.
How to solve Largest Time for Given Digits in O(n)?
The problem effectively runs in constant time because the input size is always four digits. Instead of iterating over permutations, a greedy method selects the largest valid digit for each position in the HH:MM format while removing used digits. This builds the maximum valid time directly in O(1) time and space.
What is the best approach for Largest Time for Given Digits?
The most practical approach is generating all permutations of the four digits and selecting the largest valid time. Since there are only 24 permutations, the algorithm effectively runs in constant time. Many interviewers also accept a greedy construction approach that places the largest valid digit in each position while respecting hour and minute constraints.
Is Largest Time for Given Digits asked at Google/Amazon/Meta?
Variants of digit arrangement and constraint-based construction problems appear in interviews at companies like Amazon, Google, and Meta. While this exact question is more common in coding platforms and practice sets, the underlying techniques—permutation enumeration and greedy selection—are common interview patterns.
What data structure is used in Largest Time for Given Digits?
The problem mainly uses arrays to store and manipulate the four digits. Some implementations also use simple enumeration over permutations or track used digits with indices or boolean flags. The final result is typically formatted as a string in HH:MM format.
What is the time complexity of Largest Time for Given Digits?
The brute force solution runs in O(4!) time, which equals 24 permutations and is effectively constant. Each permutation requires a simple validity check for hour and minute values. Space complexity remains O(1) because only a few variables are used.

Ready to solve this problem?

Practice Largest Time for Given Digits with our built-in code editor and test cases.

Practice on FleetCode
Previous

Number of Valid Clock Times