Last updated on February 2nd, 2025 at 06:16 am

Here, we see a Next Greater Element III LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.

List of all LeetCode Solution

Topics

String

Companies

Bloomberg

Level of Question

Medium

Next Greater Element III LeetCode Solution

1. Problem Statement

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 32-bit integer, if there is a valid answer but it does not fit in 32-bit integer, return -1.

Example 1:
Input: n = 12
Output: 21

Example 2:
Input: n = 21
Output: -1

2. Coding Pattern Used in Solution

The coding pattern used in all the provided implementations is “Permutation and Combination Manipulation”. This pattern involves identifying the next lexicographical permutation of a number (or sequence) by rearranging its digits.

3. Code Implementation in Different Languages

3.1 Next Greater Element III C++

class Solution {
public:
    int nextGreaterElement(int n) {
        vector<int> digits;
        while (n) {
            digits.push_back(n % 10);
            n /= 10;
        }
        for (int i = 1, j, len = digits.size(), lmt = INT_MAX / 10; i < len; i++) {
            if (digits[i - 1] > digits[i]) {
                j = 0;
                while (digits[j] <= digits[i]) j++;
                swap(digits[j], digits[i]);
                sort(begin(digits), begin(digits) + i, greater<int>());
                while (digits.size()) {
                    n = n * 10 + digits.back();
                    digits.pop_back();
                    if (n >= lmt && digits.size()) return -1;
                }
                return n;
            }
        }
        return -1;        
    }
};

3.2 Next Greater Element III Java

class Solution {
    public int nextGreaterElement(int n) {
        char arr[] = (Integer.toString(n)).toCharArray();
        int i=arr.length-2;
        StringBuilder ans = new StringBuilder();
        while(i>=0 && arr[i] >= arr[i+1])
            i--;
        if(i == -1)
            return -1;
        int k = arr.length-1;
        while(arr[k] <= arr[i])
            k--;
        swap(arr,i,k);
        for(int j=0;j<=i;j++)
            ans.append(arr[j]);
        for(int j=arr.length-1;j>i;j--)
            ans.append(arr[j]);
        long ans_ = Long.parseLong(ans.toString());
        return (ans_ > Integer.MAX_VALUE) ? -1 : (int)ans_;
    }
    void swap(char[] arr,int i,int j)
    {
        char temp = arr[j];
        arr[j] = arr[i];
        arr[i] = temp;
    }
}

3.3 Next Greater Element III JavaScript

var nextGreaterElement = function(n) {
    var numbers = ("" + n).split('').map(n=>parseInt(n));
    var lastIncreasePosition = null;
    var smallestToSwapWithPosition;
    var i, l;
    for (i = 0, l = numbers.length; i < l; i++) {
        if (numbers[i] < numbers[i + 1] && i + 1 < l) {
            lastIncreasePosition = i;
            smallestToSwapWithPosition = i + 1;
        } else if (lastIncreasePosition !== null) {
            if (numbers[smallestToSwapWithPosition] > numbers[i] && numbers[i] > numbers[lastIncreasePosition]) {
                smallestToSwapWithPosition = i;
            }
        }
    }
    if (lastIncreasePosition === null) {
        return -1;
    }
    let temp = numbers[lastIncreasePosition];
    numbers[lastIncreasePosition] = numbers[smallestToSwapWithPosition];
    numbers[smallestToSwapWithPosition] = temp
    var sorted = numbers.slice(0, lastIncreasePosition + 1)
    var unsorted = numbers.slice(lastIncreasePosition + 1);
    unsorted = unsorted.sort((a,b) => a - b);
    numbers = [...sorted, ...unsorted];
    n = parseInt(numbers.join(''));
    if (n > 2147483647) {
        return -1;
    }
    return n;
};

3.4 Next Greater Element III Python

class Solution(object):
    def nextGreaterElement(self, n):
        nums = list(str(n))
        i = len(nums) - 1
        while i > 0 and nums[i-1] >= nums[i]:
            i -= 1
        if i == 0:
            return -1
        j = len(nums) - 1
        while j > i-1 and nums[j] <= nums[i-1]:
            j -= 1
        nums[i-1], nums[j] = nums[j], nums[i-1]
        nums[i:] = nums[i:][::-1]
        res = int(''.join(nums))
        return res if res < 2**31 else -1

4. Time and Space Complexity

	Time Complexity	Space Complexity
C++	O(n log n)	O(n)
Java	O(n log n)	O(n)
JavaScript	O(n log n)	O(n)
Python	O(n log n)	O(n)