Simple O(n) Java solution


  • 0
    M

    This is a simple solution that is O(n) if you disregard sort operations.

    public int nextGreaterElement(int n) {
        char[] chars = String.valueOf(n).toCharArray();
        int l = chars.length - 1;
        int x = -1;
        int j;
    
        // Find first position where x = left digit < right digit.
        for (int i = l; i >= 1; i--) {
            if (chars[i - 1] < chars[i]) {
                x = i - 1;
                break;
            }
        }
    
        // If can't find, n is maximal.
        if (x == -1) return -1;
    
        // At this point, as the digits after x are sorted and the loop above implies
        //      chars[x] < chars[x - 1]
        // We try to find a digit to swap x with by searching for an index j such that
        //      chars[j] < chars[x]
        // If found, swap and then sort to get the next greater element.
        for (j = x + 1; j <= l; j++) {
            if (chars[j] <= chars[x]) {
                swap(chars, j - 1, x);
                Arrays.sort(chars, x + 1, l + 1);
                Long longVal = Long.valueOf(new String(chars));
                return longVal <= Integer.MAX_VALUE ? longVal.intValue() : -1;
            }
        }
    
        // If we hit the end without finding the position it's because the digits
        // at the right of x in the string are all equal and/or are all greater than chars[x].
        // In both cases the last position l represents the smallest number greater than n
        // so swap with last position and then sort.
        swap(chars, x, l);
        Arrays.sort(chars, x + 1, l + 1);
        Long longVal = Long.valueOf(new String(chars));
        return longVal <= Integer.MAX_VALUE ? longVal.intValue() : -1;
    }
    
    private void swap(char[] arr, int a, int b) {
        char t = arr[a];
        arr[a] = arr[b];
        arr[b] = t;
    }
    
    

Log in to reply
 

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