Largest Time for Given Digits solution and explanation
9 more videos on this problem
Largest Time for Given Digits | LeetCode 949 | C++, Java, PythonKnowledge Center · 11:08 · 6K views
Largest Time for Given Digits | September Leetcode Challenge | Leetcode 949 | Day 1Ayushi Rawat · 3:13 · 2K views
Largest Time for Given Digits | leetcode 949 | HindiCodebix · 10:36 · 2K views
largest time for given digits leetcode | leetcode 949 | two solutions | javaNaresh Gupta · 13:17 · 1K views
largest time for given digits | leetcode september challenge day 1| python solutionthecodingworld · 5:13 · 1K views
Largest Time for Given Digits | Leet code 949 | Theory explained + Python codeSai Anish Malla · 7:05 · 926 views
Largest Time for Given Digits - LeetCode September Challenge Week 1.1Code for Cause · 11:51 · 855 views
Daily Leetcode #154: Sep 01, 2020 - 949. Largest Time for Given DigitsProgramming Live with Larry · 7:34 · 812 views
Largest Time for Given Digits LeetCode September ChallengeSM TechWorld · 16:10 · 637 views
Largest Time for Given Digits | LeetCode 949 | September LeetCoding Challenge | 1st Septembercode.thinkerspoint · 14:21 · 506 views
The problem
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 == 40 <= 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.
from itertools import permutations
def largestTimeFromDigits(arr):
max_time = -1
# permutations generates all possible arrangements of the list
for perm in permutations(arr):
h1, h2, m1, m2 = perm
hours = h1 * 10 + h2
minutes = m1 * 10 + m2
# Check if the hours and minutes form a valid time
if 0 <= hours < 24 and 0 <= minutes < 60:
max_time = max(max_time, hours * 60 + minutes)
if max_time == -1:
return ""
else:
return f"{max_time // 60:02}:{max_time % 60:02}"
# Example Usage:
# print(largestTimeFromDigits([1,2,3,4])) # Output: "23:41"#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
string largestTimeFromDigits(vector<int>& arr) {
string maxTime = "";
sort(arr.begin(), arr.end());
do {
int hours = arr[0] * 10 + arr[1];
int minutes = arr[2] * 10 + arr[3];
if (hours < 24 && minutes < 60) {
string curTime = to_string(hours).substr(0, 2) + ":" + (minutes < 10 ? "0" : "") + to_string(minutes);
if (maxTime.empty() || curTime > maxTime) {
maxTime = curTime;
}
}
} while (next_permutation(arr.begin(), arr.end()));
return maxTime;
}
// Example Usage:
// int main() {
// vector<int> arr = {1, 2, 3, 4};
// cout << largestTimeFromDigits(arr) << endl; // Output: "23:41"
// }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.
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).
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.
def largestTimeFromDigits(arr):
arr.sort(reverse=True)
for i in range(24):
for j in range(60):
hh = [i//10, i%10]
mm = [j//10, j%10]
candidate = hh + mm
candidate.sort(reverse=True)
if candidate == arr:
return f"{i:02}:{j:02}"
return ""
# Example Usage:
# print(largestTimeFromDigits([1,2,3,4])) # Output: "23:41"#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
string largestTimeFromDigits(vector<int>& arr) {
sort(arr.rbegin(), arr.rend()); // Sort in descending order
for (int i = 23; i >= 0; --i) {
for (int j = 59; j >= 0; --j) {
vector<int> candidate = {i / 10, i % 10, j / 10, j % 10};
sort(candidate.rbegin(), candidate.rend());
if (candidate == arr) {
char buffer[6];
snprintf(buffer, sizeof(buffer), "%02d:%02d", i, j);
return string(buffer);
}
}
}
return "";
}
// Example Usage:
// int main() {
// vector<int> arr = {1, 2, 3, 4};
// cout << largestTimeFromDigits(arr) << endl; // Output: "23:41"
// }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.
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.
Approach 3: Default Approach
class Solution {
public String largestTimeFromDigits(int[] arr) {
int ans = -1;
for (int i = 0; i < 4; ++i) {
for (int j = 0; j < 4; ++j) {
for (int k = 0; k < 4; ++k) {
if (i != j && j != k && i != k) {
int h = arr[i] * 10 + arr[j];
int m = arr[k] * 10 + arr[6 - i - j - k];
if (h < 24 && m < 60) {
ans = Math.max(ans, h * 60 + m);
}
}
}
}
}
return ans < 0 ? "" : String.format("%02d:%02d", ans / 60, ans % 60);
}
}func largestTimeFromDigits(arr []int) string {
ans := -1
for i := 0; i < 4; i++ {
for j := 0; j < 4; j++ {
for k := 0; k < 4; k++ {
if i != j && j != k && i != k {
h := arr[i]*10 + arr[j]
m := arr[k]*10 + arr[6-i-j-k]
if h < 24 && m < 60 {
ans = max(ans, h*60+m)
}
}
}
}
}
if ans < 0 {
return ""
}
return fmt.Sprintf("%02d:%02d", ans/60, ans%60)
}Complexity comparison
| Approach | Complexity |
|---|---|
| Brute Force with Permutations | Time Complexity: O(24), because there are 4! (24) permutations to check. |
| Greedy Approach by Constructing Time | Time Complexity: O(1440) at maximum since it iterates through all minute combinations before valid time finding prematurely. |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force with Permutations | O(4!) ≈ O(1) | O(1) | Best for clarity and quick implementation since only 24 permutations exist |
| Greedy Construction of Time | O(1) | O(1) | Preferred in interviews when reasoning about constraints and digit placement |
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.