Next Closest Time Leetcode


#1

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.

Input: "19:34"
Output: "19:39"
Explanation: The next closest time choosing from digits 1, 9, 3, 4, is 19:39, which occurs 5 minutes later.  It is not 19:33, because this occurs 23 hours and 59 minutes later.

#2
/*
1. Parse digits from time and form a int array, clone it and sort the digits.
2. From the rear, find the next greater digit in the the sorted list, if you don't find, return the digit itself
3. If a next digit is found, assign that to the array, check if the digits array is valid time, if yes, break and return result or copy the smallest value in that digits place, continue search.

*/


func nextClosestTime(time string) string {
    digits := getDigits(time)
    
    sorted := append([]int{}, digits...)
    sort.Ints(sorted)
    
    fmt.Println(digits)
    for i:=len(digits)-1;i>=0;i--{
        next := nextDigit(digits[i], sorted)
        fmt.Println(next, digits[i])
        if next > digits[i]{
            digits[i] = next
            if isValid(digits){
                break
            }
        } 
        digits[i] = sorted[0]
    }
    
    result := fmt.Sprintf("%d%d:%d%d", digits[0], digits[1], digits[2], digits[3])
    return result
}

func isValid(digits []int) bool {
    return ((digits[0]*10+digits[1]) < 24 && (digits[2]*10+digits[3])< 60)
}

func nextDigit(digit int, sorted []int) int {
    for _, val := range sorted {
        if val>digit{
            return val
        }
    }
    return digit
}

func getDigits(time string) []int {
    digits := make([]int, 0)
    hourMins := strings.Split(time, ":")
    for i:=0;i<len(hourMins);i++{
        val, _ := strconv.Atoi(hourMins[i])
        digits = append(digits, val/10, val%10)
    }
    
    return digits
}

#3

A java version which avoids conversion of characters to int values.

class Solution {    
    public String nextClosestTime(String time) {
        if(time==null || time.length() < 5) return null;
        char[] result = {time.charAt(0), time.charAt(1), time.charAt(3), time.charAt(4)};
        char[] sorted = Arrays.copyOf(result, result.length);
        Arrays.sort(sorted);
       
        result[3] = findNextDigit(sorted, result[3], '9');
        if(result[3] > time.charAt(4)) return format(result);
       
        result[2] = findNextDigit(sorted, result[2], '5');   
        if(result[2] > time.charAt(3)) return format(result);
        
        result[1] = result[0]=='2'? findNextDigit(sorted, result[1], '3') : findNextDigit(sorted, result[1], '9');   
        if(result[1] > time.charAt(1)) return format(result);
                                                           
        result[0] = findNextDigit(sorted, result[0], '2');   
        if(result[0] > time.charAt(0)) return format(result);
                                                           
        return format(result);                                                   
    }   
    
    private char findNextDigit(char[] sorted, char cur, char max){
        if(cur==max) return sorted[0];
        int pos = Arrays.binarySearch(sorted, cur);
        while(pos < sorted.length){
            if(sorted[pos] > cur && sorted[pos] <= max) return sorted[pos];
            pos++;
        }
        
        return sorted[0];
    }
                                          
    private String format(char[] digits){
        return String.valueOf(""+digits[0]+digits[1]+':'+digits[2]+digits[3]);
    }
}