CA 12 - Next Permutation

Problem Statement: here PS Understanding: We have to find the arrangement of numbers that is immediately bigger than the current one. Solution: 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] left, right = i + 1, n - 1 while left < right: nums[left], nums[right] = nums[right], nums[left] left += 1 right -= 1 We have numbers like: [1, 2, 3] and we want to make the next bigger arrangement using the same numbers. Example: 123 → next is 132 132 → next is 213 213 → next is 231 1. Start from the right end and check if the number before is less than it. eg. in [1,2,3] find where left < right 2 < 3 → this is the spot So mark index of 2 2. Find a slightly bigger number on the right Now look to the right of 2: [3] Find a number just bigger than 2 → that is 3. 3. Swap them Swap 2 and 3 [1, 3, 2] 4. Fix the right side After swapping, take