Leetcode 949: Largest Time for Given Digits
Given an array of 4 digits, your task is to form the latest possible 24-hour time using each digit exactly once. The time is represented in the format ‘HH:MM’ where ‘HH’ is between 00 and 23, and ‘MM’ is between 00 and 59. If no valid time can be formed, return an empty string.
Problem
Approach
Steps
Complexity
Input: The input consists of an array of integers representing 4 digits.
Example: Input: arr = [9, 1, 2, 4]
Constraints:
• The array will always have exactly 4 digits.
• Each digit will be between 0 and 9.
Output: The output should be the latest valid time in the format 'HH:MM'. If no valid time can be formed, return an empty string.
Example: Output: '21:49'
Constraints:
• The returned string should be in the format 'HH:MM'.
Goal: The goal is to generate all possible times using the given digits and return the latest valid time.
Steps:
• 1. Sort the digits in descending order to try the largest possible times first.
• 2. Try all permutations of the digits to form potential times.
• 3. For each permutation, check if the resulting time is valid (HH:MM format).
• 4. Return the latest valid time, or an empty string if none can be formed.
Goal: Constraints ensure that the solution can handle small arrays efficiently.
Steps:
• The input array will always contain exactly 4 digits.
• Each digit will be in the range [0, 9].
Assumptions:
• The digits provided are valid integers between 0 and 9.
• Input: Input: arr = [9, 1, 2, 4]
• Explanation: The largest valid time possible from these digits is '21:49'. The other permutations are not valid 24-hour times.
• Input: Input: arr = [3, 3, 3, 2]
• Explanation: The largest valid time possible is '23:33'.
Approach: The approach involves generating all permutations of the digits and checking each one for validity in a 24-hour time format.
Observations:
• Since there are only 4 digits, the problem is manageable by checking all permutations.
• Sorting the digits in descending order first helps in quickly finding the largest valid time.
• The key observation is that only a few permutations need to be checked to find the largest valid time.
Steps:
• 1. Sort the digits in descending order to prioritize larger numbers.
• 2. Generate all permutations of the digits to explore all possible times.
• 3. For each permutation, check if the time is valid by ensuring the hours are between 00 and 23, and minutes are between 00 and 59.
• 4. Return the first valid time found in the descending order or an empty string if none is found.
Empty Inputs:
• If the input array is empty, return an empty string.
Large Inputs:
• This problem always assumes exactly 4 digits, so there are no cases for large inputs.
Special Values:
• If all the digits are the same, the approach still works as we generate permutations of identical digits.
Constraints:
• The solution must efficiently handle checking up to 24 permutations (4!) of the digits.
string largestTimeFromDigits(vector<int>& A) {
sort(begin(A), end(A), greater<int>());
do if ((A[0] < 2 || (A[0] == 2 && A[1] < 4)) && A[2] < 6)
return to_string(A[0]) + to_string(A[1]) + ":" + to_string(A[2]) + to_string(A[3]);
while(prev_permutation(begin(A), end(A)));
return "";
}
1 : Function Declaration
string largestTimeFromDigits(vector<int>& A) {
The function `largestTimeFromDigits` takes a vector of integers representing the digits of a time and returns the largest valid time as a string, or an empty string if no valid time can be formed.
2 : Sorting Digits
sort(begin(A), end(A), greater<int>());
Sort the digits in descending order to maximize the first digits of the time and try to form the largest possible valid time.
3 : Check Valid Time
do if ((A[0] < 2 || (A[0] == 2 && A[1] < 4)) && A[2] < 6)
Check if the current permutation of digits forms a valid time. A valid time must have the first two digits as a number less than 24 and the last two digits as a number less than 60.
4 : Form Time String
return to_string(A[0]) + to_string(A[1]) + ":" + to_string(A[2]) + to_string(A[3]);
If the current permutation forms a valid time, convert the digits into a string in the format `HH:MM` and return it.
5 : Generate Previous Permutation
while(prev_permutation(begin(A), end(A)));
If no valid time has been found, generate the next permutation of the digits in descending order and check again.
6 : Return Empty String
return "";
If no valid time can be formed from the digits, return an empty string.
Best Case: O(1)
Average Case: O(24)
Worst Case: O(24)
Description: Generating permutations of 4 digits results in at most 24 permutations. Checking each one takes constant time.
Best Case: O(1)
Worst Case: O(1)
Description: The space complexity is O(1) since we are only storing a few permutations at a time.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus