LeetCode | Largest Time for Given Digits

Largest Time for Given Digits

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.

Example 3:

Input: arr = [0,0,0,0]
Output: "00:00"

Example 4:

Input: arr = [0,0,1,0]
Output: "10:00"

Constraints:

 `arr.length == 4`
 `0 <= arr[i] <= 9`

Let’s start

Our main goal is to solve the problem and at the same time achieve the best linear time complexity with minimal space complexity. If you are a beginner to problem solving or trying data structure problems, I suggest you start with a brute force approach and then try to optimize your solution to the best time/space complexity.

Analysis

Let’s start analysing the problem statement. Given the array of 4 digits, we need to find out the latest 24-hour time that can be made using each digit “only once”.

• Before jumping into a solution or pseudocode, read the problem statement a couple of times and make sure to understand it well.

• Based on the problem statement, we understand that we need to compute all the possible combinations of the four digits to find the answer. This will give us a hint immediately that this problem falls under “Dynamic Programming”. It’s a very interesting topic to learn all the different approaches to tackle these kind of similar “Permutation & Combination” problems.

• Try to identify the keywords like “each digit” can be used “only once”. This is our first clue. We exactly have four digits to make our “hh:mm” latest hour (final answer).
• Second clue we can think of is to check each digit or hold the digit occurrences of all hh:mm combinations to compare with the array to get our final answer.
• Since we want the latest hour, max hour and minute in a day (24 hour time format) we need to start from the max (23 hr and 59 minute respectively) and iterate backwards to get the latest hour.

So with all these hints and analysis, let’s start writing our algorithm or pseudocode.

Algorithm | Pseudocode

• Start iterating from the max hour:minute max time (23:59) and hold all of the 4 digits combinations for each iteration
• Initialise a latest_hour boolean flag at the start to “true”.
• If the 4 digits of the single iteration not matching with the 4 elements of the input array, we have not reached the latest_hour. So set the latest_hour flag to false.
• Iterate and continue till we find the latest hour. i.e until the 4 digits combinations match with the 4 elements of the array.

Let’s start writing the solution.

Loop through every hour and digit combination. If we find the exact
four array elements. That’s it. That is our answer.
The Latest 24-hour Time!

Solution (in Java)

class Solution {
    public String largestTimeFromDigits(int[] arr) {

      for(int hour = 23; hour >= 0; hour--) {
            for(int minute = 59; minute >= 0; minute--) {
                
                boolean latest_hour = true;
                int[] count = new int[10];
                
                count[hour < 10 ? 0 : hour / 10]++;
                count[hour < 10 ? hour : hour % 10]++;
                count[minute < 10 ? 0 : minute / 10]++;
                count[minute < 10 ? minute : minute % 10]++;                

               for(int item : arr) {
                    if(--count[item] < 0) {
                        latest_hour = false;
                        break;
                    }
                }
                
                if(latest_hour) 
                  return String.format("%02d:%02d", hour, minute);
            }
        }
        
        return "";
        
    }
}

Complexity

Time Complexity => O(23 x 59 x 4) ==> O(1)
Space Complexity => O(1)

Conclusion

This problem is a very good example of Dynamic Programing. Do check out for more examples in this category for further learning. Dynamic Programming has two methods, Top-down and Bottom-up approach. Be on the lookout for a future article where I explain the two and their differences!

References

The LeetCode Problem in this article:

https://leetcode.com/problems/largest-time-for-given-digits/

Thanks for reading this post!

I hope this article is informative and helpful in some way. If it is, please like and share! Follow me on Twitter | LinkedIn for related content.

Happy learning!