# Largest Time for Given Digits
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/largest-time-for-given-digits)
Canonical: https://scaleengineer.com/dsa/problems/largest-time-for-given-digits
**Patterns:** [Backtracking](https://scaleengineer.com/dsa/patterns/backtracking), [Enumeration](https://scaleengineer.com/dsa/patterns/enumeration)
**Data structures:** Array, String
**Companies:** [LiveRamp](https://scaleengineer.com/companies/liveramp)
---
## 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`, 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`

# Approaches
## Brute-force by Iterating Through Time
This approach iterates through all possible 24-hour times, from the latest (`23:59`) to the earliest (`00:00`). For each time, it checks if the digits required to form that time can be constructed from the given input digits. The first valid time found is guaranteed to be the latest possible one because of the descending order of iteration.
**Time:** O(1). The loops run a fixed number of times (24 * 60 = 1440). Inside the loop, the operations (creating and comparing frequency arrays) take constant time. · **Space:** O(1). We use a constant amount of extra space for the frequency arrays (e.g., an integer array of size 10).
**Pros:** Simple to understand and implement.; Correctly finds the latest time by its nature of iterating downwards.
**Cons:** Performs a relatively large number of checks (up to 24 * 60 = 1440), which is less efficient than exploring the small search space of permutations of the input digits.
### Explanation
The algorithm iterates through hours from 23 down to 0, and for each hour, it iterates through minutes from 59 down to 0. For a given time `HH:MM`, we determine the four digits required: `H/10`, `H%10`, `M/10`, and `M%10`. We then check if this set of four digits is a permutation of the input `arr`. This check can be done efficiently by using frequency counts. We first create a frequency map (or an array of size 10) for the digits in the input `arr`. Then, for the current time `HH:MM`, we create a frequency map of its constituent digits. If the two frequency maps are identical, it means we can form this time. Since we are iterating downwards, this is the latest possible time. We format it as `"HH:MM"` and return. If the loops complete without finding a match, it means no valid time can be formed, so we return an empty string.

```java
import java.util.Arrays;

class Solution {
    public String largestTimeFromDigits(int[] arr) {
        int[] counts = new int[10];
        for (int digit : arr) {
            counts[digit]++;
        }

        for (int h = 23; h >= 0; h--) {
            for (int m = 59; m >= 0; m--) {
                int[] requiredCounts = new int[10];
                requiredCounts[h / 10]++;
                requiredCounts[h % 10]++;
                requiredCounts[m / 10]++;
                requiredCounts[m % 10]++;

                if (Arrays.equals(counts, requiredCounts)) {
                    return String.format("%02d:%02d", h, m);
                }
            }
        }
        return "";
    }
}
```
### Algorithm
- Create a frequency count (e.g., an array of size 10) of the digits in the input array `arr`.
- Loop for hours `h` from 23 down to 0.
- Inside the hour loop, loop for minutes `m` from 59 down to 0.
- For the current time `h:m`, determine the four digits required: `d1 = h/10`, `d2 = h%10`, `d3 = m/10`, `d4 = m%10`.
- Create a frequency count of these four required digits.
- Compare the frequency count of the required digits with the frequency count of the input `arr`.
- If the counts match, it means this time can be formed. Since we are iterating downwards from the latest possible time, this is our answer. Format the time as `String.format("%02d:%02d", h, m)` and return it.
- If the loops complete without finding any match, it means no valid time can be constructed. Return an empty string `""`.

## Generate All Permutations
Since the input is a small, fixed-size array of 4 digits, we can generate all possible arrangements (permutations) of these digits. There are 4! = 24 such permutations. For each permutation, we form a time and check if it's valid. We keep track of the latest valid time found across all permutations.
**Time:** O(1). The number of permutations is fixed at 4! = 24. For each permutation, we perform a constant number of operations. Thus, the complexity is constant. · **Space:** O(1). We only use a few variables to store the current permutation and the best time found so far.
**Pros:** Very efficient as it explores the minimal search space of 24 possibilities.; Conceptually straightforward for a fixed small number of items.
**Cons:** The implementation with nested loops can look a bit verbose. A recursive permutation generator might be cleaner but adds recursion overhead.; This approach does not scale well if the number of digits were larger (e.g., for `n` digits, it would be O(n!)). However, for this problem's constraints, it's perfect.
### Explanation
The core of this approach is to generate all 24 permutations of the input array `arr`. This can be done using four nested loops or a recursive backtracking algorithm. For each permutation, say `[d1, d2, d3, d4]`, we construct the hours `HH = d1 * 10 + d2` and minutes `MM = d3 * 10 + d4`. We then validate this time: `HH` must be in the range `[0, 23]` and `MM` must be in the range `[0, 59]`. If the time is valid, we compare it with the latest valid time found so far. We can store the time as a string `"HH:MM"` and use string comparison, or as an integer representing the total minutes (`HH * 60 + MM`) for easier comparison. We initialize our "best time" to a sentinel value (e.g., an empty string). After checking all 24 permutations, if we have found a valid time, we format and return it. Otherwise, we return an empty string.

```java
class Solution {
    public String largestTimeFromDigits(int[] arr) {
        String result = "";
        // Iterate through all 4! = 24 permutations
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 4; j++) {
                if (j == i) continue;
                for (int k = 0; k < 4; k++) {
                    if (k == i || k == j) continue;
                    
                    // The last index l is the one not used yet.
                    // The sum of indices 0,1,2,3 is 6. So l = 6 - i - j - k.
                    int l = 6 - i - j - k;

                    int h = arr[i] * 10 + arr[j];
                    int m = arr[k] * 10 + arr[l];

                    if (h < 24 && m < 60) {
                        String currentTime = String.format("%02d:%02d", h, m);
                        if (result.isEmpty() || currentTime.compareTo(result) > 0) {
                            result = currentTime;
                        }
                    }
                }
            }
        }
        return result;
    }
}
```
### Algorithm
- Initialize a variable `maxTime` to -1 to store the maximum time found so far, represented in total minutes from midnight.
- Generate all permutations of the input `arr`. A simple way is to use four nested loops with indices `i, j, k, l` from 0 to 3, ensuring `i, j, k, l` are all distinct.
- For each permutation `(arr[i], arr[j], arr[k], arr[l])`:
  - Form hours `h = arr[i] * 10 + arr[j]`.
  - Form minutes `m = arr[k] * 10 + arr[l]`.
  - Check if the time is valid: `h < 24` and `m < 60`.
  - If valid, update `maxTime = max(maxTime, h * 60 + m)`.
- After checking all permutations, if `maxTime` is still -1, no valid time was found, so return `""`.
- Otherwise, convert `maxTime` back to `"HH:MM"` format and return it. `HH = maxTime / 60`, `MM = maxTime % 60`.

# Solutions
### Java

```java
class Solution {
public
  String largestTimeFromDigits(int[] arr) {
    int ans = -1;
    for (int i = 0; i < 4; ++i) {
      for (int j = 0; j < 4; ++j) {
        for (int k = 0; k < 4; ++k) {
          if (i != j && j != k && i != k) {
            int h = arr[i] * 10 + arr[j];
            int m = arr[k] * 10 + arr[6 - i - j - k];
            if (h < 24 && m < 60) {
              ans = Math.max(ans, h * 60 + m);
            }
          }
        }
      }
    }
    return ans < 0 ? "" : String.format("%02d:%02d", ans / 60, ans % 60);
  }
}

```

### CPP

```cpp
class Solution {
public:
  string largestTimeFromDigits(vector<int> &arr) {
    int ans = -1;
    for (int i = 0; i < 4; ++i) {
      for (int j = 0; j < 4; ++j) {
        for (int k = 0; k < 4; ++k) {
          if (i != j && j != k && i != k) {
            int h = arr[i] * 10 + arr[j];
            int m = arr[k] * 10 + arr[6 - i - j - k];
            if (h < 24 && m < 60) {
              ans = max(ans, h * 60 + m);
            }
          }
        }
      }
    }
    if (ans < 0)
      return "";
    int h = ans / 60, m = ans % 60;
    return to_string(h / 10) + to_string(h % 10) + ":" + to_string(m / 10) +
           to_string(m % 10);
  }
};

```

### Python

```python
class Solution:
    def largestTimeFromDigits(self, arr: List[int]) -> str: ans = - 1 for i in range(4): for j in range(4): for k in range(4): if i != j and i != k and j != k: h = arr[i] * 10 + arr[j] m = arr[k] * 10 + arr[6 - i - j - k] if h < 24 and m < 60: ans = max(ans, h * 60 + m) return '' if ans < 0 else f ' { ans // 60 : 02 } : { ans % 60 : 02 } '

```