Practice/Meta/Leetcode 556. Next Greater Element III

Leetcode 556. Next Greater Element III

CodingMust

Problem

Given a positive integer n, find the smallest integer that is greater than n and contains exactly the same digits as n. In other words, find the next lexicographic permutation of the digits in n.

If no such integer exists (because n is already the largest permutation of its digits), or if the result would exceed the 32-bit signed integer maximum value (2³¹ - 1 = 2,147,483,647), return -1.

Requirements

1. The result must use exactly the same digits as the input number
2. The result must be the smallest number greater than the input
3. Return -1 if no valid permutation exists
4. Return -1 if the result exceeds 2,147,483,647

Constraints

• 1 ≤ n ≤ 2³¹ - 1
• The solution should run in O(d) time where d is the number of digits
• Space complexity should be O(d) for storing digits

Examples

Example 1:

Input: n = 12 Output: 21 Explanation: The only greater permutation of digits 1 and 2 is 21.

Example 2:

Input: n = 230241 Output: 230412 Explanation: Starting from the right, we find that 2 (at position 3 from left) is the first digit smaller than its successor. We swap it with 4 (the smallest digit greater than 2 in the suffix), giving 230421. Then we reverse the suffix after position 3 to get 230412.

Example 3:

Input: n = 321 Output: -1 Explanation: The digits are in descending order, so this is already the largest permutation possible.

Example 4:

Input: n = 1 Output: -1 Explanation: A single digit has no other permutation.