949. Largest Time for Given Digits #

Problem #

Given an array of 4 digits, return the largest 24 hour time that can be made.

The smallest 24 hour time is 00:00, and the largest is 23:59. Starting from 00:00, a time is larger if more time has elapsed since midnight.

Return the answer as a string of length 5. If no valid time can be made, return an empty string.

Example 1:

Input: [1,2,3,4]
Output: "23:41"

Example 2:

Input: [5,5,5,5]
Output: ""

Note:

A.length == 4
0 <= A[i] <= 9

Problem Summary #

Given an array composed of 4 digits, return the largest valid 24-hour time that can be set. The smallest 24-hour time is 00:00, and the largest is 23:59. Starting from 00:00 (midnight), the more time has elapsed, the larger the time. Return the answer as a string of length 5. If no valid time can be determined, return an empty string.

Solution Approach #

Given 4 digits, return a string representing the largest 24-hour time that can be formed from these 4 digits.
This is an easy problem; brute-force enumeration is sufficient. Check each permutation and combination of the given 4 digits in turn to see whether it is a valid time. For example, check whether 10 * A[i] + A[j] is less than 24, and whether 10 * A[k] + A[l] is less than 60. If it is valid and greater than the current maximum time, update this maximum time.

Code #


package leetcode

import "fmt"

func largestTimeFromDigits(A []int) string {
	flag, res := false, 0
	for i := 0; i < 4; i++ {
		for j := 0; j < 4; j++ {
			if i == j {
				continue
			}
			for k := 0; k < 4; k++ {
				if i == k || j == k {
					continue
				}
				l := 6 - i - j - k
				hour := A[i]*10 + A[j]
				min := A[k]*10 + A[l]
				if hour < 24 && min < 60 {
					if hour*60+min >= res {
						res = hour*60 + min
						flag = true
					}
				}
			}
		}
	}
	if flag {
		return fmt.Sprintf("%02d:%02d", res/60, res%60)
	} else {
		return ""
	}
}