I came up with a quick brute force Java solution to the leetcode problem “Next Closest Time”. You can read the problem description and try to solve it for yourself here.
Overview:
1. build an integer array of digits
2. create a copy of the digits array and sort it
3. starting from the end of the digits array attempt to substitute the current value with the next greatest available within the constraints for each digit
4. if substitution occurred then replace remaining digits to the right with the lowest digit available
Although my solution is a brute force solution it runs in 3ms which beats 93% of accepted answers. My code with comments is below.
public String nextClosestTime(String time) {
//build digits array
int[] digits = new int[4];
int idx = 0, j = 0;
while(idx < digits.length){
if(time.charAt(j) == ':'){
j++;
continue;
}
digits[idx] = Integer.parseInt(time.substring(j,j+1));
j++;
idx++;
}
//sort digits
int[] digitsSorted = digits.clone();
Arrays.sort(digitsSorted);
//attempt to increment last digits of minutes 0-9 range
for(int i = 0; i < digitsSorted.length; i++){
if(digitsSorted[i] > digits[3]){
digits[3] = digitsSorted[i];
return arrToStr(digits, digitsSorted, 3);
}
}
//attempt to increment first digits of minutes 0-5 range
for(int i = 0; i < digitsSorted.length; i++){
if(digitsSorted[i] > digits[2] && digitsSorted[i] <= 5){
digits[2] = digitsSorted[i];
return arrToStr(digits, digitsSorted, 2);
}
}
//attempt to increment last digit of hours
//0-9 or 0-3 range depending on first digit of hours
for(int i = 0; i < digitsSorted.length; i++){
if(digits[0] == 2){
//last digit is bounded to 3 if first digit of hours is 2
if(digitsSorted[i] > digits[1] && digitsSorted[i] <= 3){
digits[1] = digitsSorted[i];
return arrToStr(digits, digitsSorted, 1);
}
}
else{
if(digitsSorted[i] > digits[1]){
digits[1] = digitsSorted[i];
return arrToStr(digits, digitsSorted, 1);
}
}
}
//attempt increment first digit of hours 0-2 range
for(int i = 0; i < digitsSorted.length; i++){
if(digitsSorted[i] > digits[0] && digitsSorted[i] <= 2){
digits[0] = digitsSorted[i];
return arrToStr(digits, digitsSorted, 0);
}
}
//replace all digits with lowest value
return arrToStr(digits, digitsSorted, 0);
}
//create string from array, set digits after substitution to lowest digit available
String arrToStr(int[] arr, int[] sorted, int idx){
StringBuilder sb = new StringBuilder();
for(int i = 0; i < arr.length; i++){
if(i == 2)
sb.append(":");
if(i <= idx)
sb.append(arr[i]);
else
sb.append(sorted[0]);
}
return sb.toString();
}