949. Largest Time for Given Digits

MediumStringEnumeration

Problem Description

The problem provides us with an array of 4 digits. Our task is to use these digits to form the latest possible valid 24-hour format time. The 24-hour time format is represented as "HH:MM", where "HH" is the hour part ranging from 00 to 23 and "MM" is the minute part ranging from 00 to 59. We must use each given digit exactly once. If it's possible to form a valid time, we should return it as a string in the "HH:MM" format; otherwise, if no valid combination exists to make a proper time, we should return an empty string.

The key considerations here include ensuring that the hours are within the valid range (00 to 23) and the minutes fall within the right range (00 to 59).

Intuition

To solve this problem, the solution adopts a brute-force strategy; it iterates over all possible permutations of the given four digits and checks which of these permutations can form a valid time. The idea here is that there are only 24 distinct permutations for 4 digits, which is a small and manageable number to examine exhaustively.

Here's the breakdown of the solution approach:

The solution uses three nested loops to iterate over all possible combinations of the four digits without repetition. Each loop variable (i, j, k) represents an index for a digit in the array arr.
To ensure no digit is repeated, the conditions i != j, i != k, and j != k are enforced.
Out of these three chosen indices, the hour can be formed by combining the digits at index i and j. The minute is then formed by combining the digits at index k and the remaining digit (which is not used so far). The remaining index is calculated as 6 - i - j - k, leveraging the fact that the indices are 0, 1, 2, 3 for a 4-element array and their sum is 6.
The hours (h) are valid if they are less than 24, and the minutes (m) are valid if they are less than 60.
If a combination forms a valid time, it's converted to total minutes (h * 60 + m) to compare easily with other valid times found so far. The maximum value is maintained as ans.
If no valid time is found, ans remains -1, and an empty string is returned.
If a valid time is found, it is formatted correctly by converting the total minutes back into hours and minutes and then constructing a string with a proper "HH:MM" format using string formatting with padding zeroes where needed.

Thus, the solution explores all permutations to find the maximum possible valid time strictly using the 24-hour time constraints and efficiently formats the final answer.

Solution Approach

The implementation uses a simple backtracking algorithm to generate all permutations of the input array and validates each one as a potential 24-hour time.

To begin, a loop runs four times, from 0 to 3, corresponding to the first digit of the hour. Inside it, two nested loops run again from 0 to 3 to account for the second digit of the hour and the first digit of the minutes, respectively. The criteria for each of these loops to continue iterating are that their indices must not be equal (i != j != k) to avoid using the same digit more than once.

The digits for the hour are created by the expression arr[i] * 10 + arr[j], effectively placing arr[i] as the tens digit and arr[j] as the ones digit. Similarly, the minutes are created by the expression arr[k] * 10 + arr[6 - i - j - k], where 6 - i - j - k gives us the one unused index to complete the pair needed for the minutes.

Once h (hours) and m (minutes) are calculated, they're validated to check if they represent a valid time (i.e., h < 24 and m < 60). If the time is valid, we calculate the total minutes since 00:00 using h * 60 + m and update ans with the maximum of itself and the computed total minutes. This effectively stores the latest valid time seen so far.

After all permutations are examined, the solution checks if ans has been updated from its initial value of -1. If it hasn't, this means no valid time was found, and an empty string is returned. If ans has been updated, the total minutes are split back into hours and minutes. The formatting for the output string is done using string interpolation where ans // 60 gives the hours and ans % 60 gives the minutes. The :02 formatter is used to pad the output with leading zeroes if needed, ensuring the correct "HH:MM" format is maintained.

Though not explicitly stated, this implementation assumes that mathematical operations and comparisons are constant-time operations, and since there are only 4! (factorial of 4 i.e., 24) possible permutations, the overall time complexity of the algorithm is O(1) - although it's technically a brute-force solution, its complexity is bound by a small constant because the input size is fixed at 4.

In summary, the implementation utilizes:

A brute-force approach to generate all possible permutations using nested loops.
Mathematical operations and checks to construct valid 24-hour times from the permutations.
A running maximum (ans) to determine the latest valid time.
String formatting and modularity to convert the total minutes back into the required "HH:MM" output format.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's say the input array of 4 digits is [1, 8, 3, 2]. We are tasked with finding the latest valid time that can be formed using these digits. Using the solution approach described above, we would proceed as follows:

Start by initializing the ans variable to -1 to track the latest valid time in minutes.
Begin iterating over all possible permutations of these four digits using three nested loops.
For the first permutation, we might start with i=0, j=1, k=2. Here, i, j, and k correspond to indices in the digits' array, so the digits would be arr[0] = 1, arr[1] = 8, arr[2] = 3.
Since we need two digits for the hour (HH) and two for the minutes (MM), we choose the first two for the hour and the last two for the minute. Here, i and j are for the hours, and k and the unused index for the minutes.
The hours would be arr[i] * 10 + arr[j], which is 1 * 10 + 8 = 18. The minutes would be arr[k] * 10 + arr[6 - i - j - k], which is 3 * 10 + arr[6 - 0 - 1 - 2] = 30 + arr[3] = 30 + 2 = 32. The time so far is 18:32.
The time 18:32 is a valid 24-hour format time since 18 < 24 and 32 < 60. Therefore, we calculate the total minutes as 18 * 60 + 32 = 1152 and update ans with this value since it's the first and thus the maximum found so far.
We continue this process, generating and checking each permutation. Some permutations would be invalid, for instance, if the chosen indices led to hours >= 24 or minutes >= 60; these permutations are ignored.
Assume that after checking all permutations, the largest value for ans remains 1152. This would be the latest valid time in terms of total minutes from 00:00.
We convert 1152 back into hours and minutes. 1152 // 60 gives us 19 hours and 1152 % 60 gives us 12 minutes.
We format these back into the string representation "19:12", padding the hours or minutes with a leading zero if necessary to adhere to the "HH:MM" format. However, in this case, no padding is needed.

Finally, the latest valid time we can form with the input array [1, 8, 3, 2] is "19:12", so this is the string we would return. If we had found no valid permutations, we would return an empty string.

Solution Implementation

1from typing import List
2
3class Solution:
4    def largest_time_from_digits(self, digits: List[int]) -> str:
5        # Initialize the variable to store the maximum minutes which
6        # represents the time formed by the digits
7        max_minutes = -1
8
9        # Generate all possible combinations of the digits
10        for i in range(4):
11            for j in range(4):
12                for k in range(4):
13                    # Ensure the digits i, j, and k are distinct
14                    if i != j and i != k and j != k:
15                        # Calculate the hours by taking digits[i] as the tens place
16                        # and digits[j] as the ones place
17                        hours = digits[i] * 10 + digits[j]
18                        # Calculate the minutes by taking digits[k] as the tens place
19                        # and digits[6 - i - j - k] as the ones place (since 0+1+2+3=6)
20                        # to ensure using all distinct indices
21                        minutes = digits[k] * 10 + digits[6 - i - j - k]
22                      
23                        # Check if the hours and minutes are valid time values
24                        if hours < 24 and minutes < 60:
25                            # Update the maximum minutes if the current combination
26                            # is greater than what we have so far
27                            max_minutes = max(max_minutes, hours * 60 + minutes)
28      
29        # If no valid time could be formed, return an empty string
30        if max_minutes < 0:
31            return ""
32        else:
33            # Format the time in HH:MM format and return
34            return f'{max_minutes // 60:02}:{max_minutes % 60:02}'
35

1class Solution {
2    public String largestTimeFromDigits(int[] digits) {
3        // Initialize the maximum time represented in minutes to an invalid value
4        int maxTime = -1;
5      
6        // Generate all possible times using the four digits
7        // We'll use these digits to create hours and minutes
8        for (int i = 0; i < 4; ++i) {
9            for (int j = 0; j < 4; ++j) {
10                for (int k = 0; k < 4; ++k) {
11                    // Ensure i, j, k are all different to use different digits
12                    if (i == j || j == k || i == k) {
13                        continue; // Skip the iterations where any two are the same
14                    }
15                    // Create the hour by combining the ith and jth digits
16                    int hour = digits[i] * 10 + digits[j];
17                    // Create the minute by combining the kth and remaining digit
18                    // The sum of indices (i, j, k, l) for 4 elements is 0+1+2+3=6
19                    // l, the index of remaining element, is 6 - (i + j + k)
20                    int remainingIndex = 6 - i - j - k;
21                    int minute = digits[k] * 10 + digits[remainingIndex];
22                  
23                    // Validate if the time created is a valid 24-hour format time
24                    if (hour < 24 && minute < 60) {
25                        // Convert hour and minute into total minutes
26                        int totalMinutes = hour * 60 + minute;
27                        // Update the maximum time found so far in minutes
28                        maxTime = Math.max(maxTime, totalMinutes);
29                    }
30                }
31            }
32        }
33      
34        // If no valid time found, return an empty string
35        if (maxTime == -1) {
36            return "";
37        }
38      
39        // Construct the time in HH:MM format from maxTime
40        // maxTime divided by 60 gives the hour and modulo 60 gives the minute
41        // "%02d" means an integer is formatted to a string with at least 2 digits, padding with zeros
42        return String.format("%02d:%02d", maxTime / 60, maxTime % 60);
43    }
44}
45

1#include <vector>
2#include <string>
3#include <algorithm>
4
5class Solution {
6public:
7    // Function to find the largest time that can be made from the given digits
8    string largestTimeFromDigits(vector<int>& digits) {
9        // Initialize the answer with -1 as an indicator that no valid time is found
10        int maxTime = -1;
11
12        // Use nested loops to generate all possible times using the provided digits
13        for (int i = 0; i < 4; ++i) {
14            for (int j = 0; j < 4; ++j) {
15                for (int k = 0; k < 4; ++k) {
16                    // Ensure that i, j, and k are all different to use each digit once
17                    if (i != j && j != k && i != k) {
18                        // Form the hours component by combining two different digits
19                        int hours = digits[i] * 10 + digits[j];
20                        // Form the minutes component by combining the remaining two digits
21                        int minutes = digits[k] * 10 + digits[6 - i - j - k]; // 6 is the sum of indices (0+1+2+3)
22                        // Validate if the formed hours and minutes constitute a valid time
23                        if (hours < 24 && minutes < 60) {
24                            // Update maxTime with the maximum of current time and maxTime
25                            maxTime = std::max(maxTime, hours * 60 + minutes);
26                        }
27                    }
28                }
29            }
30        }
31
32        // If no valid time found, return an empty string
33        if (maxTime < 0) {
34            return "";
35        }
36
37        // Calculate the hours and minutes from maxTime which is in total minutes
38        int maxHours = maxTime / 60;
39        int maxMinutes = maxTime % 60;
40
41        // Form the resulting string in the format "HH:MM"
42        return FormattedTime(maxHours) + ":" + FormattedTime(maxMinutes);
43    }
44
45private:
46    // Helper function to format the hours or minutes into a 2-digit string
47    string FormattedTime(int value) {
48        return std::string(1, '0' + value / 10) + std::string(1, '0' + value % 10);
49    }
50};
51

1// Define a type for the array of digits.
2type DigitsArray = number[];
3
4// Function to format the hours or minutes into a 2-digit string.
5const formattedTime = (value: number): string => {
6    return String('0' + value).slice(-2);
7}
8
9// Function to find the largest time that can be made from the given digits.
10const largestTimeFromDigits = (digits: DigitsArray): string => {
11    // Initialize the answer with -1 as an indicator that no valid time is found.
12    let maxTime: number = -1;
13
14    // Use nested loops to generate all possible times using the provided digits.
15    for (let i = 0; i < 4; ++i) {
16        for (let j = 0; j < 4; ++j) {
17            for (let k = 0; k < 4; ++k) {
18                // Ensure that i, j, and k are all different to use each digit once.
19                if (i !== j && j !== k && i !== k) {
20                    // Form the hours component by combining two different digits.
21                    const hours: number = digits[i] * 10 + digits[j];
22                    // Form the minutes component by combining the remaining two digits.
23                    // 6 is the sum of indices (0+1+2+3) to find the remaining index.
24                    const remainingIndex: number = 6 - i - j - k;
25                    const minutes: number = digits[k] * 10 + digits[remainingIndex];
26                    // Validate if the formed hours and minutes constitute a valid time.
27                    if (hours < 24 && minutes < 60) {
28                        // Update maxTime with the maximum of current time and maxTime.
29                        maxTime = Math.max(maxTime, hours * 60 + minutes);
30                    }
31                }
32            }
33        }
34    }
35
36    // If no valid time was found, return an empty string.
37    if (maxTime === -1) {
38        return "";
39    }
40
41    // Calculate the hours and minutes from maxTime which is in total minutes.
42    const maxHours: number = Math.floor(maxTime / 60);
43    const maxMinutes: number = maxTime % 60;
44
45    // Form the resulting string in the format "HH:MM".
46    return `${formattedTime(maxHours)}:${formattedTime(maxMinutes)}`;
47};
48

Time and Space Complexity

The given code snippet is designed to find the largest possible time that can be displayed on a 24-hour clock, using digits from a given array of four integers.

Time Complexity:

The time complexity of the code is O(1) because the number of iterations is fixed and does not depend on the input size, which is always 4 elements in the arr list. Specifically, the number of iterations would be a fixed number since we are dealing with three nested loops each running for four possible options but skipping the indexes that have already been used (i != j and i != k and j != k). Therefore, the maximum number of iterations is bounded by 4 * 3 * 2 = 24 for each of the three loops (since one number is used as the first element of the hour, one as the first element of the minute, and one as the second element of the minute, while the remaining is the second element of the hour). Even though some iterations are skipped, 24 is the upper limit, which means the time complexity does not depend on the input size but is rather constant.

Space Complexity:

The space complexity of the algorithm is O(1). The extra space used by the algorithm does not grow with the input size. The variables i, j, k, h, m, and ans use a constant amount of space, and there are no additional data structures that grow with input size.

Thus, regardless of the input, the space used by the program remains constant.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What's the output of running the following function using input 56?

1KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13    def dfs(path, res):
14        if len(path) == len(digits):
15            res.append(''.join(path))
16            return
17
18        next_number = digits[len(path)]
19        for letter in KEYBOARD[next_number]:
20            path.append(letter)
21            dfs(path, res)
22            path.pop()
23
24    res = []
25    dfs([], res)
26    return res
27

1private static final Map<Character, char[]> KEYBOARD = Map.of(
2    '2', "abc".toCharArray(),
3    '3', "def".toCharArray(),
4    '4', "ghi".toCharArray(),
5    '5', "jkl".toCharArray(),
6    '6', "mno".toCharArray(),
7    '7', "pqrs".toCharArray(),
8    '8', "tuv".toCharArray(),
9    '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13    List<String> res = new ArrayList<>();
14    dfs(new StringBuilder(), res, digits.toCharArray());
15    return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19    if (path.length() == digits.length) {
20        res.add(path.toString());
21        return;
22    }
23    char next_digit = digits[path.length()];
24    for (char letter : KEYBOARD.get(next_digit)) {
25        path.append(letter);
26        dfs(path, res, digits);
27        path.deleteCharAt(path.length() - 1);
28    }
29}
30

1const KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13    let res = [];
14    dfs(digits, [], res);
15    return res;
16}
17
18function dfs(digits, path, res) {
19    if (path.length === digits.length) {
20        res.push(path.join(''));
21        return;
22    }
23    let next_number = digits.charAt(path.length);
24    for (let letter of KEYBOARD[next_number]) {
25        path.push(letter);
26        dfs(digits, path, res);
27        path.pop();
28    }
29}
30

["jk", "mno"]

["jm", "kn", "lo"]

["jklmnp"]

["jm","jn","jo","km","kn","ko","lm","ln","lo"]

I don't know