## 1. Introduction

In this tutorial, we’ll learn how to find the next higher number with the same set of digits as the original number in Java. This problem can be solved by using the concept of permutation, sorting, and a two-pointer approach.

## 2. Problem Statement

Given a positive integer, we need to find the next higher number that uses the exact same set of digits. For example, if the input is 123, we aim to rearrange its digits to form the next higher number with the same digits. In this case, the next higher number would be 132.

If the input is 654 or 444, then we return -1 to indicate that there is no next higher number possible.

## 3. Using Permutation

In this approach, we’ll utilize permutation to find the next greater number with the same digits as the input number. **We’ll generate all possible permutations of the digits in the input number and add them to a ***TreeSet* to ensure uniqueness and ordering.Â

### 3.1. Implementation

**First, we implement a method ***findPermutations()* to generate all permutations of the digits in the input number *num* and add them to a *TreeSet*:

```
void findPermutations(int num, int index, StringBuilder sb, Set<Integer> hs) {
if (index == String.valueOf(num).length()) {
hs.add(Integer.parseInt(sb.toString()));
return;
}
//...
}
```

The method first checks if the current *index* is equal to the length of the input number. If so, it means that a permutation has been fully generated, then we add the permutation to the *TreeSet* and return to end the recursion.

**Otherwise, we iterate over the digits of the number starting from the current ***index *to generate all the permutations:

```
for (int i = index; i < String.valueOf(num).length(); i++) {
char temp = sb.charAt(index);
sb.setCharAt(index, sb.charAt(i));
sb.setCharAt(i, temp);
//...
}
```

** **At each iteration, we swap the character at the current index *index* with the character at the iteration index *i*. **This swapping action effectively creates different combinations of digits.**

Following the swapping, the method recursively calls itself, with the updated *index* and the modified *StringBuilder*:

```
findPermutations(num, index + 1, sb, hs);
temp = sb.charAt(index);
sb.setCharAt(index, sb.charAt(i));
sb.setCharAt(i, temp); // Swap back after recursion
```

After the recursive call, we swap the characters back to their original positions to maintain the integrity of *sb* for subsequent iterations.

Let’s encapsulate the logic within a method:

```
int findNextHighestNumberUsingPermutation(int num) {
Set<Integer> hs = new TreeSet();
StringBuilder sb = new StringBuilder(String.valueOf(num));
findPermutations(num, 0, sb, hs);
for (int n : hs) {
if (n > num) {
return n;
}
}
return -1;
}
```

**Once all permutations are generated, we iterate through the ***TreeSet* to find the smallest number greater than the input number.Â If such a number is found, it’s the next greater number. Otherwise, we return *-1* to indicate that no such number exists.

### 3.2. Testing

Letâ€™s validate the permutation solution:

```
assertEquals(536497, findNextHighestNumberUsingPermutation(536479));
assertEquals(-1, findNextHighestNumberUsingPermutation(987654));
```

### 3.3. Complexity Analysis

**The time complexity of this implementation is ***O(n!)* in the worst case, where *n* is the number of digits in the input number. The *findPermutations()* function generates all possible permutations of the digits *n!*, which remains the dominant factor in time complexity.

While *TreeSet* provides logarithmic complexity *(log n)* for insertion and retrieval, it doesn’t significantly impact the overall time complexity.

**In the worst case, where all permutations are unique (no duplicates), the ***TreeSet* could potentially hold all *n!* permutations of the digits. This leads to a space complexity of *O(n!)*.

## 4. Using Sorting

In this method, we’ll employ a sorting approach to determine the next greater number with the same digits as the given input number.

### 4.1. Implementation

We begin by defining a method named *findNextHighestNumberUsingSorting()*:

```
int findNextHighestNumberUsingSorting(int num) {
String numStr = String.valueOf(num);
char[] numChars = numStr.toCharArray();
int pivotIndex;
// ...
}
```

**Inside the method, we convert the input number into a string and then into a character array.** We also initialize a variable *pivotIndex* to identify the pivot point.

Next, we iterate over the *numChars* array from the rightmost digit to the left to identify the largest digit that is smaller than or equal to its right neighbor:

```
for (pivotIndex = numChars.length - 1; pivotIndex > 0; pivotIndex--) {
if (numChars[pivotIndex] > numChars[pivotIndex - 1]) {
break;
}
}
```

This digit becomes the pivot point to identify the breaking point in the descending order of digits. **If this condition is true, it means we’ve found a digit that is larger than its neighbor to the left (potential pivot). **Then we break the loop because we don’t need to search further for a larger descending digit.

If no such pivot is found, it means that the number is already in descending order, therefore we return *-1*:

```
if (pivotIndex == 0) {
return -1;
}
```

After identifying the pivot, the code searches for the smallest digit to the right of the pivot that is still greater than the pivot itself:

```
int pivot = numChars[pivotIndex - 1];
int minIndex = pivotIndex;
for (int j = pivotIndex + 1; j < numChars.length; j++) {
if (numChars[j] > pivot && numChars[j] < numChars[minIndex]) {
minIndex = j;
}
}
```

**This digit are swapped with the pivot later to create the next larger number.** We iterate through the array starting from one position after the pivot using a loop to find the smallest digit that is greater than the pivot.

Once the minimum digit greater than the pivot is found, we swap its position with the pivot:

`swap(numChars, pivotIndex - 1, minIndex);`

**This swap essentially brings the smallest digit that can be greater than the pivot to the position right before the pivot.**

To create the next lexicographically larger number, the code needs to sort the digits to the right of the pivot in ascending order:

```
Arrays.sort(numChars, pivotIndex, numChars.length);
return Integer.parseInt(new String(numChars));
```

This results in the smallest permutation of the digits that is greater than the original number.

### 4.2. Testing

Now, let’s validate our sorting implementation:

```
assertEquals(536497, findNextHighestNumberUsingSorting(536479));
assertEquals(-1, findNextHighestNumberUsingSorting(987654));
```

In the first test case, the *pivot* is found at the index *4* (digit *7*). Next, to find the smallest digit larger than the *pivot* (*7*), we iterate from *pivotIndex + 1* to the end. *9* is greater than *pivot* (*7*) so the minimum digit greater than the *pivot* is found at the index *5* (digit* 9*).

Now, we swap *numChars[4] (7)* with *numChars[5] (9). *After we do the swapping and sorting, the *numChars* array becomes *[5, 3, 6, 4, 9, 7]*.

### 4.3. Complexity Analysis

**The time complexity of this implementation is ***O(n log n)* and the space complexity is *O(n)*. This is because the implementation of sorting the digits is in *O(n log n)* time and uses a character array to store the digits.

## 5. Using Two Pointers

This approach is more efficient than sorting. It utilizes two pointers to find the desired digits and manipulate them for the next higher number.

### 5.1. Implementation

Before we start the main logic, we create two helper methods to simplify the manipulation of characters within the array:

```
void swap(char[] numChars, int i, int j) {
char temp = numChars[i];
numChars[i] = numChars[j];
numChars[j] = temp;
}
void reverse(char[] numChars, int i, int j) {
while (i < j) {
swap(numChars, i, j);
i++;
j--;
}
}
```

Then we begin by defining a method named *findNextHighestNumberUsingTwoPointer()*:

```
int findNextHighestNumberUsingTwoPointer (int num) {
String numStr = String.valueOf(num);
char[] numChars = numStr.toCharArray();
int pivotIndex = numChars.length - 2;
int minIndex = numChars.length - 1;
// ...
}
```

Inside the method, Â we convert the input number to a character array and initialize two variables:

*pivotIndex*: to track the pivot index from the right side of the array
*minIndex*: to find a digit greater than the pivot

We initialize the *pivotIndex *to the second last digit because if starts from the last digit (i.e., numChars.length – 1), there’s no digit to its right to compare it with. **Subsequently, we use a ***while* loop to find the first index *pivotIndex* from the right that has a digit smaller than or equal to the digit to its right:Â

```
while (pivotIndex >= 0 && numChars[pivotIndex] >= numChars[pivotIndex+1]) {
pivotIndexi--;
}
```

If the current digit is smaller, it means we’ve found the pivot point where the increasing trend breaks. Then the loop will be terminated.

If no such index is found, it means that the input number is the largest possible permutation, and there is no greater permutation possible:

```
if (pivotIndex == -1) {
result = -1;
return;
}
```

Otherwise, we use another *while* loop to find the first index *minIndex* from the right that has a digit that’s greater than the pivot digit *pivotIndex:*

```
while (numChars[minIndex] <= numChars[pivotIndex]) {
minIndex--;
}
```

Next, we swap the digits at indices *pivotIndex*Â andÂ *minIndex*Â using theÂ *swap()* function:

`swap(numChars, pivotIndex, minIndex);`

This swap operation ensures that we explore different combinations of digits while generating permutations.

**Finally, instead of sorting, we reverse the substring to the right of index ***pivotIndex *to obtain the smallest permutation greater than the original number*:*

```
reverse(numChars, pivotIndex+1, numChars.length-1);
return Integer.parseInt(new String(numChars));
```

This effectively creates the smallest possible number greater than the original number using the remaining digits.

### 5.2. Testing

Let’s validate the two pointers implementation:

```
assertEquals(536497, findNextHighestNumberUsingSorting(536479));
assertEquals(-1, findNextHighestNumberUsingSorting(987654));
```

In the first test case, the *pivotIndex* remains as its initialized value (*4*) because *numChars[4]* (*7*) isn’t greater than *numChars[5]* (*9*). Therefore, the *while* loop breaks immediately.

In the second *while* loop, *minIndex* remains as its initialize value (*5*) as the *numChars[5]* (*9*) is not smaller than *numChars[4]* (*7*). Again, the *while* loop terminated.

Next, we swap *numChars[4] (7)* with *numChars[5] (9). *Since *pivotIndex + 1* is *5* and *minIndex* is also *5*, no reversing is needed. The *numChars *array becomes *[5, 3, 6, 4, 9, 7].*

### 5.3. Complexity Analysis

**In the worst case, the loops iterating over the digits might traverse the entire character array ***numChars*Â twice. This can happen when the input number is already in descending order (e.g., 987654).

**Therefore, the time complexity of the function is ***O(n)*. Moreover, the space complexity is *O(1) *because it uses a constant amount of extra space for pointers and temporary variables.

## 6. Summary

Here’s a table summarizing the comparison of the three approaches and recommended use cases:

Approach |
Time Complexity |
Space Complexity |
Use Case |

Permutation |
O(n!) |
O(n!) |
Use when the input number has a small number of digits |

Sorting |
O(n log n) |
O(n) |
Use when the simplicity of implementation is important |

Two Pointers |
O(n) |
O(1) |
Use when the input number has a large number of digits |

## 7. Conclusion

In this article, we’ve explored three different approaches to finding the next higher number with the same set of digits as the original number in Java. Overall, the two-pointer approach offers a good balance between efficiency and simplicity for finding the next higher number with the same set of digits.

As always, the source code for the examples is available over on GitHub.