# 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:

```python
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:

```python
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

| Item | Meaning |
|---|---|
| Input | Two arrays `nums1` and `nums2` of equal length |
| Output | Minimum number of swaps |
| Operation | Swap `nums1[i]` with `nums2[i]` at the same index |
| Goal | Make both arrays strictly increasing |

## Examples

Example:

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

If we swap at index `3`, the arrays become:

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

Both arrays are now strictly increasing.

So the answer is:

```python
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:

```python
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:

| State | Meaning |
|---|---|
| `keep` | Minimum swaps up to index `i` if we do not swap at `i` |
| `swap` | Minimum swaps up to index `i` if we swap at `i` |

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:

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

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

```python
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:

```python
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:

```python
next_keep = infinity
next_swap = infinity
```

If the arrays are increasing without crossing:

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

then we can keep the same decision pattern:

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

If the arrays are increasing with crossing:

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

then we can switch between previous keep and previous swap:

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

After processing index `i`, assign:

```python
keep = next_keep
swap = next_swap
```

The answer is:

```python
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

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | We scan the arrays once |
| Space | `O(1)` | We only keep two DP states |

## Implementation

```python
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:

```python
keep = 0
swap = 1
```

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

For every later index, we compute fresh states:

```python
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:

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

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

```python
next_keep = min(next_keep, keep)
```

Swapping current index after swapping previous index is also valid:

```python
next_swap = min(next_swap, swap + 1)
```

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

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

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

```python
next_keep = min(next_keep, swap)
```

Swapping current index after keeping previous index is valid:

```python
next_swap = min(next_swap, keep + 1)
```

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

```python
keep = next_keep
swap = next_swap
```

Finally:

```python
return min(keep, swap)
```

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

## Testing

```python
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()
```

| Test | Why |
|---|---|
| `[1,3,5,4]`, `[1,2,3,7]` | Requires one swap at the end |
| `[0,3,5,8,9]`, `[2,1,4,6,9]` | Requires one earlier swap |
| Single element | Already valid |
| Already increasing | Requires zero swaps |
| Cross transition case | Checks switching between keep and swap states |