949. Largest Time for Given Digits

public class Solution {
    public string LargestTimeFromDigits(int[] arr) {
        Array.Sort(arr);
        int maxTime = -1;
        
        do {
            int hours = arr[0] * 10 + arr[1];
            int minutes = arr[2] * 10 + arr[3];
            if (hours < 24 && minutes < 60) {
                maxTime = Math.Max(maxTime, hours * 60 + minutes);
            }
        } while (NextPermutation(arr));
        
        if (maxTime == -1) {
            return "";
        }
        
        return String.Format("{0:D2}:{1:D2}", maxTime / 60, maxTime % 60);
    }
    
    private bool NextPermutation(int[] arr) {
        int n = arr.Length;
        int i = n - 2;
        while (i >= 0 && arr[i] >= arr[i + 1]) {
            i--;
        }
        if (i < 0) {
            return false;
        }
        int j = n - 1;
        while (arr[j] <= arr[i]) {
            j--;
        }
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
        Array.Reverse(arr, i + 1, n - i - 1);
        return true;
    }
}

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public string LargestTimeFromDigits(vector<int>& arr) {
        sort(arr.begin(), arr.end());
        int maxTime = -1;
        
        do {
            int hours = arr[0] * 10 + arr[1];
            int minutes = arr[2] * 10 + arr[3];
            if (hours < 24 && minutes < 60) {
                maxTime = max(maxTime, hours * 60 + minutes);
            }
        } while (NextPermutation(arr));
        
        if (maxTime == -1) {
            return "";
        }
        
        return String.Format("{0:D2}:{1:D2}", maxTime / 60, maxTime % 60);
    }
    
    private bool NextPermutation(vector<int>& arr) {
        int n = arr.size();
        int i = n - 2;
        while (i >= 0 && arr[i] >= arr[i + 1]) {
            i--;
        }
        if (i < 0) {
            return false;
        }
        int j = n - 1;
        while (arr[j] <= arr[i]) {
            j--;
        }
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
        Array.Reverse(arr, i + 1, n - i - 1);
        return true;
    }
}

import java.util.*;

class Solution {
    public String largestTimeFromDigits(int[] arr) {
        int maxTime = -1;
        List<int[]> permutations = new ArrayList<>();
        permute(arr, 0, permutations);
        
        for (int[] perm : permutations) {
            int hours = perm[0] * 10 + perm[1];
            int minutes = perm[2] * 10 + perm[3];
            if (hours < 24 && minutes < 60) {
                maxTime = Math.max(maxTime, hours * 60 + minutes);
            }
        }
        
        if (maxTime == -1) {
            return "";
        }
        
        String hours = String.format("%02d", maxTime / 60);
        String minutes = String.format("%02d", maxTime % 60);
        return hours + ":" + minutes;
    }
    
    private void permute(int[] nums, int start, List<int[]> res) {
        if (start == nums.length) {
            res.add(nums.clone());
            return;
        }
        for (int i = start; i < nums.length; i++) {
            swap(nums, start, i);
            permute(nums, start + 1, res);
            swap(nums, start, i);
        }
    }
    
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

from itertools import permutations

def largestTimeFromDigits(arr):
    max_time = -1
    for perm in permutations(arr):
        hours = perm[0] * 10 + perm[1]
        minutes = perm[2] * 10 + perm[3]
        if hours < 24 and minutes < 60:
            max_time = max(max_time, hours * 60 + minutes)
    if max_time == -1:
        return ""
    return f"{max_time // 60:02}:{max_time % 60:02}"

package main

import (
    "fmt"
    "sort"
)

func largestTimeFromDigits(arr []int) string {
    sort.Ints(arr)
    maxTime := -1
    
    for {
        hours := arr[0]*10 + arr[1]
        minutes := arr[2]*10 + arr[3]
        if hours < 24 && minutes < 60 {
            maxTime = max(maxTime, hours*60 + minutes)
        }
        if !nextPermutation(arr) {
            break
        }
    }
    
    if maxTime == -1 {
        return ""
    }
    
    return fmt.Sprintf("%02d:%02d", maxTime/60, maxTime%60)
}

func nextPermutation(arr []int) bool {
    n := len(arr)
    i := n - 2
    for i >= 0 && arr[i] >= arr[i+1] {
        i--
    }
    if i < 0 {
        return false
    }
    j := n - 1
    for arr[j] <= arr[i] {
        j--
    }
    arr[i], arr[j] = arr[j], arr[i]
    reverse(arr[i+1:])
    return true
}

func reverse(arr []int) {
    for i, j := 0, len(arr)-1; i < j; i, j = i+1, j-1 {
        arr[i], arr[j] = arr[j], arr[i]
    }
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

Explanation

Algorithm

Перебрать все возможные перестановки массива arr.

Проверить каждую перестановку, можно ли из нее составить допустимое 24-часовое время.

Найти самое позднее допустимое время среди всех перестановок.

Алгоритм

Перебрать все возможные перестановки массива arr.

Проверить каждую перестановку, можно ли из нее составить допустимое 24-часовое время.

Найти самое позднее допустимое время среди всех перестановок.

Вернуть найденное время в формате "HH

". Если допустимое время не найдено, вернуть пустую строку.

😎