Introduction
In this series of "Leetcode" posts I will publish solutions to leetcode problems. It is true that you can find most/lots of leetcode solutions on the web, but I will try to post my solutions to problems that are interesting or to problems for which the solutions out there are not well explained and deserve a better explanation.
The aim is to share knowledge, and that people who are studying, preparing for interviews, or just practicing, can become better at solving problems. Please feel free to comment if you have a suggestion or a different approach!
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.
Solution
The main idea
- Start from the "end" of the number/digits.
- Find the indexes of the digits to swap in order to make the number greater.
- Swap the indexes.
- Sort the digits starting at swap index + 1.
- Create the new number.
Explanation and Code
The idea is to create a new number that is greater than the original number. But with the constraints that the new number must:
- Be the next smallest number
- Have the same digits
Basically you have to re-position the digits in such way that they are arranged to comply with the constraints. If there is not such number just return -1.
The second constraint: Have the same digits, helps to understand that there is no need to add/remove any digits. We just need to play with the digits we already have.
First Idea: Permutation
If all it takes is to re-arrange, then you can be thinking: Permute. You can try to permute (complexity O(n^2)), and take the next greater number out of all the possible arrangements, but the complexity is not optimal at all. Quadratic complexity is most of the time the worst possible possible solution in these types of problems, and most likely not a viable solution.So we have to think of something else.
Second Idea: Find and swap digits
We must find the next greater number with the digits we have. So we have to think what would be the next smallest number.
The example provided gives an idea:
Input: n = 12
Output: 21
The first thing you could be thinking is:
Find the next greatest digit that is greater than the first digit and swap them
That is not correct!. Let's see why.
For example if have:
Input: n = 54281
The first digit is: 5
The next greatest digit: 8
If you swap the digits you obtain:
Output: 84251
That is not the next greater number. The next greater number would be:
54821
You can create more examples. But at the end, you would realize that you need to start from the end of the number and not from the start of it.
Now it comes down to something simple:
Find the digit to replace
So which digit is that?.
You have to think what would make a number greater than another. The best way is to think of a 2 digit number:
35 => 53
So the first digit is 3, which is in the tens place. To make this number greater we would need to swap it with any digit greater than 3, that means any of {4,5,6,7,8,9}. But we only have 5, so we choose 5 and swap it.
But what happens if we have a bigger number, with more than 2 digits. I find it helpful to divide the number in 2 parts. You take a "digit" and you have all the digits before it and all the digits after it. For example:
Number: 823475321
We can take the digit: 4
Digits before: 823
Digits after: 75321
If we want to replace 4 we don't really care about the numbers before it, at least for now.
We want to find a number greater than 4, that is part of digits after 4, that means picking a digit from {7,5,3,2,1}. We must choose the next greatest digit, that means picking up 5, and then swap it:
Number: **823574321
Great we have a number greater than the original. But wait! That is not the next greater number. Look carefully, you can notice that we can arrange the numbers after the original digit(4), and create a smaller number. That means:
- Take the digits after 5(the swapped digit) : 74321.
- Now re-arrange them to get a smaller number: 12347
With this example it is easy to see how we should arrange those digits. Just sort them! Why?. Because if you sort them, it will put the smallest digit first, and then the next smallest, and so on. At the end you will obtain the smallest possible number with those digits.
It seems that we have a strategy, but the most important part is missing, how to find the digit to swap, in this example that was the number 4.
Find the number to Swap
We follow the same logic. Let's take the same example:
Number: 823475321
Start from the end. That means take the last digit 1.
But we cannot replace the last digit with anything, there is nothing after it, so move the left.We pick 2. We search in the digits after it: {1}. There are no greater digits, so we keep moving to the left.
We pick 3. We search in the digits after it: {2,1}. There are no greater digits, so we keep moving to the left.
...We do the same until we reach 4
- We pick 4. We search in the digits after it: {7,5,3,2,1}. Now we have numbers that are greater than 4, those are {7,5}, we pick the next greater number, that means 5.
Did you notice something? We kept moving as long there was no number greater than the current digit, on the numbers to its right or after it. So that's it, that is the algorithm:
- Start at position: end - 1
- Move to the left, until there is a number greater to the current digit in the digits to its right.
The code may look like this:
private int skipUntilDigitGreaterFound(char[] digits) {
int index = digits.length - 2;
while (index >= 0) {
addDigitToSeenDigits(digits[i+1]);
if (existsDigitGreaterThanCurrentInSeenDigits()) break;
index--;
}
return index;
}
But there is a big problem with this approach. The searching in the digits to the right of the current digit is the problem.
You can do a linear search (O(n)) in the seen set. Or you can take advantage of the fact that digits to the right must be sorted in the reverse order, this is a key fact to realize, and do a inverted binary search(O(log(n)).
But there is an even better approach in constant time: O(1)!
The idea is simple:
We are dealing with digits, we have a constant amount of digits: 10.
The only thing we care is finding the next bigger digit. So if we have the digit 4, we are looking if we have seen (digits to the right of 4 in the original number) a number greater than 4, which could be {5,6,7,8,9}.
So we can create an array of 10 elements(0 to 9) called: digitsPositions, where the index represents each digit, and the value represents the last found position of each digit.
When we want to find the position of a digit greater than a another, for instance: 4, we simple start at immediate next digit: 5, and see if there is some value set in the digitsPositions array for that index 5. If there is, that means we already saw that digit, and that's it we have the next bigger digit. If not, we keep on searching with the next digit: 6 and so on.
At most we would do a search for 10 elements (from 0 to 9) in the array. That means, constant time for searching.
In code we have something like this:
// Skip method, saves every "seen" digit in the digitsPositions array.
private int skipUntilDigitLessThanNext(char[] digits) {
int index = digits.length - 2;
while (index >= 0) {
digitsPositions[digits[index + 1] - '0'] = index + 1;
if (digits[index] < digits[index + 1]) break;
index--;
}
return index;
}
private int findGreaterIndex(int digit) {
for (int greaterDigit = digit + 1; greaterDigit < this.digitsPositions.length; greaterDigit++) {
if (digitsPositions[greaterDigit] > 0) return digitsPositions[greaterDigit];
}
return -1;
}
Notice that if have seen multiple times a digit we only save the last occurrence in the digitsPositions array. This does not matter at all because at the end we only care about finding that greater value and some index to replace with. After that the digits to the right of the swap are going to be sorted so no issues at all.
The complete solution
private final int[] digitsPositions = new int[10];
public int nextGreaterElement(int n) {
if (n < 10) return -1;
return findAndCreateNextGreaterElement(convertNumberToCharArray(n));
}
private char[] convertNumberToCharArray(int n) {
return String.valueOf(n).toCharArray();
}
private int findAndCreateNextGreaterElement(char[] digits) {
int indexToSwap = skipUntilDigitLessThanNext(digits);
if (indexToSwap < 0) return -1;
int digit = Character.getNumericValue(digits[indexToSwap]);
int greaterIndex = findGreaterIndex(digit);
return createNextGreaterNumber(digits, indexToSwap, greaterIndex);
}
private int skipUntilDigitLessThanNext(char[] digits) {
int index = digits.length - 2;
while (index >= 0) {
digitsPositions[digits[index + 1] - '0'] = index + 1;
if (digits[index] < digits[index + 1]) break;
index--;
}
return index;
}
private int findGreaterIndex(int digit) {
for (int greaterDigit = digit + 1; greaterDigit < this.digitsPositions.length; greaterDigit++) {
if (digitsPositions[greaterDigit] > 0) return digitsPositions[greaterDigit];
}
return -1;
}
private int createNextGreaterNumber(char[] digits, int indexToReplace, int greaterIndex) {
swap(digits, indexToReplace, greaterIndex);
Arrays.sort(digits, indexToReplace + 1, digits.length);
try {
return Integer.parseInt(new String(digits));
} catch (NumberFormatException exception) {
return -1;
}
}
private void swap(char[] digits, int currentIndex, int replaceIndex) {
char temp = digits[currentIndex];
digits[currentIndex] = digits[replaceIndex];
digits[replaceIndex] = temp;
}
Complexity
- Time: O(n) + O(nlog(n)), in the worst case we would have to go all the way to the first digit, remember we start from the end, that would be the O(n). After the swap, we need to sort the numbers to the right, and in the worst case the swap position would be 0, again at the start, so that would be O(n(log(n)).
We are only going to search through the digitsPositions once, and that is O(1).
- Space: O(1), we are only creating a the digitsPositions array, of size 10.
Another solution:
This was a very interesting problem, where there are many interesting parts to analyze before coming up with the most optimal solution. Again this problem can be one of the divide and conquer, where we split the bigger problem in smaller ones, in this case: find the swap digit and search for the greater digit. Usually it is useful to think in smaller cases and go from there. That helped me a lot for coming up with this solution.
Top comments (0)