Next Greater Element III – LeetCode Solution in Java

Introduction

In this blog post, we will discuss the solution to the LeetCode problem “Next Greater Element III” using Java. This problem requires us to find the smallest integer greater than the given number n using the same set of digits. If no such integer exists or if the result does not fit within a 32-bit integer, we return -1.

Problem Statement

Given a positive integer n, find the smallest integer that contains exactly the same digits as n and is greater than n. If no such integer exists, return -1. Additionally, the returned integer must fit within the 32-bit integer range. If a valid answer exists but exceeds this range, return -1.

Solution Explanation

The main idea to solve this problem involves the following steps:

1. Identify the rightmost ascending pair of digits: Traverse the number from the end and find the first pair where the earlier digit is smaller than the later one.
2. Find the smallest digit larger than this digit on its right: This helps in forming the next greater number.
3. Swap these two digits: This makes the number larger but not necessarily the smallest possible.
4. Reverse the suffix: To ensure the new number is the smallest possible greater number, sort the digits to the right of the swapped position.

Java Code

Here’s the Java implementation of the solution:

public class Solution {
    public int nextGreaterElement(int n) {
        char[] digits = Integer.toString(n).toCharArray();
        int length = digits.length;

        // Step 1: Find the rightmost ascending pair
        int i;
        for (i = length - 2; i >= 0; i--) {
            if (digits[i] < digits[i + 1]) {
                break;
            }
        }

        // If no such pair is found, return -1
        if (i == -1) {
            return -1;
        }

        // Step 2: Find the smallest digit larger than digits[i] on the right side
        int j;
        for (j = length - 1; j > i; j--) {
            if (digits[j] > digits[i]) {
                break;
            }
        }

        // Step 3: Swap digits[i] and digits[j]
        swap(digits, i, j);

        // Step 4: Reverse the suffix
        reverse(digits, i + 1, length - 1);

        // Convert back to integer
        long result = Long.parseLong(new String(digits));

        // Check if result is within the 32-bit integer range
        return (result <= Integer.MAX_VALUE) ? (int) result : -1;
    }

    private void swap(char[] digits, int i, int j) {
        char temp = digits[i];
        digits[i] = digits[j];
        digits[j] = temp;
    }

    private void reverse(char[] digits, int start, int end) {
        while (start < end) {
            swap(digits, start, end);
            start++;
            end--;
        }
    }
}

Explanation of the Code

1. Finding the Rightmost Ascending Pair:

• We iterate from the end of the number to find the first pair of digits where the earlier digit is smaller than the next one. This indicates the point where we need to make changes to get a larger number.

1. Finding the Smallest Larger Digit:

• We find the smallest digit on the right side of the identified digit that is larger than it. This ensures that the swap will result in a greater number.

1. Swapping Digits:

• We swap these two digits to start forming the next greater number.

1. Reversing the Suffix:

• To get the smallest possible number greater than the original, we sort the digits to the right of the swapped digit. Reversing the order of these digits achieves this.

1. Returning the Result:

• Finally, we check if the result fits within the 32-bit integer range and return the result accordingly.

Conclusion

The “Next Greater Element III” problem on LeetCode can be efficiently solved using the above approach. By carefully identifying and swapping the necessary digits, we can ensure that we find the smallest number greater than the given number using the same set of digits. This solution is both efficient and easy to understand, making it a great addition to your problem-solving toolkit.

Feel free to comment below if you have any questions or alternative approaches to this problem!

Read More…

Introduction to SQL Programming: A Beginner’s Guide – https://kamleshsingad.com/introduction-to-sql-programming-a-beginners-guide/

Top 10 SQL Programming Tips for Beginners – https://kamleshsingad.com/top-10-sql-programming-tips-for-beginners/

Understanding SQL Joins: A Comprehensive Guide – https://kamleshsingad.com/understanding-sql-joins-a-comprehensive-guide/