Problem
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
Solution
/**
* @param {number} n
* @return {number}
*/
var nextGreaterElement = function(n) {
var nums = n.toString().split('');
var i = nums.length - 1;
while (i > 0 && nums[i] <= nums[i - 1]) i--;
if (i === 0) return -1;
var j = i;
while (j <= nums.length - 1 && nums[j] > nums[i - 1]) j++;
swap(nums, i - 1, j - 1);
var newNums = nums.slice(0, i).concat(nums.slice(i).reverse());
var newNum = Number(newNums.join(''));
return newNum > Math.pow(2, 31) - 1 ? -1 : newNum;
};
var swap = function(nums, i, j) {
var tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
};
Explain:
nope.
Complexity:
- Time complexity : O(n).
- Space complexity : O(n).