/**
* Finds the smallest number greater than the given number
* using exactly the same digits.
*
* Time Complexity: O(n)
* - One pass from right to left to find pivot
* - One pass from right to left to find swap candidate
* - One reverse of suffix
* Space Complexity: O(n) for digit array
*/
function nextGreaterNumber(n: number): number {
// Convert number to array of digit characters
const digits: string[] = n.toString().split('');
const length: number = digits.length;
// Step 1: Find pivot (first digit from right that is smaller than the next)
let i: number = length - 2;
while (i >= 0 && digits[i] >= digits[i + 1]) {
i--;
}
// If no pivot found → digits are in descending order → no larger number possible
if (i < 0) {
return -1;
}
// Step 2: Find smallest digit to the right of pivot that is larger than pivot
let j: number = length - 1;
while (j > i && digits[j] <= digits[i]) {
j--;
}
// Step 3: Swap pivot with that digit
[digits[i], digits[j]] = [digits[j], digits[i]];
// Step 4: Reverse the suffix (everything after pivot)
let left: number = i + 1;
let right: number = length - 1;
while (left < right) {
[digits[left], digits[right]] = [digits[right], digits[left]];
left++;
right--;
}
// Convert array back to number
return Number(digits.join(''));
}
console.log("Result:", nextGreaterNumber(534965)); // 535469
console.log("-----------------------------");
console.log("Result:", nextGreaterNumber(111)); // -1 (all digits identical)
console.log("-----------------------------");
console.log("Result:", nextGreaterNumber(7600)); // -1 (already the largest)
/*
run:
Result: 535469
-----------------------------
Result: -1
-----------------------------
Result: -1
*/
