Abstract / Summary

Find the largest index where a number can be swapped with a smaller number to its right to make the sequence smaller with just one swap.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 49% (90k+ submissions).

Typical patterns to solve this problem:

• Array
• Greedy

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The routine implements a single-swap algorithm that produces the lexicographically largest permutation that is still smaller than the input array. It works by locating the first position from the right where the ordering breaks, then swapping that element with the greatest possible smaller value that appears later in the array. The function returns the modified list in place.

Key Steps

The first phase walks backward through the list to find a pair of adjacent elements that are out of non-decreasing order. This identifies the pivot index where a reduction can be made.

size = len(arr)

for i in reversed(range(size - 1)):
    if arr[i] > arr[i + 1]:
        # pivot found at index i
        ...
        break

Once the pivot is found, a second reverse scan searches the suffix for the largest element that is still smaller than the pivot value. The scan keeps track of the current best candidate (high) and its position (pos). The inner loop updates these variables whenever it encounters a value that lies strictly between high and the pivot.

high = arr[i + 1]
pos  = i + 1
for j in reversed(range(i + 1, size)):
    if high < arr[j] < arr[i]:
        high = arr[j]
        pos  = j

        if high == arr[i] - 1:   # early exit
            break

After the optimal candidate is identified, a single swap exchanges the pivot with the selected element, and the outer loop terminates.

arr[i], arr[pos] = arr[pos], arr[i]
break

Finally, the possibly altered array is returned.

return arr

Edge Cases Handled

When the input list is already sorted in non-decreasing order, the outer loop never encounters a decreasing pair, so the body of the conditional is never executed. In that situation the function reaches the return statement without performing any swap, correctly returning the original array because no smaller permutation exists.

The algorithm also copes with duplicate values. Because the inner condition requires the candidate to be strictly less than the pivot (arr[j] < arr[i]) but greater than the current high, it naturally selects the rightmost occurrence of the largest permissible value. This ensures that swapping does not introduce a larger element earlier in the sequence, preserving the “previous” ordering even when equal numbers are present.

The early-exit check if high == arr[i] - 1 handles the scenario where the best possible smaller value (exactly one less than the pivot) has been found. As soon as such a value appears, the inner loop stops scanning, guaranteeing that the algorithm does not waste time examining remaining elements that cannot improve the result.

Performance Optimizations

Scanning the array from right to left eliminates the need to examine elements that cannot affect the result, because any change to the left of the first decreasing pair would produce a permutation that is not the immediate predecessor. The reverse iteration also aligns with the natural ordering of the suffix, allowing the inner loop to stop early when the optimal candidate is discovered.

The inner loop maintains a running high value instead of collecting all candidates and then sorting them. By updating high only when a better candidate is found, the algorithm avoids extra data structures and reduces overhead.

The early-exit condition inside the inner loop (high == arr[i] - 1) provides a constant-time shortcut for the best possible case. When the pivot can be reduced by exactly one, no further search is necessary, and the loop terminates immediately.

Overall, the combination of reverse traversal, in-place updates, and early termination yields a solution that performs the minimal amount of work required to locate the correct swap positions.

Imagine you have a long line of blocks with numbers written on them. You want to make the line of numbers look just a tiny bit smaller by swapping two of them. To do this, look at the blocks starting from the very end of the line and move toward the beginning. Whenever you see a number that is bigger than the one right next to it on the right, you have found a special spot.

At that spot, look at all the blocks to the right side of it. You want to find one that is smaller than your current block but as big as possible. Once you find that perfect block, switch the places of the two blocks. After you do that one swap, the job is finished and the blocks are in their new order.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

not analyzed yet

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Python		Java			TS
	WalkCCC	C++	Python		Java
	leetcode.ca	C++	Python		Java		Go	TS
	LeetcodeHelp	C++	Python		Java
	Progiez	C++	Python		Java
github	black-shadows	C++
	charles-wangkai				Java
	everthis			JS
	fsq	C++
	Garvit244		Python
	JoshCrozier			JS
	lzl124631x	C++
	suxrobGM					C#
	trung-hn		Python
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fsq	C++
Garvit244	Python
JoshCrozier	JavaScript
lzl124631x	C++
suxrobGM	C#
trung-hn	Python

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality