Untitled

 avatar
unknown
plain_text
3 months ago
3.7 kB
5
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