Largest Time for Given Digits - Practice Coding Problems

Largest Time for Given Digits - 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
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.

Input & Output

Example 1 — Basic Case

$ Input: arr = [1,2,3,4]

› Output: 23:41

💡 Note: The largest valid time is 23:41. We use digits 2,3 for hours (23 ≤ 23) and digits 4,1 for minutes (41 ≤ 59).

Example 2 — No Valid Time

$ Input: arr = [5,5,5,5]

› Output: ""

💡 Note: No valid time can be formed. The smallest hour would be 55:55, but 55 > 23 for hours and 55 > 59 for minutes.

Example 3 — Edge Case with Zeros

$ Input: arr = [0,0,0,2]

› Output: 20:00

💡 Note: The largest valid time is 20:00. We use 2,0 for hours (20 ≤ 23) and 0,0 for minutes (00 ≤ 59).

Constraints

arr.length == 4
0 ≤ arr[i] ≤ 9

Visualization

Tap to expand

Understanding the Visualization

Input

Array of 4 digits: [1,2,3,4]

Process

Try all arrangements to form HH:MM format

Output

Return largest valid time: 23:41

Key Takeaway

🎯 Key Insight: With only 4 digits, we can check all 24 permutations to find the maximum valid time

Asked in

G Google 45 f Facebook 32 a Amazon 28

The key insight is that with only 4 digits, there are exactly 4! = 24 possible arrangements to check. We can generate all permutations and find the maximum valid time, or work backwards from 23:59 to find the first valid time. Best approach is brute force permutation for simplicity. Time: O(1), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Optimized - Sort and Generate Greedily	O(1)	O(1)	Sort digits and try to construct the largest time by placing largest valid digits first
Backtracking - Build Time Position by Position	O(1)	O(1)	Systematically place digits in HH:MM positions with early pruning of invalid combinations
Brute Force - Try All Permutations	O(1)	O(1)	Generate all 24 permutations of the 4 digits and check each for valid time format

Optimized - Sort and Generate Greedily — Algorithm Steps

Sort digits in descending order
Try to form hour starting with largest possible first digit (2 if available)
For second hour digit, use largest that keeps hour ≤ 23
For minutes, use largest remaining digits that keep minutes ≤ 59
If no valid combination, try next possible hour format

Visualization

Tap to expand

Step-by-Step Walkthrough

Start from 23:59

Try the latest possible time first

Check Digit Availability

See if we can form this time with available digits

First Valid = Maximum

First valid time found is the answer

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

int compare(const void* a, const void* b) {
    return (*(int*)b - *(int*)a); // Descending order
}

bool canFormTime(int arr[], int h1, int h2, int m1, int m2) {
    int digitsNeeded[] = {h1, h2, m1, m2};
    bool used[4] = {false};
    
    for (int i = 0; i < 4; i++) {
        int digit = digitsNeeded[i];
        bool found = false;
        for (int j = 0; j < 4; j++) {
            if (!used[j] && arr[j] == digit) {
                used[j] = true;
                found = true;
                break;
            }
        }
        if (!found) return false;
    }
    return true;
}

char* solution(int arr[]) {
    static char result[6];
    qsort(arr, 4, sizeof(int), compare);
    
    // Try hours from 23 down to 00
    for (int hour = 23; hour >= 0; hour--) {
        int h1 = hour / 10;
        int h2 = hour % 10;
        
        // Try minutes from 59 down to 00
        for (int minute = 59; minute >= 0; minute--) {
            int m1 = minute / 10;
            int m2 = minute % 10;
            
            if (canFormTime(arr, h1, h2, m1, m2)) {
                sprintf(result, "%02d:%02d", hour, minute);
                return result;
            }
        }
    }
    
    strcpy(result, "");
    return result;
}

int main() {
    char line[100];
    fgets(line, sizeof(line), stdin);
    
    int arr[4];
    char* ptr = strchr(line, '[') + 1;
    for (int i = 0; i < 4; i++) {
        arr[i] = strtol(ptr, &ptr, 10);
        if (i < 3) ptr = strchr(ptr, ',') + 1;
    }
    
    char* result = solution(arr);
    printf("%s\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(1)

Fixed small number of digit arrangements to try

✓ Linear Growth

Space Complexity

O(1)

Only using arrays to track digit usage and sorting

✓ Linear Space

28.4K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Optimized - Sort and Generate Greedily — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler