Jobs

Interviews

Discussions

Largest Time for Given Digits

Medium

Asked by:

18 views

Topics:

ArraysStringsRecursion

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

Try coding it in LeetCode

Largest Time for Given Digits

Medium

Asked by:

18 views

Topics:

ArraysStringsRecursion

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

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Are the digits in the input array guaranteed to be between 0 and 9 inclusive?
If it's not possible to form a valid 24-hour time, what should I return (e.g., an empty string, null, or a specific error message)?
Can the input array contain duplicate digits, and if so, how should that be handled when constructing the largest time?
Is the input array always guaranteed to contain exactly four digits?
If multiple valid times can be formed, should I return the lexicographically largest, or is any valid time acceptable?

Brute Force Solution

Approach

The brute force approach to finding the largest possible time involves trying every single combination of the given digits. We'll arrange the digits in every possible order and check if that arrangement makes a valid time. We'll keep track of the largest valid time we find.

Here's how the algorithm would work step-by-step:

Take the four given digits and start arranging them in every possible order.
For each arrangement, treat the first two digits as the hour and the last two as the minutes.
Check if the hour is between 00 and 23, and if the minutes are between 00 and 59.
If the hour and minutes are both valid, then this arrangement is a possible time.
If the possible time is larger than the largest valid time we've seen so far, remember this new time.
Repeat this process for every single arrangement of the four digits.
After trying all the arrangements, the largest valid time that we remembered is the answer.

Code Implementation

import itertools

def largest_time_from_digits(digits):
    largest_valid_time = ""
    
    # Generate all possible permutations of the digits
    for permutation in itertools.permutations(digits):
        hour = permutation[0] * 10 + permutation[1]
        minute = permutation[2] * 10 + permutation[3]
        
        # Only proceed if the current permutation forms a valid time
        if 0 <= hour <= 23 and 0 <= minute <= 59:

            time = "{0:02d}:{1:02d}".format(hour, minute)

            # Check if the new valid time is larger than the current largest
            if largest_valid_time == "" or time > largest_valid_time:
                largest_valid_time = time

    return largest_valid_time

Big(O) Analysis

Time Complexity

O(1) – The input consists of a fixed number of digits (four). The algorithm generates all permutations of these four digits, which is a constant operation (4! = 24). For each permutation, it performs a constant amount of work to check its validity as a time and update the maximum time found so far. Since both the number of permutations and the work per permutation are constant, the overall time complexity is O(1).

Space Complexity

O(1) – The provided brute force approach generates permutations of the four input digits, but the number of digits is fixed. The algorithm only needs to store a constant number of variables, such as the current largest valid time found and temporary variables for checking the validity of each permutation. The space needed does not scale with the input digits themselves because there are always only four. Therefore, the auxiliary space complexity is constant.

Optimal Solution

Approach

Instead of checking every possible time combination, we'll construct the largest possible time by carefully selecting the digits one by one. We'll focus on making the largest valid choices for each position, ensuring we build a valid time as we go.

Here's how the algorithm would work step-by-step:

First, try to place the largest possible digit (2 or less) in the first (hours tens) position. If no such digit exists, then no valid time can be formed.
Next, based on the choice for the first digit, decide the possible choices for the second (hours ones) position. If the first digit was a '2', then the largest possible digit for this second position is '3' or less; otherwise (first digit was 0 or 1), any digit (0 to 9) is permissible. Pick the largest possible choice.
Then, try to put the largest valid number (5 or less) in the third (minutes tens) position. If none of the remaining digits are five or less, no valid time can be constructed.
Finally, put the largest of the remaining available digits in the last (minutes ones) position. If there are no digits left, it means something went wrong earlier, and no time can be constructed.
If all of these steps are successfully completed, the resulting time is the largest valid time that can be constructed using the given digits.

Code Implementation

def largestTimeFromDigits(digits):
    from itertools import permutations

    largest_valid_time = ""

    for hour_tens, hour_ones, minute_tens, minute_ones in permutations(digits):
        hours = hour_tens * 10 + hour_ones
        minutes = minute_tens * 10 + minute_ones

        # Check if the generated time is valid.
        if hours < 24 and minutes < 60:
            time = "{}{}:{}{}".format(hour_tens, hour_ones, minute_tens, minute_ones)
            if time > largest_valid_time:
                largest_valid_time = time

    return largest_valid_time

def largestTimeFromDigitsOptimal(digits):
    digits.sort()

    # Function to find the largest possible digit
    def find_largest(max_digit, remaining_digits):
        for digit in sorted(remaining_digits, reverse=True):
            if digit <= max_digit:
                remaining_digits.remove(digit)
                return digit
        return -1

    remaining_digits = digits[:]

    # Try to choose the largest possible first digit (hours tens position).
    hour_tens = find_largest(2, remaining_digits)
    if hour_tens == -1:
        return ""

    # Next choose the largest possible second digit (hours ones position).
    hour_ones_max = 3 if hour_tens == 2 else 9
    hour_ones = find_largest(hour_ones_max, remaining_digits)
    if hour_ones == -1:
        return ""

    # Now, choose the largest possible third digit (minutes tens position).
    minute_tens = find_largest(5, remaining_digits)
    if minute_tens == -1:
        return ""

    # Finally, the last digit goes to the minutes ones position.
    minute_ones = remaining_digits[0]

    # Construct the time string
    return "{}{}:{}{}".format(hour_tens, hour_ones, minute_tens, minute_ones)

Big(O) Analysis

Time Complexity

O(1) – The input array always has a fixed size of 4. The algorithm involves a fixed number of steps: trying digits for each of the 4 time positions. For each position, we iterate through the available digits (at most 4) to find the largest valid one. Since the number of operations does not depend on the size of any variable input, it's a constant time operation.

Space Complexity

O(1) – The algorithm described operates directly on the input digits without creating any auxiliary data structures that scale with the input size. It involves selecting digits one by one, checking their validity, and constructing the time string, all of which can be done using a fixed number of variables to store intermediate results or track progress. Since the extra memory used remains constant irrespective of the number of digits (which is implicitly 4), the space complexity is O(1).

Edge Cases

Case	How to Handle
Empty input array or null input	Return an empty string or null to indicate no valid time can be formed.
Input array contains digits that cannot form a valid time (e.g., [9, 9, 9, 9])	Return an empty string or 'Invalid Time' to denote that no valid time is possible.
Input array contains negative numbers	Treat negative numbers as invalid input and return an empty string, as time digits cannot be negative.
Input array contains numbers greater than 9	Treat numbers greater than 9 as invalid input and return an empty string because valid time digits are 0-9.
Multiple valid times can be formed; the algorithm should find the largest	Ensure the algorithm explores all permutations to find the maximum valid time by comparing each generated time.
Input array contains duplicate digits that are crucial for forming a valid time (e.g. [1, 1, 2, 3])	The algorithm must correctly handle duplicate digits when generating permutations and consider all possible combinations.
The largest possible time is 00:00	If the input can only form the time 00:00, it should be returned as the largest valid time.
All permutations are checked efficiently without redundant computations, particularly with larger input sets	Employ backtracking with pruning to avoid exploring invalid time combinations and increase efficiency.

Empty input array or null input

How to Handle:

Return an empty string or null to indicate no valid time can be formed.

Input array contains digits that cannot form a valid time (e.g., [9, 9, 9, 9])

How to Handle:

Return an empty string or 'Invalid Time' to denote that no valid time is possible.

Input array contains negative numbers

How to Handle:

Treat negative numbers as invalid input and return an empty string, as time digits cannot be negative.

Input array contains numbers greater than 9

How to Handle:

Treat numbers greater than 9 as invalid input and return an empty string because valid time digits are 0-9.

Multiple valid times can be formed; the algorithm should find the largest

How to Handle:

Ensure the algorithm explores all permutations to find the maximum valid time by comparing each generated time.

Input array contains duplicate digits that are crucial for forming a valid time (e.g. [1, 1, 2, 3])

How to Handle:

The algorithm must correctly handle duplicate digits when generating permutations and consider all possible combinations.

The largest possible time is 00:00

How to Handle:

If the input can only form the time 00:00, it should be returned as the largest valid time.

All permutations are checked efficiently without redundant computations, particularly with larger input sets

How to Handle:

Employ backtracking with pruning to avoid exploring invalid time combinations and increase efficiency.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Are the digits in the input array guaranteed to be between 0 and 9 inclusive?
If it's not possible to form a valid 24-hour time, what should I return (e.g., an empty string, null, or a specific error message)?
Can the input array contain duplicate digits, and if so, how should that be handled when constructing the largest time?
Is the input array always guaranteed to contain exactly four digits?
If multiple valid times can be formed, should I return the lexicographically largest, or is any valid time acceptable?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Take the four given digits and start arranging them in every possible order.
For each arrangement, treat the first two digits as the hour and the last two as the minutes.
Check if the hour is between 00 and 23, and if the minutes are between 00 and 59.
If the hour and minutes are both valid, then this arrangement is a possible time.
If the possible time is larger than the largest valid time we've seen so far, remember this new time.
Repeat this process for every single arrangement of the four digits.
After trying all the arrangements, the largest valid time that we remembered is the answer.

Code Implementation

import itertools

def largest_time_from_digits(digits):
    largest_valid_time = ""
    
    # Generate all possible permutations of the digits
    for permutation in itertools.permutations(digits):
        hour = permutation[0] * 10 + permutation[1]
        minute = permutation[2] * 10 + permutation[3]
        
        # Only proceed if the current permutation forms a valid time
        if 0 <= hour <= 23 and 0 <= minute <= 59:

            time = "{0:02d}:{1:02d}".format(hour, minute)

            # Check if the new valid time is larger than the current largest
            if largest_valid_time == "" or time > largest_valid_time:
                largest_valid_time = time

    return largest_valid_time

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, try to place the largest possible digit (2 or less) in the first (hours tens) position. If no such digit exists, then no valid time can be formed.
Next, based on the choice for the first digit, decide the possible choices for the second (hours ones) position. If the first digit was a '2', then the largest possible digit for this second position is '3' or less; otherwise (first digit was 0 or 1), any digit (0 to 9) is permissible. Pick the largest possible choice.
Then, try to put the largest valid number (5 or less) in the third (minutes tens) position. If none of the remaining digits are five or less, no valid time can be constructed.
Finally, put the largest of the remaining available digits in the last (minutes ones) position. If there are no digits left, it means something went wrong earlier, and no time can be constructed.
If all of these steps are successfully completed, the resulting time is the largest valid time that can be constructed using the given digits.

Code Implementation

def largestTimeFromDigits(digits):
    from itertools import permutations

    largest_valid_time = ""

    for hour_tens, hour_ones, minute_tens, minute_ones in permutations(digits):
        hours = hour_tens * 10 + hour_ones
        minutes = minute_tens * 10 + minute_ones

        # Check if the generated time is valid.
        if hours < 24 and minutes < 60:
            time = "{}{}:{}{}".format(hour_tens, hour_ones, minute_tens, minute_ones)
            if time > largest_valid_time:
                largest_valid_time = time

    return largest_valid_time

def largestTimeFromDigitsOptimal(digits):
    digits.sort()

    # Function to find the largest possible digit
    def find_largest(max_digit, remaining_digits):
        for digit in sorted(remaining_digits, reverse=True):
            if digit <= max_digit:
                remaining_digits.remove(digit)
                return digit
        return -1

    remaining_digits = digits[:]

    # Try to choose the largest possible first digit (hours tens position).
    hour_tens = find_largest(2, remaining_digits)
    if hour_tens == -1:
        return ""

    # Next choose the largest possible second digit (hours ones position).
    hour_ones_max = 3 if hour_tens == 2 else 9
    hour_ones = find_largest(hour_ones_max, remaining_digits)
    if hour_ones == -1:
        return ""

    # Now, choose the largest possible third digit (minutes tens position).
    minute_tens = find_largest(5, remaining_digits)
    if minute_tens == -1:
        return ""

    # Finally, the last digit goes to the minutes ones position.
    minute_ones = remaining_digits[0]

    # Construct the time string
    return "{}{}:{}{}".format(hour_tens, hour_ones, minute_tens, minute_ones)

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty input array or null input	Return an empty string or null to indicate no valid time can be formed.
Input array contains digits that cannot form a valid time (e.g., [9, 9, 9, 9])	Return an empty string or 'Invalid Time' to denote that no valid time is possible.
Input array contains negative numbers	Treat negative numbers as invalid input and return an empty string, as time digits cannot be negative.
Input array contains numbers greater than 9	Treat numbers greater than 9 as invalid input and return an empty string because valid time digits are 0-9.
Multiple valid times can be formed; the algorithm should find the largest	Ensure the algorithm explores all permutations to find the maximum valid time by comparing each generated time.
Input array contains duplicate digits that are crucial for forming a valid time (e.g. [1, 1, 2, 3])	The algorithm must correctly handle duplicate digits when generating permutations and consider all possible combinations.
The largest possible time is 00:00	If the input can only form the time 00:00, it should be returned as the largest valid time.
All permutations are checked efficiently without redundant computations, particularly with larger input sets	Employ backtracking with pruning to avoid exploring invalid time combinations and increase efficiency.

Empty input array or null input

How to Handle:

Return an empty string or null to indicate no valid time can be formed.

Input array contains digits that cannot form a valid time (e.g., [9, 9, 9, 9])

How to Handle:

Return an empty string or 'Invalid Time' to denote that no valid time is possible.

Input array contains negative numbers

How to Handle:

Treat negative numbers as invalid input and return an empty string, as time digits cannot be negative.

Input array contains numbers greater than 9

How to Handle:

Treat numbers greater than 9 as invalid input and return an empty string because valid time digits are 0-9.

Multiple valid times can be formed; the algorithm should find the largest

How to Handle:

Ensure the algorithm explores all permutations to find the maximum valid time by comparing each generated time.

Input array contains duplicate digits that are crucial for forming a valid time (e.g. [1, 1, 2, 3])

How to Handle:

The algorithm must correctly handle duplicate digits when generating permutations and consider all possible combinations.

The largest possible time is 00:00

How to Handle:

If the input can only form the time 00:00, it should be returned as the largest valid time.

All permutations are checked efficiently without redundant computations, particularly with larger input sets

How to Handle:

Employ backtracking with pruning to avoid exploring invalid time combinations and increase efficiency.