In this post we will solve the LeetCode 949. Largest Time for Given Digits problem using the Java programming language and the VSCode IDE on a Windows computer.
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`di 24-hour time in "HH:MM" format. If no valid time can be made, return an empty string. Related Topics: o String o Enumeration
We are given an int[] array with four digits. We need to find the latest 24-hour time using exactly each digit once and return the results using the HH:MM format.
If interested in this problem please visit the associated LeetCode website and get the current version of the problem requirements. Once that is done we need to come up with an approach to solve it.
public String largestTimeFromDigits(int[] arr) {
}
The signature for the function of interest takes a single argument and returns the time as a string.
I will be solving the problem on my computer. When needed I will copy and paste the associated code into the IDE provided by LeetCode in order to submit it for evaluation. Unless you have a special requirement of having a test scaffold and the solution code in the same file, I suggest you solve it directly using the online IDE from LeetCode.
We will first develop a simple test scaffold which IS NOT PART OF THE SOLUTION!
1, 2, 3, 4 main <<< largestTimeFromDigits0: 23:41 main <<< largestTimeFromDigits: 23:41 2, 4, 6, 8 main <<< largestTimeFromDigits0: main <<< largestTimeFromDigits: 6, 5, 3, 2 main <<< largestTimeFromDigits0: 23:56 main <<< largestTimeFromDigits: 23:56 5,5,5,5 main <<< largestTimeFromDigits0: main <<< largestTimeFromDigits: 2, 5, 9, 3 main <<< largestTimeFromDigits0: 23:59 main <<< largestTimeFromDigits: 23:59 0, 0, 0, 0 main <<< largestTimeFromDigits0: 00:00 main <<< largestTimeFromDigits: 00:00 0,0,1,0 main <<< largestTimeFromDigits0: 10:00 main <<< largestTimeFromDigits: 10:00 1, 0, 0, 1 main <<< largestTimeFromDigits0: 11:00 main <<< largestTimeFromDigits: 11:00 1, 9, 6, 0 main <<< largestTimeFromDigits0: 19:06 main <<< largestTimeFromDigits: 19:06 2, 3, 4, 5 main <<< largestTimeFromDigits0: 23:54 main <<< largestTimeFromDigits: 23:54
Each test case is separated from others by two blank lines.
The first line represents the values for the input array. Our test scaffold reads the input line and populates an int[] with the specified values.
The test code seems to call two implementations of the function of interest. They seem to return the same value.
As I am writing this post I noticed that I omitted some messages from the test scaffold and from the implementations of the function of interest. I apologize for that. The code generating additional info used to follow the solutions has been commented out. We will see it shortly when we look at the code.
/**
* Test scaffold.
* !!! NOT PART OF SOLUTION !!
* @throws IOException
*/
public static void main(String[] args) throws IOException {
// **** open buffered reader ****
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// **** read int[] arr ****
int[] arr = Arrays.stream(br.readLine().trim().split(","))
.map(s -> s.trim())
.mapToInt(Integer::parseInt)
.toArray();
// **** close buffered reader ****
br.close();
// // ???? ????
// System.out.println("main <<< arr: " + Arrays.toString(arr));
// // ???? ????
// int[][] perms = new int[24][4];
// // ???? generate permutations ????
// ndx = 0;
// permute(arr, 0, perms);
// // ???? ????
// System.out.println("main <<< perms:");
// for (int i = 0; i < 24; i++)
// System.out.println(Arrays.toString(perms[i]));
// **** call function of interest and display output ****
System.out.println("main <<< largestTimeFromDigits0: " + largestTimeFromDigits0(arr));
// **** call function of interest and display output ****
System.out.println("main <<< largestTimeFromDigits: " + largestTimeFromDigits(arr));
}
The test scaffold reads the input line and populates the int[] `arr` array.
It seems that we declare the `perms` array and use `permute` to generate all the permutations possible using the values in the int[] `arr`. This code was used to test a faster implementation of the function that generates permutations using an int[] array versus one that uses an array list of lists.
The two implementations of the function of interest are called and their respective results are displayed.
Please note that any permutation of the input int[] `arr` would be equivalent given that we will be generating and checking all the permutations of the four integer values.
Our approach will be to generate all the permutations for the specified set of four integers. We will then iterate through the permutations looking for the one that holds the latest 24-hour time in “HH:MM” format.
/**
* Given an array arr of 4 digits,
* find the latest 24-hour time that can be made using each digit exactly once.
*
* Runtime: 16 ms, faster than 40.20% of Java online submissions.
* Memory Usage: 39.1 MB, less than 47.51% of Java online submissions.
*
* 172 / 172 test cases passed.
* Status: Accepted
* Runtime: 16 ms
* Memory Usage: 39.1 MB
*/
static public String largestTimeFromDigits0(int[] arr) {
// **** initialization ****
int latest = 0;
Integer[] array = new Integer[arr.length];
for (int i = 0; i < arr.length; i++)
array[i] = arr[i];
// ???? ????
// System.out.println("<<< array: " + Arrays.toString(array));
// **** declare list of permutations ****
ArrayList<Integer[]> perms = new ArrayList<>();
// **** generate permutations ****
permute(Arrays.asList(array), 0, perms);
// ???? ????
// System.out.println("<<< perms:");
// for (Integer[] a : perms)
// System.out.println(Arrays.toString(a));
// **** check if we cannot gereate a valid time ****
if (perms.size() == 0) return "";
// **** iterate though the list of permutations ****
for (int i = 0; i < perms.size(); i++) {
// **** for ease of use ****
Integer[] a = perms.get(i);
// ???? ????
// System.out.println("<<< a: " + Arrays.toString(a));
// **** convert array to integer ****
int arrVal = 0;
for (int j = 0; j < 4; j++) {
arrVal *= 10;
arrVal += a[j];
}
// **** skip values > 2359 ****
if (arrVal > 2359) continue;
// **** skip minutes > 59 ****
if (arrVal % 100 > 59) continue;
// **** return 00:00 ****
if (arrVal == 0) return "00:00";
// ???? ????
// System.out.println("<<< arrVal: " + arrVal);
// **** update latest time ****
latest = latest >= arrVal ? latest : arrVal;
}
// ???? ????
// System.out.println("<<< latest: " + latest);
// **** return "" or HH:MM string ****
if (latest == 0) return "";
return String.format("%02d:%02d", latest / 100, latest % 100);
}
This is the first implementation of the function of interest. We will be using lists to generate the permutations so we need to get from values in an int[] array to an ArrayList holding all the valid permutations in lists of type List<Integer>.
We start by initializing `latest` to 0. This variable will hold the integer representations of a time which we will use to generate the output string in “HH:MM” format.
We also create and populate the Integer[] array `array` which holds the same input values but in Integer, not int format. This is done to generate an ArrayList<Integer> permutations which we name `perms`.
We are now ready to populate the `perms` list using the `permute` auxiliary function.
If the `perms` list is empty, it implies that not a single permutation holds a valid time. In such a case, it is required to return the “” string.
Now we will loop over all the permutations in the `perms` list.
We get the current permutation in Integer[] array `a`.
We convert it to an int in the `larval` variable.
We now need to skip some values that are out of range.
If the value is set to 0, we need to return “00:00” to flag midnight.
Since we need to keep track of the latest time, we check if the `arrVal` holds a later time than `latest`. If so we update `latest`.
When all is said and done, if `latest` holds zero, we need to return “” to indicate that the set of input integers could not generate a valid 24-hour time; otherwise we return a string representation of the `latest` time in “HH:MM” format.
/**
* Generate permutations using a list.
* Recursive function.
*/
static void permute(List<Integer> lst, int k, List<Integer[]> perms) {
// **** generate permutations of k numbers ****
for (int i = k; i < lst.size(); i++) {
// **** swap elements ****
Collections.swap(lst, i, k);
// **** recurse ****
permute(lst, k + 1, perms);
// **** restore swap ****
Collections.swap(lst, k, i);
}
// **** add array to perms list ****
// if (k == lst.size() - 1 && lst.get(0) <= 2) {
if (k == lst.size() - 1) {
// **** convert list to array ****
Integer[] arr = lst.toArray(new Integer[lst.size()]);
// **** add array to perms list ****
perms.add(arr);
}
}
The `permute` auxiliary function takes as input a List<Integer> holding the four values, an integer `k` which represents the current value in the `lst` list, and a List<Integer> in which this function will return all permutations.
Please note this is a recursive function.
In the loop we swap two positions in the `lst` list, call recursively the `permute` function and then restore the values we swapped. Note that we call `recurse` indicating that we need to process the value at index `k`.
When the loop ends, we check if `k` has processed all four values. If so we convert the list to an Integer[] and add it to the `perms` list. The caller is set to process an Integer[] array.
/**
* Given an array arr of 4 digits,
* find the latest 24-hour time that can be made using each digit exactly once.
*
* Runtime: 9 ms, faster than 86.38% of Java online submissions for Largest Time for Given Digits.
* Memory Usage: 37.1 MB, less than 84.39% of Java online submissions for Largest Time for Given Digits.
*
* 172 / 172 test cases passed.
* Status: Accepted
* Runtime: 9 ms
* Memory Usage: 37.1 MB
*/
static public String largestTimeFromDigits(int[] arr) {
// **** initialization ****
int latest = 0;
// **** declare array of permutations ****
int[][] perms = new int[24][4];
// **** generate permutations ****
// ndx = 0;
// permute(arr, 0, perms);
permute(arr, 0, perms, new int[1]);
// **** iterate though the list of permutations ****
for (int i = 0; i < 24; i++) {
// **** for ease of use ****
int[] a = perms[i];
// **** convert array to integer ****
int arrVal = 0;
for (int j = 0; j < 4; j++) {
arrVal *= 10;
arrVal += a[j];
}
// **** skip these values ****
if (arrVal > 2359 || arrVal % 100 > 59) continue;
// **** return 00:00 ****
if (arrVal == 0) return "00:00";
// **** update latest time ****
latest = latest >= arrVal ? latest : arrVal;
}
// **** return "" or HH:MM string ****
if (latest == 0) return "";
return String.format("%02d:%02d", latest / 100, latest % 100);
}
This is the second implementation of the function of interest. Instead of representing the permutations using a List<Integer> we will represent them as int[] arrays.
We declare and initialize the `latest` variable and the `perms` int[] array.
The `perms` array is populated during the call to the `permute` auxiliary function. Note that a previous implementation used a global int `ndx` variable that needed to be initialized to zero before calling the `permute` function. We replaced it with an int[] array with a single value.
After the int[][] `perms` array is populated with all possible permutations, we traverse it converting the value in each permutation to int and storing it in the `arrVal` variable, discarding some values, returning the string “00:00”, or updating the `latest` variable. This is very similar to what we did in the previous implementation of the `permute` function.
When all is said and done we return the proper string representation of the latest time in 24-hour format.
// **** index into perms int[][] array...
// ...could / should made an argument (DONE) ****
// static int ndx = 0;
The `permute` second implementation used to use a global int `ndx` variable that needed to be initialized on each pass. We removed such value and added it as an int[] argument to the function.
/**
* Generate permutations using an array.
*
* Runtime: 9 ms, faster than 86.38% of Java online submissions.
* Memory Usage: 37.2 MB, less than 81.73% of Java online submissions.
*
* 172 / 172 test cases passed.
* Status: Accepted
* Runtime: 9 ms
* Memory Usage: 37.2 MB
*/
static void permute(int[] arr, int k, int[][] perms, int[] ndex) {
// **** generate permutations of k numbers ****
for (int i = k; i < 4; i++) {
// **** swap elements ****
swap(arr, i, k);
// int tmp = arr[i];
// arr[i] = arr[k];
// arr[k] = tmp;
// **** recurse ****
permute(arr, k + 1, perms, ndex);
// **** restore swap ****
swap(arr, k, i);
// tmp = arr[i];
// arr[i] = arr[k];
// arr[k] = tmp;
}
// **** add array to perms list ****
if (k == 3) {
// perms[ndx++] = Arrays.copyOf(arr, 4);
perms[ndex[0]++] = Arrays.copyOf(arr, 4);
}
}
This function is equivalent to the previous implementation but instead of using lists we now use int[] arrays. This is done in hopes we could reduce the runtime. At some point we tested using the `swap` function instead of the online code. It turns out that the `swap` function performed better.
/**
* Swap elements in array.
*/
static private void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
This is the implementation of the auxiliary function used to swap two values in the specified array.
Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository named LargestTimeForGivenDigits.
Please note that the code here presented might not be the best possible solution. After solving a problem, you should take a look at the best accepted solutions provided by the different websites (i.e., HackerRank, LeetCode to name a few). The idea is to learn concepts, not to memorize solutions.
If you have comments or questions regarding this, or any other post in this blog, please do not hesitate and leave me a note below. I will reply as soon as possible.
Keep on reading and experimenting. It is one of the best ways to learn, become proficient, refresh your knowledge and enhance your developer / engineering toolset.
Thanks for reading, feel free to connect with me John Canessa at LinkedIn.
Enjoy;
John