Next Permutation

In this task, I worked on finding the next lexicographically greater permutation of a given array. If such a permutation is not possible, we rearrange it to the smallest possible order (ascending).

WHAT I DID
I created a function that modifies the array to its next permutation in-place.

EXAMPLE
Input : arr[1,2,3]
ouput : [2,1,3],[1,3,2]

LOGIC IMPLEMENTED
Find index i such that:
nums[i] < nums[i+1]

Find index j such that:
nums[j] > nums[i]

Swap nums[i] and nums[j]
Reverse elements from i+1 to end

HOW IT WORKS

1. The algorithm finds the first place where order breaks from the right
2. Then it swaps with the next larger number
3. Finally, it rearranges the remaining elements to get the smallest possible order

class Solution:
    def nextPermutation(self, nums):
        n = len(nums)
        i = n - 2

        # Step 1: find first decreasing element
        while i >= 0 and nums[i] >= nums[i + 1]:
            i -= 1

        if i >= 0:
            j = n - 1

            # Step 2: find element just greater than nums[i]
            while nums[j] <= nums[i]:
                j -= 1

            # Step 3: swap
            nums[i], nums[j] = nums[j], nums[i]

        # Step 4: reverse the remaining array
        left, right = i + 1, n - 1
        while left < right:
            nums[left], nums[right] = nums[right], nums[left]
            left += 1
            right -= 1

TIME COMPLEXITY
Time Complexity: O(n)
Space Complexity: O(1)