Formatted question description: https://leetcode.ca/all/556.html

556. Next Greater Element III (Medium)

Given a positive 32-bit integer n, you need to find the smallest 32-bit integer which has exactly the same digits existing in the integer n and is greater in value than n. If no such positive 32-bit integer exists, you need to return -1.

Example 1:

Input: 12
Output: 21

Example 2:

Input: 21
Output: -1

Related Topics:
String

Similar Questions:

Solution 1.

class Solution {
    public int nextGreaterElement(int n) {
        char[] array = String.valueOf(n).toCharArray();
        boolean next = nextPermutation(array);
        if (!next)
            return -1;
        String nextGreaterElementStr = new String(array);
        long nextGreaterElementLong = Long.parseLong(nextGreaterElementStr);
        if (nextGreaterElementLong > Integer.MAX_VALUE)
            return -1;
        else {
            int nextGreaterElement = (int) nextGreaterElementLong;
            return nextGreaterElement;
        }
    }

    public boolean nextPermutation(char[] array) {
        int length = array.length;
        int index = -1;
        char curChar = Character.MAX_VALUE;
        for (int i = length - 1; i > 0; i--) {
            int difference = array[i] - array[i - 1];
            if (difference > 0) {
                index = i - 1;
                curChar = array[i - 1];
                break;
            }
        }
        if (index < 0) {
            Arrays.sort(array);
            return false;
        }
        int nextIndex = -1;
        char nextChar = Character.MAX_VALUE;
        for (int i = index + 1; i < length; i++) {
            if (array[i] > curChar && array[i] < nextChar) {
                nextIndex = i;
                nextChar = array[i];
            }
        }
        array[index] = nextChar;
        array[nextIndex] = curChar;
        Arrays.sort(array, index + 1, length);
        return true;
    }
}

############

class Solution {
    public int nextGreaterElement(int n) {
        char[] cs = String.valueOf(n).toCharArray();
        n = cs.length;
        int i = n - 2, j = n - 1;
        for (; i >= 0 && cs[i] >= cs[i + 1]; --i)
            ;
        if (i < 0) {
            return -1;
        }
        for (; cs[i] >= cs[j]; --j)
            ;
        swap(cs, i, j);
        reverse(cs, i + 1, n - 1);
        long ans = Long.parseLong(String.valueOf(cs));
        return ans > Integer.MAX_VALUE ? -1 : (int) ans;
    }

    private void swap(char[] cs, int i, int j) {
        char t = cs[i];
        cs[i] = cs[j];
        cs[j] = t;
    }

    private void reverse(char[] cs, int i, int j) {
        for (; i < j; ++i, --j) {
            swap(cs, i, j);
        }
    }
}

// OJ: https://leetcode.com/problems/next-greater-element-iii/
// Time: O(1)
// Space: O(1)
class Solution {
public:
    int nextGreaterElement(int n) {
        auto s = to_string(n);
        for (int i = s.size() - 2; i >= 0; --i) {
            if (s[i] >= s[i + 1]) continue;
            int j = lower_bound(s.begin() + i + 1, s.end(), s[i], greater<int>()) - s.begin() - 1;
            swap(s[i], s[j]);
            sort(s.begin() + i + 1, s.end());
            long n = stol(s);
            return n > INT_MAX ? -1 : n;
        }
        return -1;
    }
};

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

############

class Solution(object):
  def nextGreaterElement(self, n):
    """
    :type n: int
    :rtype: int
    """
    num = n
    n = list(str(n))
    pos = leftMost = len(n) - 1
    for i in reversed(range(0, len(n) - 1)):
      if n[i] < n[i + 1]:
        leftMost = i
        break
    for i in reversed(range(leftMost + 1, len(n))):
      if n[i] > n[leftMost]:
        pos = i
        break

    n[leftMost], n[pos] = n[pos], n[leftMost]
    n[leftMost + 1:] = sorted(n[leftMost + 1:])
    n = int("".join(n))
    print
    n
    if n <= num or n > 0x7fffffff:
      return -1
    return n

func nextGreaterElement(n int) int {
	s := []byte(strconv.Itoa(n))
	n = len(s)
	i, j := n-2, n-1
	for ; i >= 0 && s[i] >= s[i+1]; i-- {
	}
	if i < 0 {
		return -1
	}
	for ; j >= 0 && s[i] >= s[j]; j-- {
	}
	s[i], s[j] = s[j], s[i]
	for i, j = i+1, n-1; i < j; i, j = i+1, j-1 {
		s[i], s[j] = s[j], s[i]
	}
	ans, _ := strconv.Atoi(string(s))
	if ans > math.MaxInt32 {
		return -1
	}
	return ans
}

556 - Next Greater Element III

556. Next Greater Element III (Medium)

Solution 1.

All Problems

All Solutions

Welcome to Subscribe On Youtube

556. Next Greater Element III (Medium)

Solution 1.

All Problems

All Solutions