{x}
blog image

Previous Permutation With One Swap

Given an array of positive integers arr (not necessarily distinct), return the lexicographically largest permutation that is smaller than arr, that can be made with exactly one swap. If it cannot be done, then return the same array.

Note that a swap exchanges the positions of two numbers arr[i] and arr[j]

 

Example 1:

Input: arr = [3,2,1]
Output: [3,1,2]
Explanation: Swapping 2 and 1.

Example 2:

Input: arr = [1,1,5]
Output: [1,1,5]
Explanation: This is already the smallest permutation.

Example 3:

Input: arr = [1,9,4,6,7]
Output: [1,7,4,6,9]
Explanation: Swapping 9 and 7.

 

Constraints:

  • 1 <= arr.length <= 104
  • 1 <= arr[i] <= 104

Solution Explanation: Previous Permutation With One Swap

This problem asks to find the lexicographically largest permutation of the input array arr that is smaller than the input and can be achieved with exactly one swap. If no such permutation exists, the original array is returned.

Approach:

The solution employs a greedy approach. It iterates through the array from right to left, looking for a pair of elements that can be swapped to create a smaller lexicographical order.

  1. Find the First Descent: The algorithm first searches for the rightmost index i where arr[i-1] > arr[i]. This indicates a "descent" in the array – a point where the elements are not in decreasing order from right to left. If no such i is found, the array is already in the smallest possible permutation.

  2. Find the Swap Candidate: Once i is found, we look for the rightmost element arr[j] to the right of i such that arr[j] < arr[i-1] and arr[j] is not equal to the element immediately to its left (arr[j-1]). This condition ensures we find the largest possible element smaller than arr[i-1] to maintain lexicographically largest order while ensuring only one swap is performed.

  3. Swap and Return: If both i and j are found, arr[i-1] and arr[j] are swapped. The modified array represents the lexicographically largest permutation smaller than the input achieved through a single swap.

  4. No Swap Possible: If the loop completes without finding a suitable i, it means no single swap can produce a smaller lexicographically ordered array. The original array is returned.

Time and Space Complexity:

  • Time Complexity: O(n) - The algorithm iterates through the array at most twice (once to find i and once to find j). The operations within the loops are constant time.

  • Space Complexity: O(1) - The algorithm uses only a constant amount of extra space, regardless of the input array size.

Code Examples:

The code examples provided in Python, Java, C++, Go, and TypeScript all implement the same algorithm with minor syntactic differences. They each follow these steps:

  1. Iterate from right to left searching for index i where arr[i-1] > arr[i].
  2. If i is found, iterate from right to left again searching for index j where arr[j] < arr[i-1] and arr[j] != arr[j-1].
  3. If j is found, swap arr[i-1] and arr[j] and return the array.
  4. If no such i is found, return the original array.

Each code example has comments for better understanding. The core logic remains the same across all languages.