LeetCode — Next Greater Element III

Problem Link: https://leetcode.com/problems/next-greater-element-iii/

Integers

Problem Description:
Given a positive integer n, find the smallest integer which has exactly the same digits existing in the integer n and is greater in value than n. If no such positive integer exists, return -1.
Note that the returned integer should fit in a 32-bit integer if there is a valid answer but it does not fit in a 32-bit integer, return -1.

Approach Used: Mathematical, Logical, Arrays

Explanation: For finding the smallest number we need to start from right. Since we want to make the number bigger we will have to shift a bigger digit(right) to smaller digit’s position (left of bigger digit). The base case (when we return -1) will come when all digits are in non-increasing order. If this is not the case and we start from right we will encounter a position where the digit on its left is smaller than the current digit. This is the position where we need to do swapping (current_position-1). Let's call this position x. We will find the smallest digit on the right of this position since we want to make the smallest possible number bigger than the current number. We will swap these two digits (x, smallest digit on the right of x). Then sort all the digits on right side of this position(again to make the smallest possible number bigger than the current number). This will give the next biggest integer. In the end, we need to convert the array back to a number and take care of corner cases(overflow from Integer’s maximum value 2³¹)

Code: (Java)

public int nextGreaterElement(int n) {
        //make an array of all the digits in the number. 
        //The size of the array will be equal to number of digits in the input
        int[] digits = new int[Integer.toString(n).length()];
        
        //since we want to store digit in the natural ordering(left to right)
        //and we are extracting from last digit (right to left)
        //we will start storing from last index
        int index = digits.length-1;
        
        //so that original input is not changed to 0
        int temp=n;
        
        //loop that will extract all the digits and store in the array
        while(temp!=0){
            //temp%10 will extract the last digit in remaining number
            digits[index] = temp%10;
            index--;
            //reduce the number by 10
            temp/=10;
        }
        
        int i;
        //find the first position where a smaller digit is encountered on left than current digit
        for(i=digits.length-1; i>0; i--){
            if(digits[i]>digits[i-1]){
                break;
            }
        }
        
        //if we reach last, then all digits in number are in decreasing order
        //and hence a bigger number cannot be formed
        if(i==0)
            return -1;
        
        //find the smallest digit on right of this which is bigger than first digit in non-decreasing order 
        //we will swap these two digits
        int x = digits[i-1], smallestIndex=i;
        for(int j=i+1; j<digits.length; j++){
            if(digits[j]>x && digits[j]<digits[smallestIndex])
                smallestIndex=j;
        }
        
        //swapping the first digit in non-decreasing order from right with smallest digit on its right
        digits[i-1] = digits[smallestIndex];
        digits[smallestIndex] = x;
        
        //sorting all the digits on right of this index to get smallest possible number 
        //bigger than original number 
        Arrays.sort(digits, i, digits.length);
        
        //to chck for overflow (Integer max value is 2^31 -> 10 digit number starting with 2)
        //not the best approach
        if(digits.length==10 && digits[0]>2)
            return -1;
        
        //convert the array back to an integer
        int res=0;
        for(i=0; i<digits.length; i++){
            res = res*10+digits[i];
        }
        
        //if final result is negative, it means there is an overflow
        if(res<0)
            return -1;
        
        //return final output
        return res;
    }

Complexity:

Space complexity: O(length_input) . Since we store all digits in an array
Time complexity: O(length_input)
Here length_input is the number of digits in the input number.