LeetCode 801 - Minimum Swaps To Make Sequences Increasing

LeetCode Problem 801

Difficulty: 🔴 Hard
Topics: Array, Dynamic Programming

Solution

Problem Understanding

The problem gives us two arrays, nums1 and nums2, both of the same length. At every index i, we are allowed to either keep the values as they are, or swap nums1[i] with nums2[i].

Our goal is to make both arrays strictly increasing while performing the minimum number of swaps.

A strictly increasing array means:

• arr[i] < arr[i + 1] for every valid index
• Equal adjacent values are not allowed
• Decreasing values are not allowed

The important detail is that swaps are only allowed at the same index. We cannot rearrange elements arbitrarily. At each position, we make a binary decision:

• Do not swap
• Swap the pair at this index

The output is the minimum number of swaps required so that both resulting arrays become strictly increasing.

For example:

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

At index 3, the pair (4,7) breaks the increasing condition because 5 < 4 is false. Swapping them gives:

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

Now both arrays are strictly increasing, and we used exactly one swap.

The constraints are very important:

• n can be as large as 100000
• A brute-force exploration of all swap combinations would be impossible
• We need a solution close to linear time

The problem also guarantees that a valid answer always exists. That means we do not need to handle impossible states in the final output.

Several edge cases are important:

• Arrays that are already strictly increasing
• Arrays where swapping is required at multiple positions
• Cases where the optimal solution alternates between swapping and not swapping
• Cases where both swapped and non-swapped states remain valid at a position
• Equal values that can invalidate strict increasing conditions

Because each decision depends heavily on the previous index, this naturally suggests dynamic programming.

Approaches

Brute Force Approach

The most straightforward approach is to try every possible combination of swaps.

At every index, we have two choices:

1. Do not swap
2. Swap the elements at that index

Since there are n indices, this creates 2^n possible configurations.

For each configuration, we can construct the resulting arrays and verify whether both are strictly increasing. Among all valid configurations, we select the one with the minimum number of swaps.

This approach is correct because it explores every possible valid sequence of decisions. However, it is computationally infeasible.

If n = 100000, even 2^50 would already be astronomically large, so 2^100000 is completely impossible.

Optimal Dynamic Programming Approach

The key insight is that the decision at index i only depends on the state at index i - 1.

We do not need to remember the entire history of swaps. We only need to know:

• What was the minimum number of swaps up to the previous index if we did not swap there?
• What was the minimum number of swaps up to the previous index if we did swap there?

This gives us two DP states:

• keep[i] = minimum swaps needed up to index i if index i is not swapped
• swap[i] = minimum swaps needed up to index i if index i is swapped

Instead of storing full arrays, we can optimize space further because only the previous state matters.

At each position, we check two possible transitions:

1. Natural order remains increasing
2. Cross order remains increasing after swapping

This leads to an O(n) dynamic programming solution.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^n * n)	O(n)	Tries every swap combination
Optimal Dynamic Programming	O(n)	O(1)	Tracks only previous swap states

Algorithm Walkthrough

1. Initialize two variables:

• keep = 0
• swap = 1

keep means the minimum swaps needed if we do not swap index 0.

swap means the minimum swaps needed if we swap index 0, which costs one operation. 2. Iterate through the arrays from index 1 to n - 1. 3. For each index, initialize:

• next_keep = infinity
• next_swap = infinity

These represent the best results for the current index. 4. Check whether the arrays remain strictly increasing without changing swap parity.

This condition is:

nums1[i] > nums1[i - 1]
nums2[i] > nums2[i - 1]

If true:

• We can keep the current index unswapped if the previous index was also unswapped.
• We can swap the current index if the previous index was also swapped.

So:

next_keep = min(next_keep, keep)
next_swap = min(next_swap, swap + 1)

5. Check whether the arrays remain increasing if one of the two adjacent indices is swapped.

This condition is:

nums1[i] > nums2[i - 1]
nums2[i] > nums1[i - 1]

If true:

• We can swap current index while previous was kept
• We can keep current index while previous was swapped

So:

next_keep = min(next_keep, swap)
next_swap = min(next_swap, keep + 1)

6. Update:

keep = next_keep
swap = next_swap

7. After processing all indices, return:

min(keep, swap)

Why it works

The algorithm works because every valid configuration at index i depends only on whether index i - 1 was swapped or not. The strict increasing condition only compares adjacent elements, so earlier positions do not need to be reconsidered once their optimal states are known.

The DP states always maintain the minimum swaps needed for each possible previous-state configuration. Since every valid transition is examined exactly once, the algorithm guarantees the globally optimal answer.

Python Solution

from typing import List

class Solution:
    def minSwap(self, nums1: List[int], nums2: List[int]) -> int:
        n = len(nums1)

        keep = 0
        swap = 1

        for i in range(1, n):
            next_keep = float('inf')
            next_swap = float('inf')

            # Case 1:
            # No cross swap needed
            if nums1[i] > nums1[i - 1] and nums2[i] > nums2[i - 1]:
                next_keep = min(next_keep, keep)
                next_swap = min(next_swap, swap + 1)

            # Case 2:
            # Cross swap relationship works
            if nums1[i] > nums2[i - 1] and nums2[i] > nums1[i - 1]:
                next_keep = min(next_keep, swap)
                next_swap = min(next_swap, keep + 1)

            keep = next_keep
            swap = next_swap

        return min(keep, swap)

The implementation follows the dynamic programming strategy directly.

The variables keep and swap represent the minimum swaps needed up to the previous index under two different states.

Inside the loop, next_keep and next_swap compute the optimal values for the current index.

The first condition checks whether the arrays remain increasing if both indices use the same swap state. In that case:

• keep transitions to keep
• swap transitions to swap

The second condition checks whether switching swap parity between adjacent indices still preserves increasing order. In that case:

• swap transitions to keep
• keep transitions to swap

At the end of each iteration, the current results become the previous results for the next step.

Finally, the minimum of the two states gives the optimal answer.

Go Solution

package main

import "math"

func minSwap(nums1 []int, nums2 []int) int {
	n := len(nums1)

	keep := 0
	swap := 1

	for i := 1; i < n; i++ {
		nextKeep := math.MaxInt32
		nextSwap := math.MaxInt32

		// Case 1:
		// Same swap status as previous index
		if nums1[i] > nums1[i-1] && nums2[i] > nums2[i-1] {
			if keep < nextKeep {
				nextKeep