Next Greater Element III
Problem Description
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.
Examples
Input: n = 12
Output: 21
Explanation: For input 12, the next greater number with the same digits is 21.
Input: n = 21
Output: -1
Explanation: For input 21, no next greater number exists, so the output is -1.
Constraints
- 1 <= n <= 2^31 - 1
Okay ! After going through the problem statement, what would we think about the logic? How can we find the next greater number using the same digits? Let's analyse the description now..
Brute Force Approach
Intuition
One approach is - let's convert the number into a list of digits, then we will try every possible permutation of the digits and we will find the smallest one that’s bigger than the original number after sorting the permutations.
What is Permutation ?
So, what exactly are permutations?Well, think of it like arranging your favorite books on a shelf. How many different ways can you place them? That’s what permutations are—different orders of elements! For example, with three books labeled 1, 2, and 3, you can arrange them in 6 ways:123, 132, 213, 231, 312, and 321. Pretty cool, right?
But wait, there’s a chance—if all the permutations are smaller or the same, we return -1 because no greater number exists.
Now, there's an additional challenge: if the resultant value exceeds 2^{31}−1 (the maximum value for a 32-bit integer), we must also return -1. This ensures our result stays within the valid range.
Now, you might ask, “How do I generate all these different orders?” We can do it recursively by picking one book (or element), fixing it, and then permuting the rest. Keep swapping and repeating until you've covered every possible order!
So, are you ready to start rearranging?
Approach
Step 1: Initializing the empty list for permutations.
Step 2: Convert the number n into a list of digits for easy manipulation.
Step 3: Generate all possible permutations of the digits and store it in a list.
Step 4: Sort the list of the generated permutations in ascending order.
Step 5: Find the smallest permutation that is greater than n.
Step 6:
- If the resultant value is greater than the value 2^31-1, return -1
- If there is no greater number, return -1
- Else return the resultant greater number.
Dry Run
Input: n = 5673543
Output: 5674335
Explanation : The next greater element for the given one is 5674335
Initialization: n = 5673543 permutations = []
Extract Digits: Convert the number into a list of digits: digits = ['5', '6', '7', '3', '5', '4', '3']
Generate Permutations: Generate all possible permutations of the digits: permutations = ['5673543', '5673435', '5674353', ..., '7655433']
Sort Permutations: Sort the permutations lexicographically: sorted_permutations = ['3345567', ..., '5673543', ..., '7655433']
Find the Smallest Greater Number: Locate 5673543 in the sorted list:
- The number just after 5673543 in the sorted list is 5674335.
Return the Result: Output: 5674335
Brute Force Code in all Languages
1. C++ Try on Compiler
class Solution {
public:
static long long nextGreaterElement(long long n) {
string digits = to_string(n);
vector<long long> permutedNumbers;
// Generate all permutations of the digits
generatePermutations(digits, 0, permutedNumbers);
// Remove duplicates and sort the numbers
set<long long> uniqueNumbers(permutedNumbers.begin(), permutedNumbers.end());
// Iterate through the sorted unique numbers
for (long long num : uniqueNumbers) {
// Find the first number greater than the input and within the long long range
if (num > n && num <= INT_MAX) {
// Return the next greater number
return num;
}
}
// If no such number exists, return -1
return -1;
}
private:
static void generatePermutations(string &digits, int index, vector<long long> &permutedNumbers) {
if (index == digits.length()) {
try {
long long num = stoll(digits); // Use stoll to convert to long long
permutedNumbers.push_back(num);
} catch (const out_of_range& e) {
// If the number is too large, we ignore this permutation
}
return;
}
for (int i = index; i < digits.length(); i++) {
swap(digits[index], digits[i]);
generatePermutations(digits, index + 1, permutedNumbers);
swap(digits[index], digits[i]); // Backtrack
}
}
};2. Java Try on Compiler
class Solution {
public static int nextGreaterElement(int n) {
// Convert the input number to a character array for permutation
char[] digits = String.valueOf(n).toCharArray();
// List to store all permutations as long values
List<Long> permutedNumbers = new ArrayList<>();
// Generate all permutations of the digits
generatePermutations(digits, 0, permutedNumbers);
// Use a TreeSet to store unique permutations in sorted order
Set<Long> uniqueNumbers = new TreeSet<>(permutedNumbers);
// Iterate through the sorted unique numbers
for (long num : uniqueNumbers) {
// Find the first number greater than the input and within int range
if (num > n && num <= Integer.MAX_VALUE) {
return (int) num; // Cast to int and return
}
}
// If no such number exists, return -1
return -1;
}
private static void generatePermutations(char[] digits, int index, List<Long> permutedNumbers) {
// Base case: If we've reached the end of the digits array
if (index == digits.length) {
// Convert the char array back to a long and add it to the list
permutedNumbers.add(Long.parseLong(new String(digits)));
return;
}
// Recursively generate permutations by swapping digits
for (int i = index; i < digits.length; i++) {
// Swap the current digit with the digit at position i
swap(digits, index, i);
// Generate permutations for the next index
generatePermutations(digits, index + 1, permutedNumbers);
// Backtrack: Undo the swap to restore the original order
swap(digits, index, i);
}
}
private static void swap(char[] digits, int i, int j) {
// Swap two elements in the char array
char temp = digits[i];
digits[i] = digits[j];
digits[j] = temp;
}
}3. Python Try on Compiler
def next_greater_number(n):
# Convert the number into a list of digits
digits = list(str(n))
# Initialize a list to store permutations
permuted_numbers = []
# Function to generate all permutations of digits
def generate_permutations(digits, index):
# Base case: if index reaches the end of the list, add the permutation
if index == len(digits):
# Convert the list of digits back to an integer and add to permuted_numbers
permuted_numbers.append(int("".join(digits)))
return
# Generate permutations by swapping the current digit with the next ones
for i in range(index, len(digits)):
# Swap the current digit with the next one
digits[index], digits[i] = digits[i], digits[index]
# Recursively permute the next digits
generate_permutations(digits, index + 1)
# Backtrack by swapping the digits back
digits[index], digits[i] = digits[i], digits[index]
# Generate all permutations of the digits
generate_permutations(digits, 0)
# Remove duplicate permutations by converting to a set
uniqueNumbers = list(set(permuted_numbers))
# Sort the list of permutations
uniqueNumbers.sort()
# Check for the next greater permutation
for num in uniqueNumbers:
# Return the next greater permutation
if num > n:
return num
# Return -1 if no greater permutation is found
return -14. JavaScript Try on Compiler
var nextGreaterElement = function(n) {
// Convert the number to a string and then to an array of digits
let digits = n.toString().split('');
let permutedNumbers = [];
// Generate all permutations of the digits using recursion
generatePermutations(digits, 0, permutedNumbers);
// Remove duplicates and sort the numbers
let uniqueNumbers = [...new Set(permutedNumbers)].sort((a, b) => a - b);
// Iterate through the sorted unique numbers to find the next greater number
for (let num of uniqueNumbers) {
if (num > n) {
// Return the next greater number if found
if (num <= Math.pow(2, 31) - 1) { // Ensure the number is within integer limits
return num;
} else {
return -1; // Return -1 if number exceeds the integer range
}
}
}
// If no such number exists, return -1
return -1;
};
/**
* Helper function to generate permutations
* @param {Array} digits - The digits array to permute
* @param {number} index - Current index to fix a digit
* @param {Array} permutedNumbers - Array to store the unique permutations
*/
function generatePermutations(digits, index, permutedNumbers) {
if (index === digits.length) {
permutedNumbers.push(parseInt(digits.join(''), 10)); // Convert array to number and add
return;
}
for (let i = index; i < digits.length; i++) {
// Swap the digits at index and i
[digits[index], digits[i]] = [digits[i], digits[index]];
// Recursively generate permutations for the next index
generatePermutations(digits, index + 1, permutedNumbers);
// Backtrack by swapping the digits back
[digits[index], digits[i]] = [digits[i], digits[index]];
}
}
Time Complexity: O(d!log(d!))
Generating Permutations: The code generates all d! permutations of the digits, where d is the number of digits.
Sorting Permutations: Sorting d! permutations requires O(d!⋅log(d!)).
Finding the Next Greater Number: Iterating through the sorted list adds O(d!).
Total Time Complexity: O(d!) + O(d!⋅log(d!)) ≈ O(d!log(d!))
Space Complexity: O(d!)
Auxiliary Space Complexity:Auxiliary space is the extra space or temporary space used by an algorithm apart from the input.
- This algorithm generates and stores all d! permutations of the digits, using O(d!) space.
Total space complexity
Input space for integer- O(1)
Auxiliary space - O(d!)
Total space complexity O(1) + O(d!) ≈ O(d!).
The code we see works fine for small numbers, but for larger inputs, it struggles due to generating all possible permutations, which grows as d!. Imagine millions of permutations for just 10 digits—this makes the code both slow and memory-heavy. In order to move further in the interview we have to figure out an optimal way, let’s figure it out together !!
Optimal Approach
Intuition
Alright, let’s cut down on the time and space wasted by brute-forcing through permutations. We’ve got a smarter way to find the next greater number!
Okay, let’s take the number 56354.
What will be the next largest number for it? 56435, right!!!
Okay then, take 12345. What would be the next largest number for it? 12354, right!!!
What is the next largest number for 56734321? 56741233, isn’t it? Check out once carefully…
Have you got any pattern or any observation from the given examples? Yeah!!
Let’s have all the examples together!!!
Number Next Greater Number Difference
56354 56435 354 —--> 435 [last 3 digits changed their order]
12345 12354 45 —--->54 [Last 2 digits changed their order]
56734321 56741233 34321—>41233 [similarly Last 5 digits]
If you observe the above examples carefully, the digits from the right to left, covering a certain distance, are only rearranging themselves to become the next greater element for the given number. Hope we are on the track, buddies!!!! Big yes for this!
Okay then, let’s closely observe them. When the digits are rearranging, how are they?
Let’s take the number 56354 again and make the analysis. As per the above observation, the change occurred in 354 !
If you observe carefully, rearranging 4 alone in the same place cannot make the number bigger !! Okay then, consider 54.
Rearranging 54 front and forth… Can these digits (5, 4) make the number bigger? Noooo, because 54 is already greater than 45, right? So there is no use of rearranging, right! Move forward, consider the last three digits now — 354. Be attentive, my dear! Can rearranging these digits make the number bigger than the original one? Yessssss… Lots of chances to make our number bigger by arranging the digits as follows — 453, 435, 534, 543.
But why not 345 or 354? Keeping 354 again as it is doesn’t make any sense, as it is already present there, right? We need the greater one than the present right, so we won’t consider the same arrangement again! Ok fine then, keeping 345 will lower the original value, so we don’t need it !!
At last, we have 4 arrangements which can increase the value of the original one. But we want the next greater element of our original, which is slightly greater than it, so what arrangement will make the number slightly greater in these 4? (453, 435, 534, 543) Absolutely 435 among those 4, right!!!
Finally, we add this arrangement to the remaining elements to get the next greater element for our original number, which is 56435.
So from the above things, coming from right to left, if the sequence has been increasing in order, there is no use rearranging them because they are already maximized. Then, whenever the increasing order breaks — so called as a breakpoint — we have the chance to get the next greater element by rearranging the digits from right to left up to that breakpoint.
The intuition goes like this- First, we find where the digits break their increasing order from right to left. Once we spot that, we swap the identified smaller digit with the smallest larger digit from the right side.
Observe this:
56354
3—--—> is the break point , then we swap with the smallest larger number n its right side, then the number becomes 56453
56453
Next, we reverse the digits after the swapp ed position to get the smallest possible number from the remaining digits. Then the number becomes 56435.But here’s the twist — if the digits are already in descending order (meaning no "break" is found), there’s no way to create a larger number, so we return -1, or the resultant value is greater than 2^31-1.The best part? We use a two-pointer technique to find the breakpoint and reverse the digits efficiently, saving both time and space. It’s like taking a shortcut through the maze instead of wandering around aimlessly. Cool, right?
“Why not change earlier digits?” Good question! Changing earlier digits creates a much bigger jump, which we don’t want. Adjusting the breakpoint keeps the change minimal, making it the perfect starting point for our next greater number!
Approach
Step 1: Initialize a list consists of digits of the given number
Step 2: Traverse the list from right to left to find the first index where a digit is smaller than the digit immediately to its right. This is the "breakpoint."
Step 3: Starting from the rightmost digit, locate the smallest digit that is larger than the digit at the breakpoint.
Step 4: Swap the digit at the breakpoint with the smallest larger digit found in the previous step.
Step 5: Reverse the digits to the right of the breakpoint to form the smallest possible number greater than the original.
Dry Run
Input: 5673543
Output: 5674335
Explanation: The next greater element for the given one is 5674335
Convert to List of Digits:
digits = ['5', '6', '7', '3', '5', '4', '3']
Find the Breakpoint:
Start from the right:
- Compare 4 > 3 (no break).
- Compare 5 > 4 (no break).
- Compare 3 < 5 (break found at index 3).
Find the Smallest Larger Digit:
Check digits to the right of index 3 (['5', '4', '3']).
- The smallest digit larger than 3 is 4 (at index 5).
Swap the Digits:
Swap digits[3] and digits[5]: Result: ['5', '6', '7', '4', '5', '3', '3']
Reverse the Digits After the Breakpoint:
Reverse the sublist after index 3 (['5', '3', '3']):
- Reversed sublist: ['3', '3', '5']
- Updated list: ['5', '6', '7', '4', '3', '3', '5']
Combine the Digits Back:
Join the digits in the list: '5674335'
Return the Integer of the Resultant String:
Result = 5674335
Optimal Code in all Languages
1. C++ Try on Compiler
class Solution {
public:
int nextGreaterElement(int n) {
// Convert the integer to a string for easy manipulation
string nums = to_string(n);
// Step 1: Find the first digit that is smaller than the digit next to it, from right to left
int i = nums.length() - 1;
while (i > 0 && nums[i - 1] >= nums[i]) {
i--;
}
// If no such digit is found, the number is the largest possible permutation
if (i == 0) {
return -1;
}
// Step 2: Find the smallest digit to the right of nums[i - 1] that is larger than nums[i - 1]
int j = nums.length() - 1;
while (j > i - 1 && nums[j] <= nums[i - 1]) {
j--;
}
// Step 3: Swap the two digits identified in steps 1 and 2
swap(nums[i - 1], nums[j]);
// Step 4: Reverse the digits after the position i-1 to get the smallest number
reverse(nums.begin() + i, nums.end());
// Convert the string back to an integer
long res = stol(nums);
// Step 5: Check if the result is within the 32-bit integer range
return (res <= INT_MAX) ? (int)res : -1;
}
};2. Java Try on Compiler
import java.util.Scanner;
public class Solution {
public int nextGreaterElement(int n) {
// Convert the integer to a character array for easy manipulation
char[] nums = Integer.toString(n).toCharArray();
// Step 1: Find the first digit that is smaller than the digit next to it, from right to left
int i = nums.length - 1;
while (i > 0 && nums[i - 1] >= nums[i]) {
i--;
}
// If no such digit is found, the number is the largest possible permutation
if (i == 0) {
return -1;
}
// Step 2: Find the smallest digit to the right of nums[i - 1] that is larger than nums[i - 1]
int j = nums.length - 1;
while (j > i - 1 && nums[j] <= nums[i - 1]) {
j--;
}
// Step 3: Swap the two digits identified in steps 1 and 2
char temp = nums[i - 1];
nums[i - 1] = nums[j];
nums[j] = temp;
// Step 4: Reverse the digits after the position i-1 to get the smallest number
reverse(nums, i, nums.length - 1);
// Convert the character array back to an integer
long res = Long.parseLong(new String(nums));
// Step 5: Check if the result is within the 32-bit integer range
return (res <= Integer.MAX_VALUE) ? (int) res : -1;
}
// Helper method to reverse a portion of the array
private void reverse(char[] nums, int start, int end) {
while (start < end) {
char temp = nums[start];
nums[start] = nums[end];
nums[end] = temp;
start++;
end--;
}
}
}3. Python Try on Compiler
class Solution:
def nextGreaterElement(self, n: int) -> int:
# Convert the integer to a list of characters for easy manipulation
nums = list(str(n))
# Step 1: Find the first digit that is smaller than the digit next to it, from right to left
i = len(nums) - 1
while i > 0 and nums[i-1] >= nums[i]:
i -= 1
# If no such digit is found, the number is the largest possible permutation
if i == 0:
return -1
# Step 2: Find the smallest digit to the right of nums[i-1] that is larger than nums[i-1]
j = len(nums) - 1
while j > i-1 and nums[j] <= nums[i-1]:
j -= 1
# Step 3: Swap the two digits identified in steps 1 and 2
nums[i-1], nums[j] = nums[j], nums[i-1]
# Step 4: Reverse the digits after the position i-1 to get the smallest number
nums[i:] = nums[i:][::-1]
# Convert the list back to an integer
res = int(''.join(nums))
# Step 5: Check if the result is within the 32-bit integer range
return res if res < 2**31 else -14. JavaScript Try on Compiler
// Function to find the next greater element
var nextGreaterElement = function (n) {
// Convert the number to a string and then to an array of digits
let digits = n.toString().split('');
// Step 1: Find the first decreasing element from the right
let i = digits.length - 2;
while (i >= 0 && digits[i] >= digits[i + 1]) {
i--;
}
// If no such element exists, there's no greater permutation
if (i < 0) {
return -1;
}
// Step 2: Find the smallest number greater than digits[i] on its right
let j = digits.length - 1;
while (digits[j] <= digits[i]) {
j--;
}
// Step 3: Swap digits[i] and digits[j]
[digits[i], digits[j]] = [digits[j], digits[i]];
// Step 4: Reverse the digits after the index i to get the smallest possible number
let left = digits.slice(0, i + 1);
let right = digits.slice(i + 1).reverse();
digits = left.concat(right);
// Convert the array of digits back to a number
let result = Number(digits.join(''));
// Step 5: Check if the result exceeds the integer range
if (result > Math.pow(2, 31) - 1) {
return -1;
}
return result;
};
Time Complexity: O(d)
Traversing List : We traverse the list to find the break point and the smallest larger digit.So utmost we travel the whole array - O(d).
Reversing : We reverse the sublist after the swap - O(d/2).
Thus, the overall time complexity is O(d) + O(d/2) ≈ O(d).
Here, d is the length of the giving permutation(nums)
Space Complexity: O(d)
Auxiliary Space Complexity: - Auxiliary space is the extra space or temporary space used by an algorithm apart from the input.
- Traversing : We use a pointer for traversing the list - O(1)
Total space complexity
Space for input integer array- O(d)
Auxiliary space for pointer - O(1)
Total space complexity - O(d) + O(1) ≈ O(d)
Here, d is the length of the given permutation(nums)
Learning Tip
The next greater element of some element x in an array is the first greater element that is to the right of x in the same array.
You are given two distinct 0-indexed integer arrays nums1 and nums2, where nums1 is a subset of nums2.
For each 0 <= i < nums1.length, find the index j such that nums1[i] == nums2[j] and determine the next greater element of nums2[j] in nums2. If there is no next greater element, then the answer for this query is -1.
Return an array ans of length nums1.length such that ans[i] is the next greater element as described above
Given a circular integer array nums (i.e., the next element of nums[nums.length - 1] is nums[0]), return the next greater number for every element in nums.
The next greater number of a number x is the first greater number to its traversing-order next in the array, which means you could search circularly to find its next greater number. If it doesn't exist, return -1 for this number.