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)
1using System;
2
3public class Solution {
4 public int NextGreaterElement(int n) {
5 char[] digits = n.ToString().ToCharArray();
6 int i = digits.Length - 2;
7 while (i >= 0 && digits[i] >= digits[i + 1]) i--;
8 if (i < 0) return -1;
9 int j = digits.Length - 1;
10 while (digits[j] <= digits[i]) j--;
11 Swap(digits, i, j);
12 Array.Reverse(digits, i + 1, digits.Length - i - 1);
13 try {
14 return int.Parse(new string(digits));
15 } catch (OverflowException) {
16 return -1;
17 }
18 }
19
20 private void Swap(char[] arr, int i, int j) {
21 char temp = arr[i];
22 arr[i] = arr[j];
23 arr[j] = temp;
24 }
25
26 public static void Main() {
27 Solution sol = new Solution();
28 Console.WriteLine(sol.NextGreaterElement(12));
29 }
30}This C# implementation uses a character array to find the permutation in a similar pattern and includes exception handling to guard against integer overflows. Reversing and swapping are used to rearrange the digits appropriately.
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
This method parses digits from the number to locate the next higher permutation swap, initiating a reverse rotation to create the smallest increment. It precisely tracks indices, ensuring accurate results.