556. Next Greater Element III LeetCode Solution

In this guide, you will get 556. Next Greater Element III LeetCode Solution with the best time and space complexity. The solution to Next Greater Element III problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Next Greater Element III solution in C++
Next Greater Element III solution in Java
Next Greater Element III solution in Python
Additional Resources

556. Next Greater Element III LeetCode Solution image

Problem Statement of Next Greater Element III

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

Constraints:

1 <= n <= 231 – 1

Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(n)

556. Next Greater Element III LeetCode Solution in C++

class Solution {
 public:
  int nextGreaterElement(int n) {
    const string& s = nextPermutation(to_string(n));
    const long ans = stol(s);
    return ans > INT_MAX || ans <= n ? -1 : ans;
  }

 private:
  // Similar to 31. Next Permutation
  string nextPermutation(string s) {
    const int n = s.length();

    int i;
    for (i = n - 2; i >= 0; --i)
      if (s[i] < s[i + 1])
        break;

    if (i >= 0) {
      for (int j = n - 1; j > i; --j)
        if (s[j] > s[i]) {
          swap(s[i], s[j]);
          break;
        }
    }

    reverse(s, i + 1, n - 1);
    return s;
  }

  void reverse(string& s, int l, int r) {
    while (l < r)
      swap(s[l++], s[r--]);
  }
};
/* code provided by PROGIEZ */

556. Next Greater Element III LeetCode Solution in Java

class Solution {
  public int nextGreaterElement(int n) {
    final String s = nextPermutation(String.valueOf(n).toCharArray());
    final long ans = Long.parseLong(s);
    return ans > Integer.MAX_VALUE || ans <= (long) n ? -1 : (int) ans;
  }

  // Similar to 31. Next Permutation
  private String nextPermutation(char[] s) {
    final int n = s.length;

    int i;
    for (i = n - 2; i >= 0; --i)
      if (s[i] < s[i + 1])
        break;

    if (i >= 0) {
      for (int j = n - 1; j > i; --j)
        if (s[j] > s[i]) {
          swap(s, i, j);
          break;
        }
    }

    reverse(s, i + 1, n - 1);
    return new String(s);
  }

  private void reverse(char[] s, int l, int r) {
    while (l < r)
      swap(s, l++, r--);
  }

  private void swap(char[] s, int i, int j) {
    final char temp = s[i];
    s[i] = s[j];
    s[j] = temp;
  }
}
// code provided by PROGIEZ

556. Next Greater Element III LeetCode Solution in Python

class Solution:
  def nextGreaterElement(self, n: int) -> int:
    def nextPermutation(s: list[str]) -> str:
      i = len(s) - 2
      while i >= 0:
        if s[i] < s[i + 1]:
          break
        i -= 1

      if i >= 0:
        for j in range(len(s) - 1, i, -1):
          if s[j] > s[i]:
            break
        s[i], s[j] = s[j], s[i]

      reverse(s, i + 1, len(s) - 1)
      return ''.join(s)

    def reverse(s: list[str], l: int, r: int):
      while l < r:
        s[l], s[r] = s[r], s[l]
        l += 1
        r -= 1

    s = nextPermutation(list(str(n)))
    ans = int(s)
    return -1 if ans > 2**31 - 1 or ans <= n else ans
 # code by PROGIEZ