DEV Community

Cover image for LeetCode | Largest Time for Given Digits
geetcloud
geetcloud

Posted on • Edited on • Originally published at geetcloud.blogspot.com

2 2

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.
Enter fullscreen mode Exit fullscreen mode

Example 2:

Input: arr = [5,5,5,5]
Output: ""
Explanation: There are no valid 24-hour times as "55:55" is not valid.
Enter fullscreen mode Exit fullscreen mode

Example 3:

Input: arr = [0,0,0,0]
Output: "00:00"
Enter fullscreen mode Exit fullscreen mode

Example 4:

Input: arr = [0,0,1,0]
Output: "10:00"
Enter fullscreen mode Exit fullscreen mode

Constraints:

 `arr.length == 4`
 `0 <= arr[i] <= 9`
Enter fullscreen mode Exit fullscreen mode

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".

thinking

  • 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.

White Simple Music Icon Etsy Banner (3).png

  • 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 "";
        }
    }
Enter fullscreen mode Exit fullscreen mode

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!

Happy learning!

Quickstart image

Django MongoDB Backend Quickstart! A Step-by-Step Tutorial

Get up and running with the new Django MongoDB Backend Python library! This tutorial covers creating a Django application, connecting it to MongoDB Atlas, performing CRUD operations, and configuring the Django admin for MongoDB.

Watch full video →

Top comments (0)

Jetbrains image

Is Your CI/CD Server a Prime Target for Attack?

57% of organizations have suffered from a security incident related to DevOps toolchain exposures. It makes sense—CI/CD servers have access to source code, a highly valuable asset. Is yours secure? Check out nine practical tips to protect your CI/CD.

Learn more

👋 Kindness is contagious

Explore a trove of insights in this engaging article, celebrated within our welcoming DEV Community. Developers from every background are invited to join and enhance our shared wisdom.

A genuine "thank you" can truly uplift someone’s day. Feel free to express your gratitude in the comments below!

On DEV, our collective exchange of knowledge lightens the road ahead and strengthens our community bonds. Found something valuable here? A small thank you to the author can make a big difference.

Okay