LeetCode 801: Minimum Swaps To Make Sequences Increasing

Problem Restatement

We are given two integer arrays nums1 and nums2 with the same length.

At any index i, we may swap:

nums1[i], nums2[i] = nums2[i], nums1[i]

The goal is to make both arrays strictly increasing using the minimum number of swaps.

Strictly increasing means:

nums1[0] < nums1[1] < nums1[2] < ...
nums2[0] < nums2[1] < nums2[2] < ...

The problem guarantees that at least one valid answer exists.

Input and Output

Examples

Example:

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

If we swap at index 3, the arrays become:

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

Both arrays are now strictly increasing.

So the answer is:

1

First Thought: Brute Force

At each index, we have two choices:

1. Do not swap.
2. Swap nums1[i] with nums2[i].

With n indices, this gives up to:

2^n

possible swap patterns.

For each pattern, we could check whether both arrays are strictly increasing.

This is too slow because the number of patterns doubles for every new index.

Key Insight

The decision at index i only depends on the state at index i - 1.

At each index, we only need two states:

This works because strict increasing order only compares neighboring elements.

At index i, there are two possible compatibility checks.

First, the current pair can follow the previous pair without crossing:

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

Second, the current pair can follow the previous pair with crossing:

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

These two checks describe all valid transitions between index i - 1 and index i.

Algorithm

Initialize:

keep = 0
swap = 1

At index 0, keeping costs 0 swaps. Swapping costs 1 swap.

Then scan from index 1 to the end.

For each index, create new values:

next_keep = infinity
next_swap = infinity

If the arrays are increasing without crossing:

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

then we can keep the same decision pattern:

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

If the arrays are increasing with crossing:

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

then we can switch between previous keep and previous swap:

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

After processing index i, assign:

keep = next_keep
swap = next_swap

The answer is:

min(keep, swap)

Correctness

At every index i, keep stores the minimum number of swaps needed to make both arrays strictly increasing from index 0 through index i, assuming index i is not swapped.

Similarly, swap stores the minimum number of swaps needed for the same prefix, assuming index i is swapped.

For each index, the algorithm checks every valid way that index i can follow index i - 1.

If the current values can follow the previous values directly, then a previous keep state can lead to a current keep state, and a previous swap state can lead to a current swap state.

If the current values can follow the previous values after crossing, then a previous swap state can lead to a current keep state, and a previous keep state can lead to a current swap state.

These are the only possibilities, because each index has only two choices: swapped or not swapped.

Since the algorithm keeps the minimum cost for both possible states at every index, it keeps the best valid prefix after each step. At the final index, the full arrays are strictly increasing, so the smaller of the final two states is the minimum number of swaps.

Complexity

Implementation

class Solution:
    def minSwap(self, nums1: list[int], nums2: list[int]) -> int:
        keep = 0
        swap = 1

        for i in range(1, len(nums1)):
            next_keep = float("inf")
            next_swap = float("inf")

            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)

            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)

Code Explanation

We start with:

keep = 0
swap = 1

At the first index, doing nothing costs 0. Swapping costs 1.

For every later index, we compute fresh states:

next_keep = float("inf")
next_swap = float("inf")

These represent the best cost for the current index. They start as impossible until a valid transition updates them.

The first condition checks whether the current pair can follow the previous pair in the same orientation:

if nums1[i] > nums1[i - 1] and nums2[i] > nums2[i - 1]:

If yes, keeping current index after keeping previous index is valid:

next_keep = min(next_keep, keep)

Swapping current index after swapping previous index is also valid:

next_swap = min(next_swap, swap + 1)

The second condition checks whether the current pair can follow the previous pair in the crossed orientation:

if nums1[i] > nums2[i - 1] and nums2[i] > nums1[i - 1]:

If yes, keeping current index after swapping previous index is valid:

next_keep = min(next_keep, swap)

Swapping current index after keeping previous index is valid:

next_swap = min(next_swap, keep + 1)

At the end of the loop, the current states become the previous states for the next index:

keep = next_keep
swap = next_swap

Finally:

return min(keep, swap)

We do not care whether the last index is swapped. We only care about the smaller valid cost.

Testing

def run_tests():
    s = Solution()

    assert s.minSwap([1, 3, 5, 4], [1, 2, 3, 7]) == 1
    assert s.minSwap([0, 3, 5, 8, 9], [2, 1, 4, 6, 9]) == 1
    assert s.minSwap([1], [2]) == 0
    assert s.minSwap([1, 5, 6], [1, 2, 7]) == 0
    assert s.minSwap([3, 3, 8, 9, 10], [1, 7, 4, 6, 8]) == 1

    print("all tests passed")

run_tests()