Next Greater Element III solution and explanation
Google
9 more videos on this problem
Next Greater Element - III | Arrays & Strings | leetcode 556 Solution in HindiPepcoding · 35:10 · 19K views
Next Greater Element III | Live Coding with Explanation | Leetcode #556Algorithms Made Easy · 7:18 · 18K views
Next Greater Element III | next greater element iii | leetcode 556 | stringNaresh Gupta · 11:20 · 7K views
LeetCode 556. Next Greater Element IIIHappy Coding · 16:35 · 3K views
Next Greater Element III | Leet code 556 | Theory explained + Python codeSai Anish Malla · 22:00 · 3K views
Next Greater Element III | Leetcode December Challenge Day 23 | Leetcode live coding session 556Coding Decoded · 15:15 · 2K views
LeetCode | 556. Next Greater Element III | Two Pointer | StringCompl3x · 15:31 · 1K views
DSA Series: Mastering Next Greater Element III | LeetCode Problem Explained | Code Crunch AcademyShivansh Pareek | Code Crunch · 21:14 · 826 views
Daily Leetcode #267: Dec 23, 2020 - 556. Next Greater Element IIIProgramming Live with Larry · 14:07 · 653 views
Leet Code 556 : Next Greater Element III Problem | Tutort AcademyTutort Academy · 23:00 · 506 views
The problem
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.
def nextGreaterElement(n: int) -> int:
digits = list(str(n))
i = len(digits) - 2
while i >= 0 and digits[i] >= digits[i + 1]:
i -= 1
if i == -1:
return -1
j = len(digits) - 1
while digits[j] <= digits[i]:
j -= 1
digits[i], digits[j] = digits[j], digits[i]
digits[i + 1:] = reversed(digits[i + 1:])
result = int(''.join(digits))
return result if result <= 2**31 - 1 else -1
print(nextGreaterElement(12))class Solution {
public int nextGreaterElement(int n) {
char[] digits = Integer.toString(n).toCharArray();
int i = digits.length - 2;
while (i >= 0 && digits[i] >= digits[i + 1]) i--;
if (i < 0) return -1;
int j = digits.length - 1;
while (digits[j] <= digits[i]) j--;
swap(digits, i, j);
reverse(digits, i + 1, digits.length - 1);
try {
return Integer.parseInt(new String(digits));
} 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--;
}
}
public static void main(String[] args) {
Solution sol = new Solution();
System.out.println(sol.nextGreaterElement(12));
}
}#include <iostream>
#include <string>
#include <algorithm>
int nextGreaterElement(int n) {
std::string digits = std::to_string(n);
int i = digits.size() - 2;
while (i >= 0 && digits[i] >= digits[i + 1]) i--;
if (i < 0) return -1;
int j = digits.size() - 1;
while (digits[j] <= digits[i]) j--;
std::swap(digits[i], digits[j]);
std::reverse(digits.begin() + i + 1, digits.end());
long long result = std::stoll(digits);
return (result > INT_MAX) ? -1 : result;
}
int main() {
int n = 12;
std::cout << nextGreaterElement(n) << std::endl;
return 0;
}function nextGreaterElement(n) {
let digits = n.toString().split('');
let i = digits.length - 2;
while (i >= 0 && digits[i] >= digits[i + 1]) i--;
if (i === -1) return -1;
let j = digits.length - 1;
while (digits[j] <= digits[i]) j--;
[digits[i], digits[j]] = [digits[j], digits[i]];
let result = parseInt(digits.slice(0, i + 1).concat(digits.slice(i + 1).reverse()).join(''));
return result > 2**31 - 1 ? -1 : result;
}
console.log(nextGreaterElement(12));#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int compare(const void* a, const void* b) {
return (*(char*)a - *(char*)b);
}
int nextGreaterElement(int n) {
char digits[11];
sprintf(digits, "%d", n);
int len = strlen(digits);
int i, j;
for (i = len - 2; i >= 0; i--) {
if (digits[i] < digits[i + 1]) {
break;
}
}
if (i < 0) return -1;
for (j = len - 1; j > i; j--) {
if (digits[j] > digits[i]) {
break;
}
}
char temp = digits[i];
digits[i] = digits[j];
digits[j] = temp;
qsort(digits + i + 1, len - i - 1, sizeof(char), compare);
long long newNumber = atoll(digits);
return (newNumber > INT_MAX) ? -1 : (int)newNumber;
}
int main() {
int n = 12;
printf("%d\n", nextGreaterElement(n));
return 0;
}using System;
public class Solution {
public int NextGreaterElement(int n) {
char[] digits = n.ToString().ToCharArray();
int i = digits.Length - 2;
while (i >= 0 && digits[i] >= digits[i + 1]) i--;
if (i < 0) return -1;
int j = digits.Length - 1;
while (digits[j] <= digits[i]) j--;
Swap(digits, i, j);
Array.Reverse(digits, i + 1, digits.Length - i - 1);
try {
return int.Parse(new string(digits));
} catch (OverflowException) {
return -1;
}
}
private void Swap(char[] arr, int i, int j) {
char temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public static void Main() {
Solution sol = new Solution();
Console.WriteLine(sol.NextGreaterElement(12));
}
}The Python solution converts the number into a list of digits for ease of manipulation. The core logic finds the right index to swap and then reverses the list from there. The final calculation checks against Python's integer overflow, though Python handles large integers naturally.
Time Complexity: O(n)
Space Complexity: O(n) (due to list conversion and slicing)
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.
def nextGreaterElement(n: int) -> int:
digits = list(str(n))
i = len(digits) - 2
while i >= 0 and digits[i] >= digits[i + 1]:
i -= 1
if i == -1:
return -1
j = len(digits) - 1
while digits[j] <= digits[i]:
j -= 1
digits[i], digits[j] = digits[j], digits[i]
digits = digits[:i+1] + sorted(digits[i+1:])
result = int(''.join(digits))
return result if result <= 2**31 - 1 else -1
print(nextGreaterElement(12))class Solution {
public int nextGreaterElement(int n) {
char[] digits = Integer.toString(n).toCharArray();
int i = digits.length - 2;
while (i >= 0 && digits[i] >= digits[i + 1]) i--;
if (i < 0) return -1;
int j = digits.length - 1;
while (digits[j] <= digits[i]) j--;
char temp = digits[i];
digits[i] = digits[j];
digits[j] = temp;
Arrays.sort(digits, i+1, digits.length);
long result = Long.parseLong(new String(digits));
return (result > Integer.MAX_VALUE) ? -1 : (int) result;
}
public static void main(String[] args) {
Solution sol = new Solution();
System.out.println(sol.nextGreaterElement(12));
}
}#include <iostream>
#include <vector>
#include <algorithm>
int nextGreaterElement(int n) {
std::string digits = std::to_string(n);
int i = digits.length() - 2;
while (i >= 0 && digits[i] >= digits[i + 1]) i--;
if (i < 0) return -1;
int j = i + 1;
while (j + 1 < digits.length() && digits[j + 1] > digits[i]) j++;
std::swap(digits[i], digits[j]);
std::sort(digits.begin() + i + 1, digits.end());
long long result = std::stoll(digits);
return (result > INT_MAX) ? -1 : result;
}
int main() {
int n = 12;
std::cout << nextGreaterElement(n) << std::endl;
return 0;
}function nextGreaterElement(n) {
let digits = n.toString().split('').map(Number);
let i = digits.length - 2;
while (i >= 0 && digits[i] >= digits[i + 1]) i--;
if (i === -1) return -1;
let j = digits.length - 1;
while (digits[j] <= digits[i]) j--;
[digits[i], digits[j]] = [digits[j], digits[i]];
let pre = digits.slice(0, i + 1);
let post = digits.slice(i + 1).sort((a, b) => a - b);
let result = parseInt(pre.concat(post).join(''));
return result > 2**31 - 1 ? -1 : result;
}
console.log(nextGreaterElement(12));#include <stdio.h>
int calculateMinimumLargerSwap(int *digits, int start, int indexToSwap) {
int minIndex = -1;
for (int i = start; i >= 0; --i) {
if (digits[i] > digits[indexToSwap]) {
if (minIndex == -1 || digits[i] < digits[minIndex]) {
minIndex = i;
}
}
}
return minIndex;
}
void reverse(int *digits, int start, int end) {
while (start < end) {
int temp = digits[start];
digits[start] = digits[end];
digits[end] = temp;
start++;
end--;
}
}
int nextGreaterElement(int n) {
int digits[10], count = 0;
while (n) {
digits[count++] = n % 10;
n /= 10;
}
int i = 0;
for (i = 0; i < count - 1 && digits[i] >= digits[i + 1]; i++);
if (i == count - 1) return -1;
int j = calculateMinimumLargerSwap(digits, i - 1, i);
int temp = digits[i];
digits[i] = digits[j];
digits[j] = temp;
reverse(digits, 0, i - 1);
long long result = 0;
for (int k = count - 1; k >= 0; k--) result = result * 10 + digits[k];
return (result > INT_MAX) ? -1 : (int)result;
}
int main() {
int n = 12;
printf("%d\n", nextGreaterElement(n));
return 0;
}using System;
using System.Linq;
public class Solution {
public int NextGreaterElement(int n) {
char[] digits = n.ToString().ToCharArray();
int i = digits.Length - 2;
while (i >= 0 && digits[i] >= digits[i + 1]) i--;
if (i < 0) return -1;
int j = digits.Length - 1;
while (digits[j] <= digits[i]) j--;
char temp = digits[i];
digits[i] = digits[j];
digits[j] = temp;
Array.Sort(digits, i + 1, digits.Length - i - 1);
try {
return int.Parse(new string(digits));
} catch (OverflowException) {
return -1;
}
}
public static void Main() {
Solution sol = new Solution();
Console.WriteLine(sol.NextGreaterElement(12));
}
}Python's straightforward handling of larger integers aids as we build permutations with clever slice reusing, compounding shortened permutations backwards.
Time Complexity: O(n log n)
Space Complexity: O(n)
Approach 3: Default Approach
func nextGreaterElement(n int) int {
s := []byte(strconv.Itoa(n))
n = len(s)
i, j := n-2, n-1
for ; i >= 0 && s[i] >= s[i+1]; i-- {
}
if i < 0 {
return -1
}
for ; j >= 0 && s[i] >= s[j]; j-- {
}
s[i], s[j] = s[j], s[i]
for i, j = i+1, n-1; i < j; i, j = i+1, j-1 {
s[i], s[j] = s[j], s[i]
}
ans, _ := strconv.Atoi(string(s))
if ans > math.MaxInt32 {
return -1
}
return ans
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Next Permutation | Time Complexity: O(n) |
| Approach 2: Mathematical Permutation Logic | Time Complexity: O(n log n) |
| Default Approach | – |
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. |
Frequently asked questions
Is Next Greater Element III easy or hard?
Next Greater Element III is considered a Medium difficulty problem. The implementation itself is short, but recognizing that the task is equivalent to the next lexicographical permutation problem requires algorithmic insight.
Next Greater Element III Python/Java solution
Python and Java implementations follow the same steps: convert the integer to a character or digit array, apply the next permutation logic, then reconstruct the integer and check the 32-bit limit. The logic remains identical across languages with only syntax differences.
How to solve Next Greater Element III in O(n)?
Scan the digits from right to left to find the first index i where digits[i] < digits[i+1]. Then find the smallest digit greater than digits[i] to its right and swap them. Finally reverse the digits after index i so the suffix becomes the smallest possible order. This sequence of operations produces the next lexicographically greater permutation in linear time.
What is the best approach for Next Greater Element III?
The optimal approach is the Next Permutation algorithm. Convert the integer to a digit array, find the pivot where digits stop increasing from right to left, swap it with the smallest larger digit in the suffix, then reverse the suffix. This produces the smallest number greater than the original using the same digits in O(n) time and O(1) space.
Is Next Greater Element III asked at Google/Amazon/Meta?
Variants of permutation and next greater element problems frequently appear in interviews at companies like Google, Amazon, and Meta. The question tests understanding of permutations, greedy digit manipulation, and in-place array transformations.
What data structure is used in Next Greater Element III?
The algorithm typically converts the integer into an array or string of digits so it can be manipulated like a sequence. Operations involve scanning, swapping elements, and reversing a suffix, which are standard array or string manipulation techniques.
What is the time complexity of Next Greater Element III?
The optimal solution runs in O(n) time where n is the number of digits. The algorithm performs a few linear passes: finding the pivot, locating the next larger digit, and reversing the suffix. Space complexity remains O(1) since all operations are done in place on the digit array.