Abstract / Summary

Find the fewest steps to make the last elements of all arrays equal by only increasing them.

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 44% (30k+ submissions).

Typical patterns to solve this problem:

• Array
• Enumeration

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 presented implementation solves a combinatorial decision problem: given two integer arrays nums1 and nums2, the goal is to determine the minimum number of element-wise swaps required so that every pair of corresponding elements respects two upper bounds defined by the last elements of the original arrays. If no sequence of swaps can satisfy the constraints, the function returns -1. The algorithm explores two high-level scenarios-keeping the original last elements in place or swapping them-while iterating through the remaining elements only once per scenario.

Core Logic

The function begins by extracting the terminal values of both input lists. These values serve as immutable thresholds for the rest of the computation. The extraction is performed with direct indexing and pop operations, which also shrink the input lists, simplifying later iteration.

last1 = nums1[-1]
last2 = nums2[-1]
nums1.pop()
nums2.pop()

A guard clause handles the degenerate case where the input lists originally contained a single element. After removing the last elements, both nums1 and nums2 become empty, and the function returns 0 because no swaps are needed.

if not nums1:
    return 0

The algorithm then enters a two-pass loop controlled by swapLast. The loop variable takes the values 0 and 1, representing the two possibilities: retain the original ordering of the last elements (swapLast == 0) or exchange them (swapLast == 1). The variable swaps is initialized with the current value of swapLast, accounting for the potential swap of the last elements.

for swapLast in range(2):
    swaps = swapLast
    okay  = True

Inside the loop, a zip iteration walks through the shortened nums1 and nums2 simultaneously. For each pair (one, two), the algorithm first checks whether the pair already satisfies the constraints (one <= last1 and two <= last2). If the condition holds, the loop proceeds without incrementing the swap counter.

for one, two in zip(nums1, nums2):
    if one <= last1 and two <= last2:
        continue

When the pair violates the constraints, the algorithm attempts a single swap of the two elements. The swap is performed by tuple unpacking, and the swap counter is incremented. After the swap, the constraints are re-evaluated. If the swapped pair still exceeds either threshold, the current scenario is marked as invalid by setting okay to False and breaking out of the inner loop.

    one, two = two, one
    swaps   += 1
    if one >  last1 or  two >  last2:
        okay = False
        break

If the entire pass completes without violating the constraints (okay remains True), the algorithm updates the global result with the smaller of its current value and the swaps counted in this scenario.

if okay:
    result = min(result, swaps)

At the end of each outer iteration, the thresholds last1 and last2 are swapped to reflect the alternative scenario for the next pass.

last1, last2 = last2, last1

Finally, the function returns the best result found, or -1 if no feasible configuration exists.

return result if result < +inf else -1

Edge Cases Handled

The code explicitly addresses the situation where the input arrays consist of a single element. By popping the last elements and checking for an empty remainder, it returns 0 without further processing, correctly handling the minimal input size.

Another implicit edge case is the possibility that the initial thresholds themselves are insufficient to accommodate any element from the other array, even after a swap. The inner loop’s early exit (break) upon detecting an unsolvable pair ensures that such scenarios are discarded promptly, leading to a final return value of -1.

The algorithm also gracefully handles cases where one or both arrays contain duplicate values. Since the comparison operators are non-strict (<=), equal values to the thresholds are considered valid, and the logic does not depend on uniqueness.

Performance Optimizations

The implementation achieves efficiency by limiting the number of passes over the data to exactly two. Each pass processes the shortened arrays in a single linear scan, avoiding any nested loops or repeated traversals. The use of zip provides a concise and memory-efficient way to iterate over paired elements without constructing intermediate structures.

Swapping the thresholds only once per outer iteration eliminates the need for separate copies of the arrays for each scenario. By reusing the same nums1 and nums2 lists after the initial pop, the algorithm reduces allocation overhead.

The early termination (break) when a pair cannot be salvaged by a swap prevents unnecessary work on the remaining elements of the current scenario. This short-circuiting can dramatically reduce runtime on inputs where the constraints are violated early in the sequence.

The initialization of result with positive infinity (+inf) allows a single min operation to keep track of the best feasible swap count without additional conditional checks, streamlining the update logic.

Overall, the design balances clarity with a tight control flow that minimizes both time spent on successful paths and wasted effort on impossible configurations.

Imagine two rows of toy bricks sitting on the floor. Each row has a special anchor brick at the very end. The goal is to make sure every single brick in the first row is small enough to fit under its anchor, and every brick in the second row is also small enough to fit under its own special anchor.

To fix the rows, you inspect each pair of bricks, one from the first row and one from the second row. If a brick is too big for its spot, you trade it with the matching brick from the other row. Every time a trade happens, you count it as one step. You try this in two different ways: by keeping the anchor bricks where they are, or by swapping the two anchors with each other first. After checking both ways, you look at how many trades were made and try to make the total number of trades as small as possible. If the bricks still do not fit after trying both ways, it means it is impossible to solve, and you can just say it cannot be done.

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

Time: linear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

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		Java	C++		Python	TS
	WalkCCC		Java	C++		Python
	leetcode.ca		Java	C++	Go	Python	TS
	Progiez		Java	C++		Python
github	charles-wangkai		Java
	everthis	JS
	fsq			C++
	JoshCrozier	JS
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
Progiez	C++, Java, Python
charles-wangkai	Java
everthis	JavaScript
fsq	C++
JoshCrozier	JavaScript

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