Untitled
unknown
plain_text
9 months ago
3.7 kB
7
Indexable
### Intuition and Thought Process
This problem is a variation of **Next Permutation**, where we need to find the next lexicographically greater number using the same digits.
1. **Identify the First Decreasing Digit from the Right**
- Start from the rightmost digit and move left until you find the first digit that is **smaller than** the digit immediately after it. This is the **pivot**.
- If no such pivot is found, it means the number is the largest permutation (e.g., `21`), so return `-1`.
2. **Find the Smallest Digit Greater than Pivot**
- Scan the digits to the right of the pivot and find the **smallest digit that is larger than the pivot**.
- Swap these two digits to make the number larger.
3. **Sort (Reverse) the Remaining Digits**
- To ensure we get the **smallest possible** number greater than `n`, sort (or reverse) the digits **after** the pivot position.
4. **Check for 32-bit Integer Overflow**
- Convert the final result back to an integer.
- If it exceeds `Integer.MAX_VALUE` (i.e., `2^31 - 1`), return `-1`.
### Java Implementation
```java
import java.util.*;
public class NextGreaterElement {
public int nextGreaterElement(int n) {
char[] digits = Integer.toString(n).toCharArray();
int len = digits.length;
// Step 1: Find the first decreasing digit from the right
int i = len - 2;
while (i >= 0 && digits[i] >= digits[i + 1]) {
i--;
}
// If no such index is found, return -1
if (i == -1) return -1;
// Step 2: Find the smallest digit on the right that is larger than digits[i]
int j = len - 1;
while (digits[j] <= digits[i]) {
j--;
}
// Step 3: Swap the two numbers
swap(digits, i, j);
// Step 4: Reverse the remaining digits to get the smallest permutation
reverse(digits, i + 1, len - 1);
// Convert back to integer and check for overflow
long result = Long.parseLong(new String(digits));
return (result > Integer.MAX_VALUE) ? -1 : (int) result;
}
private void swap(char[] arr, int i, int j) {
char temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
private void reverse(char[] arr, int start, int end) {
while (start < end) {
swap(arr, start++, end--);
}
}
public static void main(String[] args) {
NextGreaterElement obj = new NextGreaterElement();
System.out.println(obj.nextGreaterElement(12)); // Output: 21
System.out.println(obj.nextGreaterElement(21)); // Output: -1
System.out.println(obj.nextGreaterElement(54321)); // Output: -1
System.out.println(obj.nextGreaterElement(12443322)); // Output: 13222344
}
}
```
### Complexity Analysis
- **Finding the pivot:** O(n)
- **Finding the correct swap position:** O(n)
- **Swapping:** O(1)
- **Reversing the remaining portion:** O(n)
- **Converting to integer:** O(n)
**Total Complexity:** O(n), where `n` is the number of digits in the number.
### Edge Cases Considered
1. **Already Largest Permutation:**
- If `n = 21`, `54321`, etc., return `-1`.
2. **Single Digit Numbers:**
- If `n = 7`, return `-1` (since no greater number is possible).
3. **Numbers with Repeating Digits:**
- If `n = 12443322`, the output should be `13222344`.
4. **Largest 32-bit Integer Handling:**
- If the result exceeds `2^31 - 1`, return `-1`.
This method ensures that we find the next greater number efficiently and correctly.
Editor is loading...
Leave a Comment