Sponsored
Sponsored
This approach uses the concept of finding the next permutation of the digits of the number. We traverse the digits from right to left to find the first digit that is smaller than the digit next to it. Once found, we swap it with the smallest larger digit on its right and then reverse the sequence following the swapped digit.
Time Complexity: O(n log n) (due to sorting in worst case)
Space Complexity: O(1) (in-place swap and conversion)
1class Solution {
2 public int nextGreaterElement(int n) {
3 char[] digits = Integer.toString(n).toCharArray();
4 int i = digits.length - 2;
5 while (i >= 0 && digits[i] >= digits[i + 1]) i--;
6 if (i < 0) return -1;
7 int j = digits.length - 1;
8 while (digits[j] <= digits[i]) j--;
9 swap(digits, i, j);
10 reverse(digits, i + 1, digits.length - 1);
11 try {
12 return Integer.parseInt(new String(digits));
13 } catch (NumberFormatException e) {
14 return -1;
15 }
16 }
17
18 private void swap(char[] arr, int i, int j) {
19 char temp = arr[i];
20 arr[i] = arr[j];
21 arr[j] = temp;
22 }
23
24 private void reverse(char[] arr, int start, int end) {
25 while (start < end) {
26 swap(arr, start, end);
27 start++;
28 end--;
29 }
30 }
31
32 public static void main(String[] args) {
33 Solution sol = new Solution();
34 System.out.println(sol.nextGreaterElement(12));
35 }
36}The Java solution similarly scans for a decreasing sequence, finds the first occurrence, swaps with a slightly larger digit on the right, and then reverses the remainder. Exception handling is used to catch 32-bit integer overflow conditions.
This approach entails understanding mathematical permutation generation principles. First, identify the point where the digits stop increasing when moving left-to-right, then swap it. Finally, regenerate that segment to form the smallest sequential increase.
Time Complexity: O(n^2) (as it checks for minimum swap position for small digits segment)
Space Complexity: O(n) (array storage)
1
Python's straightforward handling of larger integers aids as we build permutations with clever slice reusing, compounding shortened permutations backwards.