Previous Permutation With One Swap

Previous Permutation With One Swap

What is this problem about?

The Previous Permutation With One Swap problem asks you to find the lexicographically largest permutation that is strictly smaller than the current one, achievable by exactly one swap of two elements. This coding problem uses a greedy right-to-left scan to find the optimal swap. The array and greedy interview pattern is the core.

Why is this asked in interviews?

Microsoft and Meta ask this as a variant of the Next Permutation problem — but in reverse direction. It tests whether candidates can adapt the standard permutation algorithm to find the previous rather than next permutation with a single swap constraint.

Algorithmic pattern used

Right-to-left scan + greedy swap. From right to left, find the first index i where arr[i] > arr[i+1] (descending). Then find the rightmost index j > i where arr[j] < arr[i] and arr[j] is not equal to any previous arr[j] for same value (pick leftmost of equal smaller values). Swap arr[i] and arr[j].

Example explanation

arr=[3,2,1]. Find first descending: i=1 (arr[1]=2 > arr[2]=1). Find largest j > 1 where arr[j] < arr[1]=2: j=2 (value 1). Swap: [3,1,2]. Result: [3,1,2].

arr=[1,9,4,6,7]. First descending: i=2 (arr[2]=4 < arr[3]=6? No, arr[3]=6>arr[4]=7? No, arr[2]=4 < arr[3]=6 not descending... Let me recheck: find where arr[i] > arr[i+1]. arr[3]=6 < arr[4]=7: no. arr[2]=4 < arr[3]=6: no. arr[1]=9 > arr[2]=4: yes, i=1). Find rightmost j > 1 where arr[j] < 9 and largest: j=4 (7). Swap: [1,7,4,6,9]. Result: [1,7,4,6,9].

Common mistakes candidates make

• Using the next permutation logic (going right instead of left).
• Not finding the rightmost occurrence of the largest smaller element.
• Handling duplicates incorrectly (if multiple elements equal the "best smaller," pick leftmost to get largest previous).
• Not returning the original array when already at smallest permutation.

Interview preparation tip

Previous Permutation With One Swap is the complement of Next Permutation. While next permutation finds a rightmost ascending pair (left of which has a smaller element), previous permutation finds a rightmost descending step (where a larger element sits left of smaller). Practice both together. The "rightmost" constraint for previous permutation ensures you make the minimal decrease needed for the largest possible previous permutation.