[JAVA] 3 rules for next number / T : O(N), S : O(N)


  • 0
    J
    class Solution {
        
        //12345 -> 12354 -> 12435 -> 12453 -> 12534 -> 12543 -> 13245 -> 13254 ->13425 -> 13452 -> 13524
        
        public int nextGreaterElement(int n) {
            char[] chs = String.valueOf(n).toCharArray();
            int pivot = -1;
            for(int i = chs.length-1; i > 0; i--) { // O(N)
                if(chs[i] > chs[i-1]){
                    pivot = i;
                    break;
                }
            }
            
            // Descending order, 
            if(pivot == -1){
                return -1;
            }
            
            // Find smallest great number for chs[pivot - 1], O(N)
            int smallest = pivot;
            int smallest_last = pivot;
            for(int i = pivot; i < chs.length; i++){
                if(chs[i] > chs[pivot-1]){
                    if(chs[smallest] > chs[i]){
                        smallest = i;
                        smallest_last = i;
                    }
                    else if(chs[smallest] == chs[i])
                        smallest_last = i;
                }
            }
            
            char temp = chs[pivot-1];
            chs[pivot-1] = chs[smallest];
            chs[smallest] = temp;
            
            // Reverse below numbers 
            reverse(chs, smallest, smallest_last); // Consider 333 => 233 => 332
            reverse(chs, pivot, chs.length-1);
            
            // If number is bigger than Integer.MAX_VALUE
            String result = String.valueOf(chs);
            if(Long.parseLong(result) > Integer.MAX_VALUE)
                return -1;
                
            
            return Integer.parseInt(result);
        }
        
        public void reverse(char[] chs, int i, int j){
            while(i < j){
                char temp = chs[i];
                chs[i] = chs[j];
                chs[j] = temp;
                i++; j--;
            }
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.