DEV Community

Cover image for Leetcode 31 : Next Permutation
Rohith V
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;
    }
}
Enter fullscreen mode Exit fullscreen mode

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).

Github link :

GitHub logo Rohithv07 / LeetCode

LeetCode problems that are solved.

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));

A Sample Structure




GitHub logo Rohithv07 / LeetCodeTopInterviewQuestions

Leetcode Top Interview questions discussed in Leetcode. https://leetcode.com/explore/interview/card/top-interview-questions




Top comments (0)