Next Integer Permutation - Amazon Top Interview Questions

                        Solution in C++ :

int solve(int n) {
    string s = to_string(n);
    int i = 0, j = 0;
    for (i = s.size() - 2; i >= 0; i--) {
        if (s[i] < s[i + 1]) break;
    }
    if (i < 0) {
        sort(s.begin(), s.end());
        return stoi(s);
    }
    for (j = s.size() - 1; j >= 0; j--) {
        if (s[j] > s[i]) break;
    }
    swap(s[i], s[j]);
    sort(s.begin() + i + 1, s.end());
    return stoi(s);
}
                    

                        Solution in Java :

import java.util.*;

class Solution {
    public int solve(int n) {
        ArrayList<Integer> ar = new ArrayList<>();
        int a = n;
        while (a > 0) {
            ar.add(a % 10);
            a = a / 10;
        }
        int arr[] = new int[ar.size()];
        int j = ar.size() - 1;
        for (int x : ar) {
            arr[j--] = x;
        }
        int mark = arr.length - 2;
        while (mark >= 0 && arr[mark + 1] <= arr[mark]) {
            mark--;
        }
        if (mark == -1) {
            reverse(arr, 0);
            return number(arr);
        }
        if (mark >= 0) {
            int k = arr.length - 1;
            while (k >= mark && arr[k] <= arr[mark]) {
                k--;
            }
            swap(arr, mark, k);
        }
        reverse(arr, mark + 1);
        return number(arr);
    }

    private int number(int nums[]) {
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum = sum * 10 + nums[i];
        }
        return sum;
    }
    private void reverse(int nums[], int start) {
        int i = start, j = nums.length - 1;
        while (i < j) {
            swap(nums, i, j);
            i++;
            j--;
        }
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}
                    

                        Solution in Python : 
                            
class Solution:
    def solve(self, num):
        # convert the number to a list of each digit
        A = list(map(int, str(num)))

        i = len(A) - 1

        # find the position of the rightmost element where we encounter
        # increasing comparison (A[i-1] < A[i])
        # for 527, this will be 27 and i = 2, A[i] = 7
        while i > 0 and A[i - 1] >= A[i]:
            i -= 1

        if i == 0:
            # if i == 0, it means the whole list was sorted in reverse order
            # in other words, it's already the highest permutation
            # so we just reverse it to get the smallest permutation
            A.reverse()
        else:
            j = len(A) - 1
            k = i - 1  # for 527: k = 1, A[k] = 2

            # starting from the position i-1, we go left to find the number
            # that's larger than the that number
            while A[j] <= A[k]:
                j -= 1
            A[j], A[k] = A[k], A[j]  # for 527, we swap 2 and 7 since j=2

            # we reverse the remaining part of the array
            # after the index k + 1, since it should be reset to
            # the smallest permutation
            left, right = k + 1, len(A) - 1
            while left < right:
                A[left], A[right] = A[right], A[left]
                left, right = left + 1, right - 1

        return int("".join(map(str, A)))