Next Greater Element III LeetCode Solution

Difficulty Level Medium
Frequently asked in Adobe Amazon Apple Bloomberg ByteDance DoorDash Facebook Google Microsoft Oracle SalesforceViews 3692

Problem Statement

The problem, Next Greater Element III LeetCode Solution states that you are given a positive integer n and you need to find the next greatest integer using the digits present in n only. If there does not exist any such integer, you need to print -1. Moreover, the new integer should fit in a 32-bit integer. If not, then also print -1.

Examples

Test Case 1 –

Input – 13

Output – 31

Test Case 2 –

Input – 41

Output – -1

Test Case 3 –

Input – 2147483486

Output – -1

Approach for Next Greater Element III LeetCode Solution

Observations

  1. If all the digits of the number are sorted in descending order, then we cannot find a larger number and hence the output will be -1.
  2. If all the digits of the number are sorted in ascending order, then we can swap the last two digits of the number to find the next larger number.
  3. In every other case, we need to process the number from the rightmost digit.

Idea

  1. One thing is clear we need to process the given number digit-wise from right to left. So it is better to convert the number to a string and then process the string.
  2. Consider the number 35687 for understanding.  Start traversing the number from right until the first point where the digit is greater than its previous digit i.e. digit at index i > digit at index (i-1). In the number 35687, we will stop at 8 because it is greater than its previous digit 6.
  3. If while traversing, we reach the very first digit in the number, it means that the digits are in descending order and a larger number is not possible. Hence the output will be -1 for that case.
  4. Once the required index is found, reverse all the digits from that index to the end of the number. In the number 35687, the index is 3 corresponding to digit 8. So we reverse the digits for index 3 to the end of the number, and the number becomes 35678.
  5. Finally, in the last step, we need to find the smallest number that is greater than the digit present at index (i-1) and swap the two digits. In the number 35678, the digit 6 will be swapped with the digit 7, and the number becomes 35768.
  6. As a last check, compare the obtained number with 2147483647, to check if the number fits in 32-bits.
  7. Note – In step 4, we can also sort the digits from index i to the end, but that will increase the complexity from O(n) to O(nlogn), where n is the number of digits from index i to the end. We reversed the digits because they are already sorted in descending order and reversing them will do the job.

Code for Next Greater Element III LeetCode Solution

C++

class Solution {
public:
    int nextGreaterElement(int n) {
        string num = to_string(n);
        int len = num.size();
        int i = len-1;
        while(i>0){
            if(num[i] > num[i-1]) break;
            i--;
        }
        if(i==0) return -1;
        reverse(num.begin()+i, num.end());
        int j = i-1;
        while(i<len){
            if(num[j] < num[i]){
                swap(num[j], num[i]);
                break;
            }
            i++;
        }
        double ans = stod(num);
        if(ans > INT_MAX) return -1;
        return (int)ans;
    }
};

JAVA

class Solution {
    public int nextGreaterElement(int n) {
        String number = Integer.toString(n);
        char[] num = number.toCharArray();
        int len = num.length;
        int i = len-1;
        while(i>0){
            if(num[i] > num[i-1]) break;
            i--;
        }
        if(i==0) return -1;
        int j = i-1;
        i = len-1;
        while(i>j){
            if(num[j] < num[i]){
                char temp = num[j];
                num[j] = num[i];
                num[i] = temp;
                break;
            }
            i--;
        }
        StringBuilder ans_str = new StringBuilder();
        for(i=0;i<=j;i++) ans_str.append(num[i]);
        for(i=len-1;i>j;i--) ans_str.append(num[i]);
        
        long ans = Long.parseLong(ans_str.toString());
        
        if(ans > Integer.MAX_VALUE) return -1;
        return (int)ans;
    }
}

Python

class Solution(object):
    def nextGreaterElement(self, n):
        number = str(n);
        num = list(number)
        length = len(num);
        i = length - 1
        while i>0:
            if num[i] > num[i-1]:
                break
            i = i-1
        
        if i==0:
            return -1
        
        j = i-1;
        i = length-1
        while i>0:
            if num[j] < num[i]:
                temp = num[j]
                num[j] = num[i]
                num[i] = temp
                break
            i = i-1
        
        i = 0
        ans_str = ""
        while i<=j:
            ans_str += num[i]
            i = i+1
        
        i = length-1
        while i>j:
            ans_str += num[i]
            i = i-1
        
        ans = int(ans_str)
        
        if ans > 2147483647:
            return -1
        
        return ans

Complexity Analysis for Next Greater Element III LeetCode Solution

Time Complexity

In the worst case, the algorithm will iterate through all the digits present in the number. The number of digits present in a number is ceil(log n). So the time complexity is O(log n).

Space Complexity

We are not using any auxiliary space in the algorithm, so the space complexity is O(1).

Reference: https://algodaily.com/lessons/using-the-two-pointer-technique

Translate »