## DEV Community ๐ฉโ๐ป๐จโ๐ป is a community of 964,423 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

Rohith V

Posted on

# Leetcode 31 : Next Permutation

## Problem Statement

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such an arrangement is not possible, it must rearrange it as the lowest possible order (i.e., sorted in ascending order).

The replacement must be in place and use only constant extra memory.

## Test Cases

Example 1:

Input: nums = [1,2,3]
Output: [1,3,2]
Example 2:

Input: nums = [3,2,1]
Output: [1,2,3]
Example 3:

Input: nums = [1,1,5]
Output: [1,5,1]
Example 4:

Input: nums = [1]
Output: [1]

## Constraints

1 <= nums.length <= 100
0 <= nums[i] <= 100

## Algorithm :

1. Start traversing from the right to left.
2. Make sure while traversing from the right to left, we are having an increasing order pattern.
3. If this increasing order pattern continues until we complete the traversal, then the given array is in its greatest permutation possible and there are no other next greater permutation. This time just reverse the whole array.
4. Otherwise, if at any of the index say `i`, the increasing order pattern is violated, just stop at that position and mark it as the violated index.
5. Now from that violated index `i` search for another index `j` to the right of `i` such that there is a number `nums[j]` which is just greater than `nums[i]`.
6. After finding `j`, just swap the numbers at `nums[i]` and `nums[j]`.
7. Now reverse the array from `i + 1` to `length - 1` where length is the size of array.
8. This will give us our next greater permuatation.

## Code

``````class Solution {
public void nextPermutation(int[] nums) {
if (nums == null || nums.length <= 1) {
return;
}
// we will be going from right to left and search for the index
int violatingIncreasingOrder = -1;
int length = nums.length;
for (int i=length - 1; i>0; i--) {
if (nums[i] > nums[i - 1]) {
violatingIncreasingOrder = i - 1;
break;
}
}
// if already in greatest form, then just reverse the whole array
if (violatingIncreasingOrder == -1) {
reverse(nums, 0, length - 1);
return;
}
int nextGreaterElementOfI = nums[violatingIncreasingOrder + 1];
int violationNumber = nums[violatingIncreasingOrder];
int nextGreaterIndex = violatingIncreasingOrder + 1;
// find for the next greater index which is just greater than the violating number
for (int i=violatingIncreasingOrder + 1; i<length; i++) {
int currentNumber = nums[i];
if (currentNumber > violationNumber && currentNumber <= nextGreaterElementOfI) {
nextGreaterElementOfI = currentNumber;
nextGreaterIndex = i;
}
}
// reverse from the point of violation and the next greater element of that violation number
swap(nums, violatingIncreasingOrder, nextGreaterIndex);
reverse(nums, violatingIncreasingOrder + 1, length - 1);
}

private void reverse(int [] nums, int i, int j) {
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;
}
}
``````

## Complexity :

• Here we are traversing through the array from right to left one time and from the point of violation to right one time. So it will result in O(n) where n = size of array.

• We are not making use of any extra space, so space complexity is O(1).

# LeetCode

LeetCode problems that are solved.

• take the bit of the ith(from right) digit:

bit = (mask >> i) & 1;

• set the ith digit to 1: mask = mask | (1 << i);

• set the ith digit to 0: mask = mask & (~(1 << i));