In this post we will solve LeetCode 681. Next Closest Time problem using the Java programming language, the VSCode IDE on a Windows computer. Please note that the computer platform and the IDE should make no difference. One of the simplest ways to solve the problem is to use the online IDE provided by LeetCode.
Given a time represented in the format "HH:MM", form the next closest time by reusing the current digits. There is no limit on how many times a digit can be reused. You may assume the given input string is always valid. For example, "01:34", "12:09" are all valid. "1:34", "12:9" are all invalid. Constraints: * time.length == 5 * time is a valid time in the form "HH:MM". o 0 <= HH < 24 o 0 <= MM < 60 Related Topics: o String o Enumeration
We are given a string with a time expressed in 24-hour format. By reusing the digits as many times as needed, we need to form the next closest time.
If interested in this problem and wish to see a similar one, I invite you to take a look at the previous post LeetCode 949. Largest Time for Given Digits. You might get some inspiration on how to tackle the current problem.
public String nextClosestTime(String time) {
}
The signature for the function of interest is right on. The single argument is a string with a time expressed in “HH:MM” format and the returned value is a string.
Since I will be solving the problem in my Windows computer I will need to develop a simple test scaffold which will read the input time, generate the argument, call the function of interest, and display the result. Please note that the test code IS NOT PART OF THE SOLUTION!!!
19:34 main <<< time ==>19:34<== <<< minutes: 1174 <<< digits: [0, 1, 0, 1, 1, 0, 0, 0, 0, 1] main <<< nextClosestTime0: 19:39 <<< MINS_IN_DAY: 1440 <<< digits: [0, 1, 0, 1, 1, 0, 0, 0, 0, 1] <<< hh:mm: 19:34 main <<< nextClosestTime: 19:39 23:59 main <<< time ==>23:59<== <<< minutes: 1439 <<< digits: [0, 0, 1, 1, 0, 1, 0, 0, 0, 1] main <<< nextClosestTime0: 22:22 <<< MINS_IN_DAY: 1440 <<< digits: [0, 0, 1, 1, 0, 1, 0, 0, 0, 1] <<< hh:mm: 23:59 main <<< nextClosestTime: 22:22
The test cases are separated by two blank lines.
The first line in each test case contains the input time string expressed in HH:MM format.
Our test scaffold seems to read the input string, assign it to a variable named `time` and display it for us to verify that all is well so far.
A first implementation of the function of interest is called. Some intermediate lines are displayed to verify things are going as expected. Please note that such output IS NOT PART OF THE SOLUTION.
The result generated by the function of interest is then displayed.
The second implementation seems to follow the same pattern.
https://www.geeksforgeeks.org/var-keyword-in-java/ var keyword in Java The var keyword was introduced in Java 10. Type inference is used in var keyword in which it detects automatically the datatype of a variable based on the surrounding context.
While reading an article in GeeksforGeeks I decided to use in this and future posts the keyword `var`. If you see a reason for not doing so, please leave me a comment bellow.
/**
* Test scaffold.
* !!! NOT PART OF THE SOLUTION !!!
* @throws IOException
*/
public static void main(String[] args) throws IOException {
// **** open buffered reader ****
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// **** read time ****
String time = br.readLine().trim();
// **** close bufferered reader ****
br.close();
// ???? ????
System.out.println("main <<< time ==>" + time + "<==");
// **** call function of interest and display output ****
System.out.println("main <<< nextClosestTime0: " + nextClosestTime0(time));
// **** call function of interest and display output ****
System.out.println("main <<< nextClosestTime: " + nextClosestTime(time));
}
The test scaffold is quite simple and follows closely the description of the test cases. At this time I do not have much to add to the description of this code.
/**
* Given a time represented in the format "HH:MM",
* form the next closest time by reusing the current digits.
* There is no limit on how many times a digit can be reused.
*
* Runtime: 15 ms, faster than 16.99% of Java online submissions.
* Memory Usage: 39.6 MB, less than 16.58% of Java online submissions.
*
* 66 / 66 test cases passed.
* Status: Accepted
* Runtime: 15 ms
* Memory Usage: 39.6 MB
*/
static public String nextClosestTime0(String time) {
// **** minutes in a day ****
final var MINS_IN_DAY = 1440;
// **** initialization ****
var minutes = Integer.parseInt(time.substring(0, 2)) * 60;
minutes += Integer.parseInt(time.substring(3));
// ???? ????
System.out.println("<<< minutes: " + minutes);
// **** to keep track of the valid digits ****
var digits = new int[10];
for (char c : time.toCharArray()) {
// **** skip ':' ****
if (c == ':') continue;
// **** add this digit to the set ****
digits = 1;
}
// ???? ????
System.out.println("<<< digits: " + Arrays.toString(digits));
// **** loop until we find a valied time ****
var isValid = false;
while (!isValid) {
// **** move to the next minute or next day ****
minutes = minutes + 1 == MINS_IN_DAY ? 0 : minutes + 1;
// ??? ????
// System.out.println("<<< minutes: " + minutes);
// **** for ease of use ****
int[] nextTime = { minutes / 60 / 10,
minutes / 60 % 10,
minutes % 60 / 10,
minutes % 60 % 10};
// ???? ????
// System.out.println("<<< nextTime: " + Arrays.toString(nextTime));
// **** is this a valid time ****
if (digits[nextTime[0]] == 1 &&
digits[nextTime[1]] == 1 &&
digits[nextTime[2]] == 1 &&
digits[nextTime[3]] == 1)
isValid = true;
}
// **** return ****
return String.format("%02d:%02d", minutes / 60, minutes % 60);
}
The approach that we will use on both implementations is the same. The differences are only in the implementations in order to attempt to achieve better performance.
Since we are given a start time, our approach will be to increment the time one minute at a time and check if the new time matches the requirements of the problem. If it does, we are done; otherwise we need to continue incrementing the time by one until we encounter a time that matches requirements.
For simplicity we start by declaring a constant `MINS_IN_DAY` which contains the number of minutes in a day (24 hours with 60 minutes per hour). The time for a day starts at 00:00 and ends at “23:59”.
We then declare the `minutes` variable that holds the current time. This is done in order to attempt to simplify the way we keep track of the time.
We then declare and populate the `digits` array used to keep track of the digits we are allowed to use in the next `largest` time.
We then enter a while loop.
We need to increment the number of minutes in the `minutes` variable by one minute.
To perform the check we use the `nextTime` int[] in which we populate the first two entries with the HH, and the last two entries with the MM from the current time.
Now that we have isolated the four digits of interest in HH:MM, we proceed to check if the current time is valid. If so we flag it in the `isValid` variable which will end the while loop.
Our function then returns a string in the format HH:MM using the value in the `minutes` variable.
For performance information please take a look at the comments section in the source code.
/**
* Given a time represented in the format "HH:MM",
* form the next closest time by reusing the current digits.
* There is no limit on how many times a digit can be reused.
*
* Runtime: O(K) - Space: O(1)
*
* Runtime: 10 ms, faster than 33.91% of Java online submissions.
* Memory Usage: 39.1 MB, less than 34.11% of Java online submissions.
*
* 66 / 66 test cases passed.
* Status: Accepted
* Runtime: 10 ms
* Memory Usage: 39.1 MB
*/
static public String nextClosestTime(String time) {
// **** constant ****
final int MINS_IN_DAY = 1440; // 24 * 60
// **** initialization ****
int[] digits = new int[10];
int hh = 0;
int mm = 0;
boolean inHours = true;
// **** initialize digits, hh and mm - O(n) ****
for (char c : time.toCharArray()) {
// **** skip ':' ****
if (c == ':') {
inHours = false;
continue;
}
// **** add this digit to t ****
if (inHours)
hh = hh * 10 + (c - '0');
else mm = mm * 10 + (c - '0');
// **** flag c is in use ****
digits = 1;
}
// ???? ????
System.out.println("<<< MINS_IN_DAY: " + MINS_IN_DAY);
System.out.println("<<< digits: " + Arrays.toString(digits));
System.out.println("<<< hh:mm: " + hh + ":" + mm);
// **** loop incrementing time by 1 minute testing if done - O(K) ****
for (int i = 0; i < MINS_IN_DAY; i++) {
// **** increment time by 1 minute ****
mm++;
// **** update HH and MM (as needed) ****
if (mm == 60 ) {
// **** start of next hour ****
mm = 0;
hh++;
// **** start of next day ****
if (hh >= 24)
hh = 0;
}
// **** check if all digits in hh are in digits[] ****
if (hh < 10) {
if (digits[hh] == 0) continue;
if (digits[0] == 0) continue;
} else {
if (digits[hh / 10] == 0) continue;
if (digits[hh % 10] == 0) continue;
}
// **** check if digits in mm are in digits[] ****
if (mm < 10) {
if (digits[mm] == 0) continue;
if (digits[0] == 0) continue;
} else {
if (digits[mm / 10] == 0) continue;
if (digits[mm % 10] == 0) continue;
}
// **** this is the closest time ****
break;
}
// **** return next closest time ****
return String.format("%02d:%02d", hh, mm);
}
This implementation of the function of interest uses the same approach as the previous implementation by incrementing the time by one minute until the time matches the specified requirements.
We start by performing initialization steps.
We then enter a loop in which we will move forward up to an entire day one minute at a time.
We start by incrementing the `mm` variable which holds the minutes component of the time.
We check if the minutes turned into an hour. If so we increment the `hh` variable checking if we move to the next day at 00:00 hours.
We then check if the current time in `hh` and `mm` meet requirements. If not, we go back and increment the `mm` variable by one; otherwise we break out of the loop since we have found a time that meets requirements.
A string in the 24-hour format is generated and returned by the function.
If interested in performance information, please check the comments section in the function header.
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 NextClosestTime.
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