LeetCode 556: Next Greater Element III Solution

Master LeetCode problem 556 (Next Greater Element III), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

556. Next Greater Element III

Medium

Math Two Pointers String

Problem Explanation

Explanation

To find the next greater element that can be formed by rearranging the digits of a given number n, we can start from the rightmost digit and compare it with the digits to its left. We want to find the first digit from the right that is smaller than any digit to its right. Once we find such a digit, we swap it with the smallest digit to its right that is greater than it. Then, we sort the digits to the right of the swapped digit in ascending order to get the smallest possible number greater than the original number.

Algorithm

Convert the integer n to a character array to work with individual digits.
Start from the rightmost digit and find the first digit (let's call it i) that is smaller than the digit to its right (let's call it j).
If no such digit i exists, it means the number is already the largest possible number with the given digits. Return -1.
Find the smallest digit that is greater than digit i to the right of digit i. Swap digit i with this smallest digit.
Sort all digits to the right of digit i in ascending order to get the smallest number possible.
Convert the modified character array back to an integer and check if it exceeds the 32-bit integer limit. Return -1 if it does.
Otherwise, return the new integer as the answer.

Time Complexity

The time complexity of this algorithm is O(n) where n is the number of digits in the input number n.

Space Complexity

The space complexity of this algorithm is O(n) for storing the character array representation of the input number.

Solution Code

class Solution {
    public int nextGreaterElement(int n) {
        char[] digits = String.valueOf(n).toCharArray();
        
        int i = digits.length - 2;
        while (i >= 0 && digits[i] >= digits[i + 1]) {
            i--;
        }
        
        if (i == -1) {
            return -1;
        }
        
        int j = digits.length - 1;
        while (j >= 0 && digits[j] <= digits[i]) {
            j--;
        }
        
        swap(digits, i, j);
        reverse(digits, i + 1, digits.length - 1);
        
        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);
            start++;
            end--;
        }
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 556 (Next Greater Element III)?

This page provides optimized solutions for LeetCode problem 556 (Next Greater Element III) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 556 (Next Greater Element III)?

The time complexity for LeetCode 556 (Next Greater Element III) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 556 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 556 in Java, C++, or Python.

Back to LeetCode Solutions