Sponsored
Sponsored
This approach involves transforming the current permutation into its next lexicographical order. The key operations include identifying the longest non-increasing suffix and swapping elements to get a slightly larger permutation, followed by reversing the suffix to get the lowest order.
Time Complexity: O(n), where n is the number of elements in the array. This is due to the maximal traversal and operations over the array.
Space Complexity: O(1) since the operation is performed in-place with constant memory usage.
1def nextPermutation(nums):
2 i = len(nums) - 2
3 while i >= 0 and nums[i] >= nums[i + 1]:
4 i -= 1
5 if i >= 0:
6 j = len(nums) - 1
7 while nums[j] <= nums[i]:
8 j -= 1
9 nums[i], nums[j] = nums[j], nums[i]
10 nums[i + 1:] = reversed(nums[i + 1:])
11
12if __name__ == "__main__":
13 nums = [1, 2, 3]
14 nextPermutation(nums)
15 print(nums)In Python, the solution determines the point of change by identifying a decrease, swaps the element for the next largest, and reverses the latter part of the array for the least permutation. This process leverages Python's innate ability to handle array slicing and obstruction-free swapping, guaranteeing minimal space use.