-
Notifications
You must be signed in to change notification settings - Fork 0
/
NextGreaterElement.java
66 lines (56 loc) · 1.96 KB
/
NextGreaterElement.java
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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
package dsalgo.leetcode;
import java.util.Arrays;
import dsalgo.util.ArrayUtils;
/**
* NextGreaterElement
* Find the smallest number that has same set of digits as given number
*
* @author Umang Gala
*/
public class NextGreaterElement {
/**
* <p>
* {@code NextGreaterElement} instance should NOT be constructed in standard
* programming, so its defined as private
* </p>
*/
private NextGreaterElement() {
}
/**
* nextGreaterElement
* function to returns smallest number greater than number with same set
* of digits
*
* @param number input number
* @return smallest number greater than number with same set of digits
*/
public static int nextGreaterElement(int number) {
char[] noDigits = Integer.toString(number).toCharArray();
int i;
// I) Start from the right most digit and find the first digit that is
// smaller than the digit next to it.
for (i = noDigits.length - 1; i > 0; i--) {
if (noDigits[i] > noDigits[i - 1])
break;
}
// If no such digit is found, then all digits are in descending order means
// there cannot be a greater number with same set of digits
if (i == 0)
return -1;
else {
int x = noDigits[i - 1], min = i;
// II) Find the smallest digit on right side of (i-1)'th digit that is
// greater than number[i-1]
for (int j = i + 1; j < noDigits.length; j++) {
if (noDigits[j] > x && noDigits[j] < noDigits[min]) {
min = j;
}
}
// III) Swap the above found smallest digit with number[i-1]
ArrayUtils.swapArrayElements(noDigits, i - 1, min);
// IV) Sort the digits after (i-1) in ascending order
Arrays.sort(noDigits, i, noDigits.length);
return Integer.parseInt(new String(noDigits));
}
}
}