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.

Examples

Example 1:

1
2

Input: n = 12
Output: 21

Example 2:

1
2

Input: n = 21
Output: -1

Example 3:

1
2

Input: n = 423862
Output: 426238

Here is a similar problem - Arrange Given Number To Form The Biggest Number Possible.

This is also similar code: Next Greater number with given set of digits

Solution

Method 1 - Greedy Approach

Lets look at example 3 - 423862.

  • Go through each digit from right to left.
  • Find the first digit that is not in descending order. In the example, it’s 3, 423862.
  • For all digits after the current digit (862), find the smallest one that is also greater than the current digit, which is 6. Swap it with the current digit. ⇨ 423862
  • So the current number is 426832.
  • The last step is to sort all digits after the current digit (6) in ascending order, so we get 426238.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

public int nextGreaterElement(int n) {
	char[] number = (n + "").toCharArray();

	int i, j;
	// I) Start from the right most digit and 
	// find the first digit that is
	// smaller than the digit next to it.
	for (i = number.length - 1; i > 0; i--) {
		if (number[i - 1]<number[i]) {
			break;
		}
	}

	// If no such digit is found, its the edge case 1.
	if (i == 0) {
		return -1;
	}

	// II) Find the smallest digit on right side of (i-1)'th 
	// digit that is greater than number[i-1]
	int x = number[i - 1], smallest = i;
	for (j = i + 1; j<number.length; j++) {
		if (number[j] > x && number[j]<= number[smallest]) {
			smallest = j;
		}
	}

	// III) Swap the above found smallest digit with 
	// number[i-1]
	char temp = number[i - 1];
	number[i - 1] = number[smallest];
	number[smallest] = temp;

	// IV) Sort the digits after (i-1) in ascending order
	Arrays.sort(number, i, number.length);

	long val = Long.parseLong(new String(number));
	return (val<= Integer.MAX_VALUE) ? (int) val : -1;
}

Complexity

  • ⏰ Time complexity: O( log n) where n is number of digits in number.
  • 🧺 Space complexity: O(1)