Next Permutation

In this task, I worked on finding the next permutation of a given array. A permutation means a different arrangement of the same elements, and the “next permutation” is the next greater arrangement in order.

What I Did

I created a function called nextPermutation that modifies the given array and gives the next possible arrangement.

For example:
Input: [2, 1, 5, 4, 3, 0, 0]
Output: [2, 3, 0, 0, 1, 4, 5]

How I Solved It

To solve this problem, I followed a step-by-step approach:

First, I started from the end of the array and looked for the first element that is smaller than the element next to it. This helps identify where the change needs to happen.

Once I found that position, I again searched from the end to find the next bigger element than that value and swapped them.

After swapping, I reversed the part of the array that comes after that position. This ensures that the new arrangement is the next smallest possible permutation.

Code

def nextPermutation(nums):
    n = len(nums)
    i = n - 2
    while i >= 0 and nums[i] >= nums[i + 1]:
        i -= 1
    if i >= 0:
        j = n - 1
        while nums[j] <= nums[i]:
            j -= 1
        nums[i], nums[j] = nums[j], nums[i]
    nums[i + 1:] = reversed(nums[i + 1:])
nums = [2, 1, 5, 4, 3, 0, 0]
print("Original:", nums)
nextPermutation(nums)
print("Next Permutation:", nums)

How It Works

The function works by identifying a point where the order stops increasing from the end. Then it swaps that element with a slightly bigger one and rearranges the remaining part to get the next closest permutation.

This approach avoids generating all permutations and directly finds the next one efficiently.