Finding the Next Higher Number With the Same Digits

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:

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.