4 Steps solution


  • 0
    M

    4 step algorithm:

    1. find the right most index i : s[i] < s[i + 1]
    2. find the right most index j: j > i and s[i] > s[j]
    3. swap s[i] with s[j]
    4. reverse s[i + 1] .. s[n - 1]
    public class Solution {
        public int nextGreaterElement(int n) {
            char[] s = String.valueOf(n).toCharArray();
            
            // step 1: find the right most index i : s[i] < s[i + 1]
            int i = s.length - 2;
            for (; i >= 0 && s[i] >= s[i + 1]; i--);
    
            if (i == -1) 
                return -1;
            
            // step 2: find the right most index j: j > i and s[i] > s[j]
            int j = s.length - 1;
            for (; j > i && s[j] <= s[i]; j--);
            
            // step 3: swap s[i] with s[j]        
            char tmp = s[i];
            s[i] = s[j];
            s[j] = tmp;
            
            // step 4: reverse s[i + 1] .. s[n - 1]
            for (int start = i + 1, end = s.length -1; start < end; start++, end--) {
                char buf = s[start];
                s[start] = s[end];
                s[end] = buf;
            }
            
            long val = Long.parseLong(String.valueOf(s));
            
            // after swap integer may not fit in 32 bit integer
            return val <= Integer.MAX_VALUE ? (int)val : -1;
        }
    }

Log in to reply
 

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