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 == 4
  • 0 <= 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;
  }
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
arr = [1,2,3,4]

Output

x
+
cmd
"23:41"

#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;
};
Copy The Code & Try With Live Editor

Input

x
+
cmd
arr = [1,2,3,4]

Output

x
+
cmd
"23:41"

#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 ""
Copy The Code & Try With Live Editor

Input

x
+
cmd
arr = [5,5,5,5]

Output

x
+
cmd
""

#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}" : "";
        }
    }
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
arr = [5,5,5,5]

Output

x
+
cmd
""
Advertisements

Demonstration


Previous
#948 Leetcode Bag of Tokens Solution in C, C++, Java, JavaScript, Python, C# Leetcode
Next
#950 Leetcode Reveal Cards In Increasing Order Solution in C, C++, Java, JavaScript, Python, C# Leetcode