// 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) {
// Convert number to array of characters (digits)
$digits = str_split((string)$n);
$length = count($digits);
// Step 1: Find pivot (first digit from right that is smaller than the next)
$i = $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
$j = $length - 1;
while ($j > $i && $digits[$j] <= $digits[$i]) {
$j--;
}
// Step 3: Swap pivot with that digit
$temp = $digits[$i];
$digits[$i] = $digits[$j];
$digits[$j] = $temp;
// Step 4: Reverse the suffix (everything after pivot)
$left = $i + 1;
$right = $length - 1;
while ($left < $right) {
$tmp = $digits[$left];
$digits[$left] = $digits[$right];
$digits[$right] = $tmp;
$left++;
$right--;
}
// Convert array back to integer
return (int)implode('', $digits);
}
// Test cases
echo "Result: " . nextGreaterNumber(534965) . PHP_EOL; // 535469
echo "-----------------------------" . PHP_EOL;
echo "Result: " . nextGreaterNumber(111) . PHP_EOL; // -1 (all digits identical)
echo "-----------------------------" . PHP_EOL;
echo "Result: " . nextGreaterNumber(7600) . PHP_EOL; // -1 (already the largest)
/*
run:
Result: 535469
-----------------------------
Result: -1
-----------------------------
Result: -1
*/
