Is Previous Permutation With One Swap easy or hard?

Previous Permutation With One Swap is typically rated Medium difficulty. The challenge lies in recognizing the permutation pattern and selecting the correct element to swap when duplicates exist in the suffix.

Previous Permutation With One Swap Python/Java solution

Python and Java implementations follow the same steps: identify the pivot index with reverse traversal, locate the best smaller element in the suffix, and swap them. Since the operation modifies the array directly, both implementations run in O(n) time with O(1) extra space.

How to solve Previous Permutation With One Swap in O(n)?

Traverse the array from the end to find the first index i where nums[i] > nums[i+1]. Then search the suffix for the largest element smaller than nums[i], taking care to handle duplicates correctly. Swap those two values and return the array. This greedy strategy ensures only one pass plus a small suffix scan, giving O(n) time.

What is the best approach for Previous Permutation With One Swap?

The best approach uses a greedy reverse traversal. Scan from right to left to find the first index where nums[i] > nums[i+1], then find the largest value smaller than nums[i] in the suffix and swap them. This produces the largest permutation smaller than the original in O(n) time and O(1) space.

Is Previous Permutation With One Swap asked at Google/Amazon/Meta?

Permutation and greedy array problems similar to this appear frequently in interviews at companies like Amazon, Google, and Meta. The problem tests understanding of lexicographic permutations, greedy selection, and efficient array traversal patterns.

What data structure is used in Previous Permutation With One Swap?

The problem primarily uses arrays with a greedy scanning technique. The algorithm relies on reverse traversal of the array and selecting the correct swap candidate from the suffix to maintain the largest possible smaller permutation.

What is the time complexity of Previous Permutation With One Swap?

The optimal solution runs in O(n) time because the array is scanned from right to left to find the pivot and then scanned again to find the best swap candidate. Space complexity is O(1) since the swap is performed in place without extra data structures.

Description Hints 1 Solution Video 9:42

1053. Previous Permutation With One Swap

Medium49.5% acceptance2 companies

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 <= 10⁴
1 <= arr[i] <= 10⁴

Asked at 2 companies

NVIDIA Microsoft

Topics

Array Greedy

Hints open one at a time

Hint 1

You need to swap two values, one larger than the other. Where is the larger one located?

9:42

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def prevPermOpt1(self, arr: List[int]) -> List[int]:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3

Input

[3,2,1]

Input

[1,1,5]

Input

[1,9,4,6,7]

Your code is saved on this device.Solution