algoadvance

Leetcode 556. Next Greater Element III

Problem Statement

Given a positive integer n, find the smallest integer which has exactly the same digits existing in the integer n and is greater in value than n. If no such positive integer exists, return -1.

Example:

  1. Input: n = 12 Output: 21

  2. Input: n = 21 Output: -1

Clarifying Questions

  1. Q: Can n contain leading zeros? A: No, n will be a positive integer with no leading zeros.

  2. Q: What is the range of n? A: The constraint is not explicitly given, but assume it will fit within the bounds of a 32-bit signed integer (1 <= n <= 2^31 - 1).

Strategy

To solve the problem, we follow these steps:

  1. Identify the Pivot: From the right, find the first digit that is smaller than its next digit. Let this digit be at index i.
  2. Find the Swap Candidate: From the right, find the smallest digit that is larger than the digit at index i and swap them.
  3. Reverse the Suffix: Reverse the digits to the right of index i to get the smallest lexicographical order.

Here are the detailed steps:

  1. Convert the integer n to a character array arr for easy manipulation of digits.
  2. Traverse the array from the second last element to the start to find the first decreasing element; index i.
  3. If no such element is found, return -1.
  4. Traverse the array from the end to find the smallest digit larger than arr[i] and swap them.
  5. Reverse the sub-array starting from i + 1 to the end.
  6. Convert the character array back to an integer.
  7. If the result exceeds 32-bit integer range, return -1.

Code

class Solution {
    public int nextGreaterElement(int n) {
        char[] number = Integer.toString(n).toCharArray();
        
        int i = number.length - 2;
        // Step 1: Find first decreasing digit
        while (i >= 0 && number[i] >= number[i + 1]) {
            i--;
        }
        
        // If no such element is found, return -1
        if (i < 0) return -1;
        
        int j = number.length - 1;
        // Step 2: Find the next larger digit to swap with
        while (number[j] <= number[i]) {
            j--;
        }
        
        // Step 3: Swap the elements
        swap(number, i, j);
        
        // Step 4: Reverse the digits after index i
        reverse(number, i + 1, number.length - 1);
        
        // Convert back to integer and be cautious with overflow
        try {
            return Integer.parseInt(new String(number));
        } catch (NumberFormatException e) {
            return -1;
        }
    }
    
    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);
            start++;
            end--;
        }
    }
}

Time Complexity

This approach ensures that we effectively find the next greater permutation with the least lexicographical order in a constrained time frame.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI