<p>Given a positive integer <code>n</code>, find <em>the smallest integer which has exactly the same digits existing in the integer</em> <code>n</code> <em>and is greater in value than</em> <code>n</code>. If no such positive integer exists, return <code>-1</code>.</p>

<p><strong>Note</strong> that the returned integer should fit in <strong>32-bit integer</strong>, if there is a valid answer but it does not fit in <strong>32-bit integer</strong>, return <code>-1</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<pre><strong>Input:</strong> n = 12
<strong>Output:</strong> 21
</pre><p><strong class="example">Example 2:</strong></p>
<pre><strong>Input:</strong> n = 21
<strong>Output:</strong> -1
</pre>
<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= n &lt;= 2<sup>31</sup> - 1</code></li>
</ul>

class Solution:
    def nextGreaterElement(self, n: int) -> int:
        if n < 10: 
            return -1

        digits = list(map(int, list(str(n))))

        # step 1. find pivot idx
        for idx in range(len(digits) - 2, -1, -1):
            if digits[idx] < digits[idx + 1]:
                break
        else:
            # digits in n are sorted desc
            return -1

        pivot_idx = idx

        # step 2. find digit to swap pivot with
        for idx in range(len(digits) - 1, pivot_idx, -1):
            if digits[idx] > digits[pivot_idx]:
                break
        swap_idx = idx

        # step 3. swap and reverse post pivot
        digits[pivot_idx], digits[swap_idx] = digits[swap_idx], digits[pivot_idx]
        digits[pivot_idx + 1:] = reversed(digits[pivot_idx + 1:])

        # str_next_greater = ''.join(map(str, digits))
        # str_big_int = str(2**31 - 1)

        # if str_next_greater.rjust(len(str_big_int), '0') > str_big_int:
        #     return -1
        # else:
        #     return int(''.join(map(str, digits)))
        MAX = 2**31 - 1
        res = int(''.join(map(str, digits)))
        return res if res <= MAX else -1




# 999888731. sorted desc -> -1

# 312431 --swap 2 and 3-> 313421 --rev after 3-> 313124
#   p
#     s


16400