Home
Algorithms Data Structures Interview Experiences
Amazon Google Facebook Microsoft Apple Netflix
Play 2048 How to

LeetCode Solutions

556. Next Greater Element III

Time: $O(n)$

Space: $O(n)$

			


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:
  // Very simliar 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--]);
  }
};




			


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;
  }

  // Very simliar 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;
  }
}




			


class Solution:
  def nextGreaterElement(self, n: int) -> int:
    def nextPermutation(s: List[chr]) -> 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[chr], 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