Next Permutation Problem: A Step-by-Step Guide

In this article, we will discuss the Next Permutation problem, which is a common algorithmic challenge. The task is to rearrange an array of integers into its next lexicographical permutation. If no such permutation exists (i.e., the array is sorted in descending order), we rearrange the numbers into the lowest possible order (ascending order).

Problem Explanation

Given an array arr[] representing a permutation of integers, our goal is to find the next permutation in lexicographical order. If the current permutation is the largest possible (sorted in descending order), we return the smallest permutation (sorted in ascending order).

Examples:

1. Input: arr = [2, 4, 1, 7, 5, 0]Output: [2, 4, 5, 0, 1, 7]Explanation: The next permutation of [2, 4, 1, 7, 5, 0] is [2, 4, 5, 0, 1, 7].
2. Input: arr = [3, 2, 1]Output: [1, 2, 3]Explanation: Since this array is sorted in descending order (the largest permutation), the next permutation is the smallest one: [1, 2, 3].

Solution Approach

The solution to this problem can be broken down into a few simple steps:

Step-by-Step Explanation:

1. Find the Breakpoint:Traverse the array from right to left and find the first element that violates the descending order. This element is called the breakpoint. It marks where we can make a change to find a larger permutation.For example, in [2, 4, 1, 7, 5, 0], the breakpoint is 1 because 1 < 7.
2. Find the Smallest Larger Element:Once we have identified the breakpoint (arr[break_point]), we need to find the smallest element on its right that is larger than arr[break_point]. This ensures that we get the next greater permutation.In our example [2, 4, 1, 7, 5, 0], after finding 1 as the breakpoint element at index 2, we look for the smallest number larger than 1 on its right side. That number is 5.
3. Swap Elements:Swap arr[break_point] with this smallest larger element found in step #2.After swapping in our example: [2, 4, *5*, *7*, *1*, *0*].
4. Reverse the Right Half:Finally, reverse all elements to the right of break_point. This ensures that these elements are arranged in ascending order to give us the next lexicographical permutation.After reversing: [2, 4, *5*, *0*, *1*, *7*].

Edge Case:

• If no breakpoint is found (i.e., if the array is sorted in descending order like [3, 2, 1]), simply reverse the entire array to get it sorted in ascending order.

Code Implementation

Here’s how you can implement this solution in Python:

class Solution:
    def reverse(self, arr, start, end):
        while start < end:
            arr[start], arr[end] = arr[end], arr[start]
            start += 1
            end -= 1

    def nextPermutation(self, arr):
        # Step 1: Find break point
        i = len(arr) - 2
        while i >= 0:
            if arr[i] < arr[i + 1]:
                break_point = i
                break
            i -= 1
        
        # Step 2: If no break point found (array is sorted in descending order)
        if i == -1:
            self.reverse(arr, 0, len(arr) - 1)
            return arr
        
        # Step 3: Find element just larger than break_point element
        i = len(arr) - 1
        while i > break_point:
            if arr[i] > arr[break_point]:
                # Step 4: Swap with break point
                arr[break_point], arr[i] = arr[i], arr[break_point]
                break
            i -= 1
        
        # Step 5: Reverse elements after break point
        self.reverse(arr, break_point + 1, len(arr) - 1)
        
        return arr        

Time and Space Complexity

• Time Complexity: The time complexity of this solution is O(n)O(n), where nn is the length of the array. The algorithm performs linear passes over the array multiple times (finding the breakpoint and reversing part of the array).
• Space Complexity: The space complexity is O(1)O(1) because we are modifying the input array in place without using any additional data structures.

Conclusion

The Next Permutation problem can be efficiently solved by identifying a breakpoint where we can make a change and then reversing part of the array to ensure that we get the smallest possible lexicographical permutation. This approach runs in linear time and uses constant space.By following these steps and understanding how permutations work lexicographically, you can solve similar problems with ease!