Minimum Swaps To Make Sequences Increasing

You are given two integer arrays nums1 and nums2 of the same length. In one operation, you can swap nums1[i] and nums2[i] at some index i. Your goal is to make both arrays strictly increasing using the minimum number of swaps. The problem guarantees that a valid answer always exists.

This is LeetCode 801: Minimum Swaps To Make Sequences Increasing. It looks like a greedy problem at first glance, but greedy fails because swapping at one position affects the constraints at the next. The real solution is a two-state dynamic programming approach where you track the cost of swapping and not swapping at each index.

Why this problem matters

This problem teaches you state machine DP, one of the most powerful patterns in dynamic programming. Instead of a single DP value at each index, you maintain two states: the cost when you swap at position i and the cost when you keep position i unchanged. The transitions between these states depend on whether the current elements are already in the right order relative to their neighbors.

You will see this two-state tracking pattern again in:

• Best Time to Buy and Sell Stock with Cooldown (hold vs. not-hold states)
• House Robber (rob vs. skip states)
• Paint House (one state per color choice)

Once you internalize how to split a decision into parallel DP tracks and define transitions between them, these problems all follow the same template.

The approach

At each index i, you have two choices: keep the elements where they are, or swap nums1[i] and nums2[i]. Each choice has a cost, and that cost depends on what you did at index i - 1.

Define two variables:

• keep = minimum swaps to make indices 0 through i valid when you do NOT swap at index i
• swap = minimum swaps to make indices 0 through i valid when you DO swap at index i

At each step, you compute new_keep and new_swap based on two conditions:

Condition 1: Natural order works. If nums1[i] > nums1[i-1] and nums2[i] > nums2[i-1], then you can keep both i and i-1 unswapped, or swap both. So:

• new_keep = min(new_keep, keep) (neither swapped)
• new_swap = min(new_swap, swap + 1) (both swapped, so relative order preserved)

Condition 2: Cross order works. If nums1[i] > nums2[i-1] and nums2[i] > nums1[i-1], then you can swap at i but not i-1, or vice versa. So:

• new_keep = min(new_keep, swap) (swapped at i-1 but not i)
• new_swap = min(new_swap, keep + 1) (kept at i-1 but swapped at i)

The answer is min(keep, swap) after processing the last index.

Clean solution

def min_swap(nums1, nums2):
    n = len(nums1)
    keep = 0
    swap = 1

    for i in range(1, n):
        new_keep = float('inf')
        new_swap = float('inf')

        if nums1[i] > nums1[i - 1] and nums2[i] > nums2[i - 1]:
            new_keep = min(new_keep, keep)
            new_swap = min(new_swap, swap + 1)

        if nums1[i] > nums2[i - 1] and nums2[i] > nums1[i - 1]:
            new_keep = min(new_keep, swap)
            new_swap = min(new_swap, keep + 1)

        keep = new_keep
        swap = new_swap

    return min(keep, swap)

This is already space-optimized. You only store two values from the previous iteration, so there is no array to optimize away. Let's walk through the example to see how the states evolve.

DP walkthrough

Using nums1 = [1, 3, 5, 4] and nums2 = [1, 2, 3, 7]:

Notice how at index 3, the natural order check fails because nums1[3] = 4 is not greater than nums1[2] = 5. But the cross order check passes: 4 > 3 (nums2[2]) and 7 > 5 (nums1[2]). This means we need to either swap at index 3 and keep at index 2, or keep at index 3 and swap at index 2. The DP handles this by pulling from the opposite state.

Space-optimized version

The solution above is already O(1) space. We only keep keep and swap from the previous iteration, and compute new_keep and new_swap for the current one. No arrays needed.

If you want to see what the full DP array version looks like before optimization:

def min_swap(nums1, nums2):
    n = len(nums1)
    keep_dp = [float('inf')] * n
    swap_dp = [float('inf')] * n
    keep_dp[0] = 0
    swap_dp[0] = 1

    for i in range(1, n):
        if nums1[i] > nums1[i - 1] and nums2[i] > nums2[i - 1]:
            keep_dp[i] = min(keep_dp[i], keep_dp[i - 1])
            swap_dp[i] = min(swap_dp[i], swap_dp[i - 1] + 1)

        if nums1[i] > nums2[i - 1] and nums2[i] > nums1[i - 1]:
            keep_dp[i] = min(keep_dp[i], swap_dp[i - 1])
            swap_dp[i] = min(swap_dp[i], keep_dp[i - 1] + 1)

    return min(keep_dp[-1], swap_dp[-1])

Since each keep_dp[i] and swap_dp[i] only depend on keep_dp[i-1] and swap_dp[i-1], you can replace the arrays with two variables. That gives you the clean version from above.

Complexity analysis

One pass through the arrays, constant work at each index. The space optimization follows the same principle as Climbing Stairs and House Robber: when your recurrence only looks back one step, you only need to store the previous values.

The building blocks

This problem is built on state machine DP with two parallel tracks. You iterate through a sequence, and at each position you maintain multiple states that represent different decisions you could have made. The transitions between states encode the constraints of the problem.

The structure:

• States: keep and swap, representing the two possible decisions at each index
• Transitions: at each index, check which orderings are valid and update each state from the appropriate previous state
• Space optimization: since you only look back one step, replace arrays with variables

What makes this problem tricky is that the transitions are conditional. Unlike House Robber, where the recurrence is always max(dp[i-1], dp[i-2] + nums[i]), here the valid transitions depend on the relationship between adjacent elements. Sometimes only one condition holds. Sometimes both do. The DP handles all cases gracefully.

Edge cases

• Already sorted arrays: both nums1 and nums2 are already strictly increasing. The answer is 0 because keep stays 0 throughout and never needs updating through the swap path.
• Every position needs a swap: if the only valid configuration requires swapping at every index, swap will track the accumulating cost while keep stays at infinity.
• Alternating swap and keep: some inputs require swapping at even indices and keeping at odd indices (or vice versa). The two-state DP naturally handles this because each state can transition from either state at the previous index.
• Arrays of length 1: no comparisons needed, and no swaps needed. The answer is 0.

From understanding to recall

You have just worked through the two-state DP approach for minimum swaps. The idea of maintaining keep and swap states with conditional transitions probably makes sense right now. But try to write this solution from scratch tomorrow without looking at the code. Can you remember which conditions trigger which transitions?

That gap between understanding and recall is exactly what spaced repetition solves. You revisit the two-state transition logic at increasing intervals, write it from scratch each time, and after a few reps the conditional updates become automatic. No more second-guessing whether new_keep pulls from keep or swap in the cross-order case.

State machine DP is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Drilling them individually with spaced repetition beats random problem grinding every time.

Related posts

• House Robber - Two-variable DP with a decision at each step, the simpler version of the same pattern
• Best Time to Buy and Sell Stock with Cooldown - State machine DP with hold, sold, and rest states
• Climbing Stairs - The foundation for constant-state linear DP and space optimization