What is the time complexity of Next Greater Element III?

The optimal solution has a time complexity of O(n).

What data structures are used to solve Next Greater Element III?

This problem uses Math, Two Pointers, String. Understanding these concepts is essential for solving this Medium problem efficiently.

What are the key insights for solving Next Greater Element III?

Insight 1: The next greater element can be found by identifying the first decreasing element from right to left. This marks the position where a swap needs to occur to increase the number's value. Insight 2: After identifying the decreasing element, find the smallest element to its right that is larger than it and swap them. This ensures the smallest possible increase.

Which companies ask LeetCode 556. Next Greater Element III in interviews?

This problem is frequently asked at DoorDash, Goldman Sachs, Mitsogo.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Next Greater Element III - LeetCode 556 Solution

Next Greater Element III - Complete Solution Guide

Next Greater Element III is LeetCode problem 556, a Medium level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

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 . Note that the returned integer should fit in 32-bit integer , if there is a valid answer but it does not fit in 32-bit integer , return -1 . Example 1: Input: n = 12 Output: 21 Example 2: Input: n = 21 Output: -1 Constraints: 1 <= n <= 2 31 - 1

Detailed Explanation

The problem asks us to find the smallest integer that is greater than a given positive integer 'n' and contains the exact same digits as 'n'. If no such integer exists, we should return -1. A crucial constraint is that the resulting integer must fit within a 32-bit signed integer range. This means if the result is valid but exceeds the maximum 32-bit integer (231 - 1), we must also return -1.

Solution Approach

The solution involves these steps: First, convert the integer to a string (or char array). Then, starting from the right, find the first decreasing digit. If no such digit is found, the number is already the largest permutation, and no greater element exists. If a decreasing digit is found, find the smallest digit to its right that is larger than the decreasing digit, and swap them. After swapping, reverse the substring of digits to the right of the initially identified decreasing digit. Finally, convert the resulting string back to an integer and check for overflow. If the resulting integer is larger than the maximum 32-bit integer, return -1. Otherwise, return the integer.

Step-by-Step Algorithm

Step 1: Convert the input integer 'n' into a string (or character array).
Step 2: Iterate through the string from right to left, starting from the second-to-last digit (index l-2, where l is the length of the string).
Step 3: Find the first index 'i' where s[i] < s[i+1]. This is the decreasing element from right to left.
Step 4: If no such 'i' is found (i.e., the digits are non-increasing from left to right), it means the number is already the largest permutation, and we return -1.
Step 5: If 'i' is found, iterate through the string from right to left, starting from the last digit (index l-1).
Step 6: Find the first index 'j' where s[j] > s[i]. This is the smallest digit to the right of 'i' that is larger than s[i].
Step 7: Swap s[i] and s[j].
Step 8: Reverse the substring of the string from index i+1 to the end (index l-1). This ensures that the digits to the right of 'i' are in ascending order, creating the smallest possible number after the swap.
Step 9: Convert the modified string back into an integer.
Step 10: Check if the resulting integer is within the 32-bit signed integer range (i.e., less than or equal to 231 - 1). If not, return -1. Otherwise, return the integer.

Key Insights

Insight 1: The next greater element can be found by identifying the first decreasing element from right to left. This marks the position where a swap needs to occur to increase the number's value.
Insight 2: After identifying the decreasing element, find the smallest element to its right that is larger than it and swap them. This ensures the smallest possible increase.
Insight 3: Finally, reverse the portion of the number to the right of the swapped element to minimize the magnitude of the increase. This creates the smallest possible next greater element.
Insight 4: Need to check for integer overflow since the solution must fit within a 32-bit integer.

Complexity Analysis

Time Complexity: O(n)

Space Complexity: O(n)

Topics

This problem involves: Math, Two Pointers, String.

Companies

Asked at: DoorDash, Goldman Sachs, Mitsogo.

Next Greater Element III | LeetCode 556

Medium

Math Two Pointers String

Time: O(n)Space: O(n)

Solution Code

Available in:

class Solution {
    public int nextGreaterElement(int n) {
        char[] s = String.valueOf(n).toCharArray();
        int l = s.length;

        int i = l - 2;
        while (i >= 0 && s[i] >= s[i + 1]) {
            i--;
        }

        if (i < 0) {
            return -1;
        }

        int j = l - 1;
        while (j > i && s[j] <= s[i]) {
            j--;
        }

        char temp = s[i];
        s[i] = s[j];
        s[j] = temp;

        int left = i + 1;
        int right = l - 1;
        while (left < right) {
            char temp2 = s[left];
            s[left] = s[right];
            s[right] = temp2;
            left++;
            right--;
        }

        long res = Long.parseLong(new String(s));

        if (res > Integer.MAX_VALUE) {
            return -1;
        }
        
        return (int) res;
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 556: Next Greater Element III - Detailed explanation and solution approaches.

Topics

Math Two Pointers String

Companies

DoorDashGoldman SachsMitsogo

Stats

Difficulty:Medium

Languages:4

Companies:3

Problem #:556

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

10 steps

1
Step 1: Convert the input integer 'n' into a string (or character array).
2
Step 2: Iterate through the string from right to left, starting from the second-to-last digit (index l-2, where l is the length of the string).
3
Step 3: Find the first index 'i' where s[i] < s[i+1]. This is the decreasing element from right to left.
4
Step 4: If no such 'i' is found (i.e., the digits are non-increasing from left to right), it means the number is already the largest permutation, and we return -1.
5
Step 5: If 'i' is found, iterate through the string from right to left, starting from the last digit (index l-1).
6
Step 6: Find the first index 'j' where s[j] > s[i]. This is the smallest digit to the right of 'i' that is larger than s[i].
7
Step 7: Swap s[i] and s[j].
8
Step 8: Reverse the substring of the string from index i+1 to the end (index l-1). This ensures that the digits to the right of 'i' are in ascending order, creating the smallest possible number after the swap.
9
Step 9: Convert the modified string back into an integer.
10
Step 10: Check if the resulting integer is within the 32-bit signed integer range (i.e., less than or equal to 231 - 1). If not, return -1. Otherwise, return the integer.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(n)

👍 Linear - Good! Visits each element once.

💾

Space Complexity

O(n)

📦 Linear space - Memory grows with input size.

📝

Why?

The time complexity is determined by the number of iterations through the digits of the input number, making it linear. The space complexity comes from the string representation of the number, which scales linearly with the number of digits.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Brute Force

Generate all permutations of the digits of the input number and find the smallest permutation that is greater than the original number. This can be done recursively or using libraries.

Time: O(n! * n), where n is the number of digits. Generating all permutations takes O(n!), and comparing each permutation with the original number takes O(n).Space: O(n), where n is the number of digits, to store the permutations.

Trade-offs: The brute force approach has a significantly higher time complexity (factorial) compared to the optimal approach (linear). It is only suitable for small input numbers with very few digits. The main solution using the decreasing sequence and swapping is superior.

✨

Key Insights

1Insight 1: The next greater element can be found by identifying the first decreasing element from right to left. This marks the position where a swap needs to occur to increase the number's value.
2Insight 2: After identifying the decreasing element, find the smallest element to its right that is larger than it and swap them. This ensures the smallest possible increase.
3Insight 3: Finally, reverse the portion of the number to the right of the swapped element to minimize the magnitude of the increase. This creates the smallest possible next greater element.
4Insight 4: Need to check for integer overflow since the solution must fit within a 32-bit integer.

📚

Key Terms Explained

For Students

Two Pointers

Using two indices to traverse data from different positions simultaneously.

String

A sequence of characters. Like a word or sentence in programming!

Edge Cases

Edge case 1: Input is already the largest possible permutation (e.g., 54321). The algorithm correctly identifies this and returns -1.
Edge case 2: The resulting number after swapping and reversing exceeds the maximum 32-bit integer value (231 - 1). The algorithm includes a check for this overflow and returns -1.
Edge case 3: Single-digit numbers. The loops won't execute, and the code will return -1 as expected.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Failing to check for integer overflow after constructing the new integer. This can lead to incorrect results for inputs that produce values outside the 32-bit integer range.

✗Common mistake 2: Incorrectly implementing the substring reversal, leading to an incorrect next greater element.

✗Common mistake 3: Forgetting the edge case where the input number is already the largest possible permutation and incorrectly returning a number instead of -1.

✗Common mistake 4: Using `Integer.parseInt` in Java without first checking for potential `NumberFormatException` (although the code uses `Long.parseLong` and checks against `Integer.MAX_VALUE` which addresses this).

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Optimizing resource allocation. If you have a system that assigns tasks based on numerical IDs, finding the next greater ID can be useful in assigning the next available resource.

🏦Real-world scenario 2: Lexicographical ordering. This algorithm can be adapted for scenarios involving lexicographical ordering of strings or other data structures, such as finding the next valid password or code in a sequence.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

When dealing with arrays, always consider if sorting would simplify the problem. Many array problems have O(n) solutions using hash maps or two-pointer technique.

🎯 Interview Tip

If stuck, try working through a small example by hand. The pattern often reveals itself.

⚠️ Watch Out

Always test your solution with edge cases: empty input, single element, and boundary values.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: June 17, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

The key insight here is recognizing the pattern. Once you see it, the solution becomes straightforward.

@AlgoMasterJul 14

I was asked this exact problem at my Google interview. The interviewer wanted me to optimize space complexity.

@InterviewProJul 7

❓

Frequently Asked Questions

When is the two-pointer technique most effective?

Two pointers work best on sorted arrays or when searching for pairs/triplets that satisfy a condition. Common patterns include: moving pointers inward from both ends (like in two-sum variants), fast/slow pointers for cycle detection, or left/right pointers for partitioning.

What techniques are commonly tested in medium-difficulty problems?

Medium problems often require combining multiple techniques: two-pointer with hash maps, BFS/DFS with state tracking, dynamic programming with optimization, or divide-and-conquer approaches. They test your ability to recognize patterns and choose the right combination of techniques.

How should I practice algorithm problems effectively?

Focus on understanding patterns rather than memorizing solutions. After solving a problem, review optimal solutions and understand the intuition. Group similar problems to recognize patterns. Practice explaining your approach out loud. Review problems after a few days to test retention.

What is the optimal approach for "Next Greater Element III"?

For this medium-level Math problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether two pointers techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?