Java Solution like Next Permutation Problem O(n)


  • 4
    public class Solution {
        public int nextGreaterElement(int n) {
            char[] a=(""+n).toCharArray();
            int i = a.length - 2;
            while (i >= 0 && a[i + 1] <= a[i]) {
                i--;
            }
            if(i<0)
                return -1;
            int j = a.length - 1;
            while (j >= 0 && a[j] <= a[i]) {
                j--;
            }
            swap(a, i, j);
            reverse(a, i + 1);
            try{
               return Integer.parseInt(new String(a));
            }
            catch(Exception e){
               return -1;
            }
        }
        private void reverse(char[] a, int start) {
            int i = start, j = a.length - 1;
            while (i < j) {
                swap(a, i, j);
                i++;
                j--;
            }
        }
        private void swap(char[] a, int i, int j) {
            char temp = a[i];
            a[i] = a[j];
            a[j] = temp;
        }
    }

  • 0
    R
    This post is deleted!

  • 3
    S

    This works , but I think we need to handle Integer MAX_VALUE cases as well, don't we?

           try{
                return Integer.parseInt(res); 
            }catch(Exception e){
                return -1;
            }

  • 2
    V

    Your solution will fail for the 10 digit integers. Ex: 1999999999


  • 0
    L

    Same idea here, and a little modification:

    public class Solution {
        public int nextGreaterElement(int n) {
            char[] arr=(n+"").toCharArray();
            if(arr.length<=1)  return -1;
            int i=arr.length-2;
            //Find the rightmost element, which is not in a non-increasing sequence ending at arr[arr.length-1];
            //For example, for 679833,  7 is the rightmost element, which is not in the non-increasing sequence 9,8,3,3.
            while(i>=0&&arr[i]>=arr[i+1]){
                i--;
            }
            if(i<0)   return -1;
            int j = arr.length - 1;
            //Find the smallest element larger than arr[i] in the non-increasing sequence.
            //Here, 8 is the smallest element larger than 7 in the sequence 9,8,3,3.
            while (arr[j] <= arr[i]) {
                j--;
            }
            //Swap arr[i] with the element arr[j]. 
            //Here, swap 7 with 8.
            char tmp=arr[i];
            arr[i]=arr[j];
            arr[j]=tmp;
            //Sort this newly modified non-increasing sequence, which is equivalent to reversing the sequence.
            //Now, 9,7,3,3, becomes 3,3,7,9;
            Arrays.sort(arr,i+1,arr.length);
            
            //Use long to avoid overflow;
            //Here, res=683379
            long res=Long.parseLong(new String(arr));
            return res>Integer.MAX_VALUE?-1:(int)res;
        }
    }
    

  • 0

    @vivek75 I have updated the solution. Thanks


  • 0

    Why do you say it's O(n)? It's O(log n), isn't it?

    Fascinating. Six people name a complexity class in their title, and all of them say O(n). (Well, one says O(N) and fails to say what they mean with N).


  • 0
    S

    @StefanPochmann said in Java Solution like Next Permutation Problem O(n):

    Why do you say it's O(n)? It's O(log n), isn't it?

    Fascinating. Six people name a complexity class in their title, and all of them say O(n). (Well, one says O(N) and fails to say what they mean with N).

    Isn't this O(n) where n is number of digits in input or O(log n) where n is number?


  • 0

    @suneelg Well, kind of. But n is the input number. That's defined in the problem.


Log in to reply
 

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