public class NextGreaterNumber {
// 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
public static long nextGreaterNumber(long n) {
// Convert number to char array (digits)
char[] digits = String.valueOf(n).toCharArray();
int length = digits.length;
// Step 1: Find pivot (first digit from right that is smaller than the next)
int i;
for (i = length - 2; i >= 0; i--) {
if (digits[i] < digits[i + 1]) {
break;
}
}
// 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
int j;
for (j = length - 1; j > i; j--) {
if (digits[j] > digits[i]) {
break;
}
}
// Step 3: Swap pivot with that digit
char temp = digits[i];
digits[i] = digits[j];
digits[j] = temp;
// Step 4: Reverse the suffix (everything after pivot)
reverse(digits, i + 1, length - 1);
// Convert char array back to long
long result = 0;
for (char c : digits) {
result = result * 10 + (c - '0');
}
return result;
}
// Helper method to reverse part of the array
private static void reverse(char[] arr, int left, int right) {
while (left < right) {
char temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
left++;
right--;
}
}
public static void main(String[] args) {
System.out.println("Result: " + nextGreaterNumber(534965)); // 535469
System.out.println("-----------------------------");
System.out.println("Result: " + nextGreaterNumber(111)); // -1 (all digits identical)
System.out.println("-----------------------------");
System.out.println("Result: " + nextGreaterNumber(7600)); // -1 (already the largest)
}
}
/*
run:
Result: 535469
-----------------------------
Result: -1
-----------------------------
Result: -1
*/
