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] <= 9In #949 Largest Time for Given Digits, you are given four digits and must arrange them to form the largest possible valid 24-hour time in the format HH:MM. Since there are only four digits, the key idea is to explore all possible permutations of these digits and check which arrangements produce a valid time.
A practical strategy is to generate all permutations of the four digits and treat the first two digits as the hour and the last two as the minutes. For each permutation, verify whether the hour is less than 24 and the minutes are less than 60. Among all valid combinations, track the one that represents the maximum time. Converting the time into total minutes or comparing lexicographically can help determine the largest valid result.
Because the number of digits is fixed, the total permutations are limited. This makes a brute-force enumeration approach both simple and efficient. The algorithm runs in constant time due to the small input size and requires minimal extra space.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Permutation / Enumeration of all digit arrangements | O(1) (at most 4! permutations) | O(1) |
Knowledge Center
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.
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).
1#include <iostream>
2#include <vector>
3#include <algorithm>
4#include <string>
5
6using namespace std;
7
8string largestTimeFromDigits(vector<int>& arr) {
9 string maxTime = "";
10 sort(arr.begin(), arr.end());
11 do {
12 int hours = arr[0] * 10 + arr[1];
13 int minutes = arr[2] * 10 + arr[3];
14 if (hours < 24 && minutes < 60) {
15 string curTime = to_string(hours).substr(0, 2) + ":" + (minutes < 10 ? "0" : "") + to_string(minutes);
16 if (maxTime.empty() || curTime > maxTime) {
17 maxTime = curTime;
18 }
19 }
20 } while (next_permutation(arr.begin(), arr.end()));
21 return maxTime;
22}
23
24// Example Usage:
25// int main() {
26// vector<int> arr = {1, 2, 3, 4};
27// cout << largestTimeFromDigits(arr) << endl; // Output: "23:41"
28// }
29This C++ solution first sorts the digits to facilitate permutations using std::next_permutation, which is efficient because it modifies the arrangement of elements directly. Within each permutation, it checks the validity of the hours and minutes and keeps track of the largest time found in lexicographical comparison. It returns the largest formatted time discovered or an empty string.
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.
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.
1def largestTimeFromDigits(arr):
2 arr.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, variations of this problem appear in coding interviews because it tests permutation generation, validation logic, and careful handling of constraints. It is commonly categorized as a medium-level problem involving arrays and enumeration.
The most effective approach is to generate all permutations of the four digits and check which combinations form valid 24-hour times. Among the valid times, keep track of the maximum one. Since there are only 24 permutations, this enumeration method is efficient and simple.
Arrays or simple lists are sufficient for this problem because the input size is fixed at four digits. Most solutions rely on permutation generation and basic integer comparisons rather than complex data structures.
After forming a permutation, treat the first two digits as the hour and the last two as the minutes. A valid time must satisfy hour < 24 and minute < 60. Only such combinations should be considered when determining the maximum time.
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.