Algorithm
Problem Name: 949. Largest Time for Given Digits
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 == 40 <= arr[i] <= 9
Code Examples
#1 Code Example with Java Programming
Code -
Java Programming
class Solution {
public String largestTimeFromDigits(int[] arr) {
int[] maxTime = {-1};
permute(arr, 0, maxTime);
return maxTime[0] == -1 ? "" : String.format("%02d:%02d", maxTime[0] / 60, maxTime[0] % 60);
}
private void permute(int[] arr, int idx, int[] maxTime) {
if (idx == arr.length) {
buildTime(arr, maxTime);
return;
}
for (int i = idx; i < arr.length; i++) {
swap(arr, i, idx);
permute(arr, idx + 1, maxTime);
swap(arr, idx, i);
}
}
private void buildTime(int[] arr, int[] maxTime) {
int hour = arr[0] * 10 + arr[1];
int minutes = arr[2] * 10 + arr[3];
if (hour < 24 && minutes < 60) {
maxTime[0] = Math.max(maxTime[0], hour * 60 + minutes);
}
}
private void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
Input
Output
#2 Code Example with Javascript Programming
Code -
Javascript Programming
const largestTimeFromDigits = function(A) {
let ans = "";
for (let i = 0; i < 4; ++i) {
for (let j = 0; j < 4; ++j) {
for (let k = 0; k < 4; ++k) {
// avoid duplicate among i, j & k.
if (i == j || i == k || j == k) continue;
// hour, minutes, & time.
let h = "" + A[i] + A[j], m = "" + A[k] + A[6 - i - j - k], t = h + ":" + m;
// hour < 24; minute < 60; update result.
if (h < "24" && m < "60" && ans < t) ans = t;
}
}
}
return ans;
};
Input
Output
#3 Code Example with Python Programming
Code -
Python Programming
class Solution:
def largestTimeFromDigits(self, A):
h = m = -float("inf")
for n1, n2, n3, n4 in itertools.permutations(A):
hh, mm = n1 * 10 + n2, n3 * 10 + n4
if 0 <= hh <= 23 and 0 <= mm <= 59 and (hh > h or hh == h and mm > m):
h, m = hh, mm
sh = str(h) if h > 9 else "0" + str(h)
sm = str(m) if m > 9 else "0" + str(m)
return 0 <= h <= 23 and 0 <= m <= 59 and sh + ":" + sm or ""
Input
Output
#4 Code Example with C# Programming
Code -
C# Programming
using System;
namespace LeetCode
{
public class _0949_LargestTimeForGivenDigits
{
public string LargestTimeFromDigits(int[] A)
{
int ans = -1;
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;
int l = 6 - i - j - k;
int hours = 10 * A[i] + A[j];
int mins = 10 * A[k] + A[l];
if (hours < 24 && mins < 60)
ans = Math.Max(ans, hours * 60 + mins);
}
}
return ans >= 0 ? $"{ans / 60:D2}:{ans % 60:D2}" : "";
}
}
}
Input
Output