Problem Description

Given an array of positive integers arr (not necessarily distinct), you need to find the lexicographically largest permutation that is smaller than arr by making exactly one swap. If no such permutation exists, return the original array unchanged.

A swap means exchanging the positions of two numbers arr[i] and arr[j] in the array.

To understand lexicographical ordering: an array is lexicographically smaller than another if at the first position where they differ, the first array has a smaller element. For example, [3,1,2] is lexicographically smaller than [3,2,1] because at index 1, we have 1 < 2.

The goal is to find the largest possible array that is still smaller than the original by swapping exactly one pair of elements. This means we want to make the smallest possible decrease to the array's lexicographical value.

For example:

• If arr = [3,2,1], we can swap 3 and 2 to get [2,3,1], which is lexicographically smaller than [3,2,1]
• If arr = [1,1,5], no single swap can make it smaller, so we return [1,1,5]
• If arr = [3,1,1,3], we can swap the first 3 with the second 1 to get [1,1,3,3]

The key challenge is identifying which two elements to swap to achieve the lexicographically largest result among all possible smaller permutations.

Intuition

To make the array lexicographically smaller with exactly one swap, we need to find a position where we can place a smaller number. Think about it from left to right - the leftmost position where we make a change will have the most significant impact on the lexicographical order.

However, we want the largest permutation that is smaller than the original. This means we should make the smallest possible decrease. So we need to:

1. Find the rightmost position where we can make a beneficial swap
2. At that position, swap with the largest possible smaller value

Let's think about when a swap can make the array smaller. If we have a decreasing sequence like [5,4,3,2,1], no swap can make it smaller - it's already the smallest possible arrangement of these numbers. But if we have any position where arr[i-1] > arr[i], that means there's a smaller number to the right that we could potentially swap with arr[i-1].

So our strategy becomes:

1. Find the swap position: Traverse from right to left to find the first position i-1 where arr[i-1] > arr[i]. This is the rightmost position where the array "increases" when viewed from right to left. This position i-1 is where we want to place a smaller number.

2. Find the best swap candidate: Once we know position i-1 needs a smaller value, we need to find which number to swap it with. We want the largest number that is still smaller than arr[i-1]. We search from the right again to find the rightmost such number (to get the largest possible value among candidates).

3. Handle duplicates: If there are duplicate values, we need to be careful. We should pick the rightmost occurrence of our chosen value to ensure we get the lexicographically largest result. That's why we check arr[j] != arr[j-1] - to avoid swapping with a duplicate that isn't the rightmost one.

This greedy approach works because making the swap as far right as possible (step 1) and choosing the largest valid replacement (step 2) ensures we get the lexicographically largest array that is smaller than the original.

Learn more about Greedy patterns.

Solution Approach

The implementation follows a greedy approach with two main scanning phases:

Phase 1: Find the position to swap from

We traverse the array from right to left (from index n-1 to 1):

for i in range(n - 1, 0, -1):
    if arr[i - 1] > arr[i]:

When we find the first position where arr[i-1] > arr[i], we've identified that arr[i-1] is the element that needs to be swapped. This is the rightmost position where we can make a beneficial swap to create a smaller permutation.

Phase 2: Find the best element to swap with

Once we've found position i-1, we need to find the best candidate to swap it with. We scan from the right again (from index n-1 to i-1):

for j in range(n - 1, i - 1, -1):
    if arr[j] < arr[i - 1] and arr[j] != arr[j - 1]:

The conditions here are crucial:

• arr[j] < arr[i - 1]: We need an element smaller than arr[i-1] to make the array lexicographically smaller
• arr[j] != arr[j - 1]: This ensures we pick the rightmost occurrence of a value when duplicates exist, giving us the lexicographically largest result among valid swaps

Perform the swap and return

When we find the suitable j, we swap the elements and immediately return:

arr[i - 1], arr[j] = arr[j], arr[i - 1]
return arr

Edge case: No valid swap exists

If we complete the first loop without finding any position where arr[i-1] > arr[i], it means the array is already in ascending order (like [1,2,3,4]) or is the smallest possible permutation of its elements. In this case, we return the original array unchanged.

The time complexity is O(n) where n is the length of the array, as we potentially scan the array twice in the worst case. The space complexity is O(1) as we only use a constant amount of extra space for the loop variables.

Example Walkthrough

Let's walk through the solution with arr = [3,1,1,3]:

Phase 1: Find the position to swap from

We scan from right to left looking for the first position where arr[i-1] > arr[i]:

• i = 3: arr[2] = 1, arr[3] = 3. Since 1 < 3, continue.
• i = 2: arr[1] = 1, arr[2] = 1. Since 1 = 1, continue.
• i = 1: arr[0] = 3, arr[1] = 1. Since 3 > 1, we found our position!

So i-1 = 0 is the position we need to swap from. We need to replace arr[0] = 3 with something smaller.

Phase 2: Find the best element to swap with

Now we scan from right to left (from index 3 to 1) to find the best candidate to swap with arr[0] = 3:

• j = 3: arr[3] = 3. Since 3 ≮ 3, continue.
• j = 2: arr[2] = 1. Check conditions:
  • arr[2] < arr[0]? Yes, 1 < 3 ✓
  • arr[2] != arr[1]? No, 1 = 1 ✗
  • Skip this position (it's not the rightmost occurrence of value 1)
• j = 1: arr[1] = 1. Check conditions:
  • arr[1] < arr[0]? Yes, 1 < 3 ✓
  • arr[1] != arr[0]? Yes, 1 ≠ 3 ✓
  • Found our swap candidate!

Phase 3: Perform the swap

Swap arr[0] and arr[1]:

• Before: [3,1,1,3]
• After: [1,3,1,3]

The result [1,3,1,3] is lexicographically smaller than [3,1,1,3] (comparing position 0: 1 < 3), and it's the largest such permutation achievable with one swap.

Note how the condition arr[j] != arr[j-1] helped us skip the duplicate at position 2 and choose the rightmost occurrence at position 1, ensuring we get the lexicographically largest result among all valid swaps.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the array. While the code contains nested loops, the outer loop traverses from right to left looking for the first position where arr[i-1] > arr[i]. Once such a position is found, the inner loop searches from the right for the largest element that is smaller than arr[i-1] and not a duplicate of its predecessor. After the swap is performed, the function returns immediately. In the worst case, the outer loop might traverse the entire array once, and for one iteration of the outer loop, the inner loop might also traverse a portion of the array once. However, since the function returns as soon as a valid swap is found, the total number of elements examined is at most 2n, giving us O(n) time complexity.

The space complexity is O(1) as the algorithm only uses a constant amount of extra space for the loop variables i and j, and performs the swap operation in-place without requiring any additional data structures that scale with the input size.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall: Not Handling Duplicate Values Correctly

One of the most common mistakes when solving this problem is failing to properly handle duplicate values when selecting which element to swap with. Consider this scenario:

Problem Example:

arr = [3, 1, 1, 3]

Incorrect Approach: If we don't check for duplicates and simply swap arr[i-1] with the first element we find that is smaller, we might swap with index 1 (the first 1), resulting in:

[1, 3, 1, 3]  # Not optimal!

Why This Is Wrong: The issue is that swapping with the leftmost occurrence of a duplicate value doesn't give us the lexicographically largest result. We want to minimize the change to the array, which means swapping with the rightmost valid element.

Correct Approach: By including the condition arr[j] != arr[j - 1] in our search, we ensure we skip over duplicate values and find the rightmost occurrence. This would correctly swap with index 2 (the second 1), giving us:

[1, 1, 3, 3]  # Optimal result

Solution to Avoid This Pitfall:

The key is the condition in the second loop:

if arr[j] < arr[i - 1] and arr[j] != arr[j - 1]:

The arr[j] != arr[j - 1] check serves two purposes:

1. Skip duplicates: When we encounter consecutive duplicate values, we skip all but the rightmost one
2. Maximize the result: By choosing the rightmost valid element to swap, we ensure the resulting permutation is as large as possible while still being smaller than the original

Alternative Implementation to Make Intent Clearer: If you want to make the duplicate handling more explicit, you could modify the code like this:

for j in range(n - 1, i - 1, -1):
    if arr[j] < arr[i - 1]:
        # Skip if this is not the rightmost occurrence of this value
        if j < n - 1 and arr[j] == arr[j + 1]:
            continue
        # Found the rightmost valid element to swap
        arr[i - 1], arr[j] = arr[j], arr[i - 1]
        return arr

This alternative makes it clearer that we're looking for the rightmost occurrence of each distinct value that satisfies our swap condition.