Next Greater Element III - Solution & Explanation
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 <= 231 - 1
Approach Overview
Problem Overview: Given a positive 32-bit integer n, rearrange its digits to form the next greater integer using exactly the same digits. If no such integer exists, or the result exceeds the 32-bit signed integer range, return -1.
Approach 1: Next Permutation (O(n) time, O(1) space)
This problem is essentially the classic next permutation task applied to the digits of an integer. Convert the number into a digit array or string. Traverse from right to left to find the first index where digits[i] < digits[i+1]. This position marks the pivot where a larger permutation can be formed. Then scan the suffix from the end to locate the smallest digit greater than digits[i], swap them, and reverse the suffix after i to make it the smallest possible arrangement. The algorithm performs a few linear scans over the digits, giving O(n) time with constant extra space. This technique is a common permutation trick when working with digit manipulation problems involving string processing and two pointers style scanning from both ends.
Approach 2: Mathematical Permutation Logic (O(n) time, O(1) space)
This approach derives the same idea directly through mathematical reasoning about digit order. Starting from the least significant digit, identify the first digit that breaks the non-increasing sequence when moving left. That digit is the pivot. The digits to the right are already in descending order, meaning they form the largest permutation of that suffix. To get the next greater number, swap the pivot with the smallest digit in that suffix that is larger than it. After the swap, reorder the suffix into ascending order so the resulting number is the smallest valid integer greater than the original. The process involves simple digit comparisons and swaps, making it efficient and memory-friendly. It highlights the role of permutation ordering in math-based digit manipulation problems.
Recommended for interviews: The Next Permutation approach is the expected solution. Interviewers often look for recognition that the task is identical to the next lexicographical permutation problem. Implementing the pivot search, swap, and suffix reversal in O(n) time demonstrates solid understanding of permutations and in-place array manipulation. The mathematical explanation helps justify why the algorithm works, but the next permutation implementation is typically what candidates code during interviews.
Approach 1: Approach 1: Next Permutation
This approach uses the concept of finding the next permutation of the digits of the number. We traverse the digits from right to left to find the first digit that is smaller than the digit next to it. Once found, we swap it with the smallest larger digit on its right and then reverse the sequence following the swapped digit.
The solution involves converting the integer to a string and manipulating the characters to find the next permutation. We ensure to swap the digits right before reversing the tail end. We also handle possible overflow scenarios by checking if the result exceeds the 32-bit limit.
Complexity
Time Complexity: O(n log n) (due to sorting in worst case)
Space Complexity: O(1) (in-place swap and conversion)
Approach 2: Approach 2: Mathematical Permutation Logic
This approach entails understanding mathematical permutation generation principles. First, identify the point where the digits stop increasing when moving left-to-right, then swap it. Finally, regenerate that segment to form the smallest sequential increase.
This method parses digits from the number to locate the next higher permutation swap, initiating a reverse rotation to create the smallest increment. It precisely tracks indices, ensuring accurate results.
Complexity
Time Complexity: O(n^2) (as it checks for minimum swap position for small digits segment)
Space Complexity: O(n) (array storage)
Approach 3: Default Approach
Try this approach in the editor →Complexity Comparison
| Approach | Complexity |
|---|---|
| Approach 1: Next Permutation | Time Complexity: O(n log n) (due to sorting in worst case) |
| Approach 2: Mathematical Permutation Logic | Time Complexity: O(n^2) (as it checks for minimum swap position for small digits segment) |
| Default Approach | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Next Permutation | O(n) | O(1) | General case. Standard algorithm for generating the next lexicographical permutation of digits. |
| Mathematical Permutation Logic | O(n) | O(1) | Useful for reasoning about digit order and permutation behavior without explicitly referencing the next permutation algorithm. |
Video Solution
Next Greater Element - III | Arrays & Strings | leetcode 556 Solution in Hindi • Pepcoding • 19,312 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Next Greater Element III easy or hard?
Next Greater Element III Python/Java solution
How to solve Next Greater Element III in O(n)?
What is the best approach for Next Greater Element III?
Is Next Greater Element III asked at Google/Amazon/Meta?
What data structure is used in Next Greater Element III?
What is the time complexity of Next Greater Element III?
Ready to solve this problem?
Practice Next Greater Element III with our built-in code editor and test cases.
Practice on FleetCodeProblem Info
Table of Contents
Practice this problem
Open in Editor