# Minimum Swaps To Make Sequences Increasing
**Difficulty:** HARD
[External](https://leetcode.com/problems/minimum-swaps-to-make-sequences-increasing)
Canonical: https://scaleengineer.com/dsa/problems/minimum-swaps-to-make-sequences-increasing
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Array
---
## Problem
You are given two integer arrays of the same length `nums1` and `nums2`. In one operation, you are allowed to swap `nums1[i]` with `nums2[i]`.

* For example, if `nums1 = [1,2,3,8]`, and `nums2 = [5,6,7,4]`, you can swap the element at `i = 3` to obtain `nums1 = [1,2,3,4]` and `nums2 = [5,6,7,8]`.

Return _the minimum number of needed operations to make_ `nums1` _and_ `nums2` _**strictly increasing**_. The test cases are generated so that the given input always makes it possible.

An array `arr` is **strictly increasing** if and only if `arr[0] < arr[1] < arr[2] < ... < arr[arr.length - 1]`.

**Example 1:**

**Input:** nums1 = [1,3,5,4], nums2 = [1,2,3,7]
**Output:** 1
**Explanation:** 
Swap nums1[3] and nums2[3]. Then the sequences are:
nums1 = [1, 3, 5, 7] and nums2 = [1, 2, 3, 4]
which are both strictly increasing.

**Example 2:**

**Input:** nums1 = [0,3,5,8,9], nums2 = [2,1,4,6,9]
**Output:** 1

**Constraints:**

* `2 <= nums1.length <= 105`
* `nums2.length == nums1.length`
* `0 <= nums1[i], nums2[i] <= 2 * 105`

# Approaches
## Dynamic Programming with Linear Space
A classic approach for this type of problem is dynamic programming. We can determine the minimum swaps for a prefix of the arrays by building upon the solution for the previous, smaller prefix. We define two states for each index `i`: the minimum swaps needed if we *don't* swap `nums1[i]` and `nums2[i]`, and the minimum swaps needed if we *do* swap them. By iterating through the arrays, we can compute these values for each index based on the values of the previous index.
**Time:** O(N), where N is the length of the arrays. We perform a single pass through the arrays to fill the DP tables. · **Space:** O(N), where N is the length of the arrays. We use two arrays, `keep` and `swap`, each of size N.
**Pros:** Provides a clear and structured way to solve the problem.; The logic is relatively straightforward to follow.
**Cons:** Uses O(N) extra space, which is not optimal for this problem.
### Explanation
We use two DP arrays, `keep` and `swap`, of size `n`. `keep[i]` stores the minimum swaps to make prefixes `nums1[0...i]` and `nums2[0...i]` strictly increasing, with the condition that we do **not** swap elements at index `i`. Similarly, `swap[i]` stores the minimum swaps if we **do** swap elements at index `i`.

The base cases are at index 0. `keep[0]` is 0 because not swapping the first pair of elements costs 0 swaps. `swap[0]` is 1 because swapping them costs 1 swap.

For any subsequent index `i > 0`, the values of `keep[i]` and `swap[i]` depend on the values at `i-1`. We check two main conditions:
1.  `nums1[i] > nums1[i-1] && nums2[i] > nums2[i-1]`: If this is true, the arrays remain increasing if we either kept both `i-1` and `i` as they are, or swapped both. This allows a transition from `keep[i-1]` to `keep[i]` and from `swap[i-1]` to `swap[i]`.
2.  `nums1[i] > nums2[i-1] && nums2[i] > nums1[i-1]`: If this is true, the arrays remain increasing if we swapped at one index (`i-1` or `i`) but not the other. This allows a transition from `swap[i-1]` to `keep[i]` and from `keep[i-1]` to `swap[i]`.

We combine these possibilities to find the minimum costs for `keep[i]` and `swap[i]`. The final answer is the minimum of `keep[n-1]` and `swap[n-1]`. This same logic can also be implemented using top-down recursion with memoization.

```java
class Solution {
    public int minSwap(int[] nums1, int[] nums2) {
        int n = nums1.length;
        int[] keep = new int[n];
        int[] swap = new int[n];

        // Base case
        keep[0] = 0;
        swap[0] = 1;

        for (int i = 1; i < n; i++) {
            keep[i] = Integer.MAX_VALUE;
            swap[i] = Integer.MAX_VALUE;

            boolean noSwapCondition = nums1[i] > nums1[i - 1] && nums2[i] > nums2[i - 1];
            boolean swapCondition = nums1[i] > nums2[i - 1] && nums2[i] > nums1[i - 1];

            if (noSwapCondition) {
                keep[i] = keep[i - 1];
                swap[i] = swap[i - 1] + 1;
            }

            if (swapCondition) {
                keep[i] = Math.min(keep[i], swap[i - 1]);
                swap[i] = Math.min(swap[i], keep[i - 1] + 1);
            }
        }

        return Math.min(keep[n - 1], swap[n - 1]);
    }
}
```
### Algorithm
- Create two integer arrays, `keep` and `swap`, of the same length `n` as the input arrays.
- `keep[i]` will store the minimum swaps for the prefix `0...i` to be strictly increasing, with **no swap** at index `i`.
- `swap[i]` will store the minimum swaps for the prefix `0...i` to be strictly increasing, with a **swap** at index `i`.
- **Base Case (i=0):**
  - `keep[0] = 0` (no swaps needed for the first element if we don't swap).
  - `swap[0] = 1` (one swap is needed for the first element if we swap).
- **Transitions (i > 0):**
  - Iterate from `i = 1` to `n-1`.
  - For each `i`, we consider two possibilities for the state at `i-1` (kept or swapped) to determine the cost for the state at `i`.
  - Let `noSwapCondition = (nums1[i] > nums1[i-1] && nums2[i] > nums2[i-1])`.
  - Let `swapCondition = (nums1[i] > nums2[i-1] && nums2[i] > nums1[i-1])`.
  - If `noSwapCondition` is true, it means we can maintain the increasing property without cross-swapping between `i-1` and `i`. 
    - `keep[i] = keep[i-1]`
    - `swap[i] = swap[i-1] + 1`
  - If `swapCondition` is true, it means we can maintain the increasing property by cross-swapping between `i-1` and `i`.
    - `keep[i] = min(keep[i], swap[i-1])`
    - `swap[i] = min(swap[i], keep[i-1] + 1)`
- **Final Result:**
  - The minimum total swaps is the minimum of the two possibilities at the last index: `min(keep[n-1], swap[n-1])`.

## Space-Optimized Dynamic Programming
The previous dynamic programming approach can be optimized in terms of space. Notice that the calculations for `keep[i]` and `swap[i]` only depend on the values from the immediately preceding index, `i-1`. This means we don't need to store the entire history of `keep` and `swap` values in arrays. We only need to keep track of the values from the previous step, which allows us to reduce the space complexity from O(N) to O(1).
**Time:** O(N), where N is the length of the arrays. We still need to iterate through the arrays once. · **Space:** O(1). We only use a constant number of variables to store the states of the previous and current steps, regardless of the input size.
**Pros:** Highly efficient, with optimal O(1) space complexity.; Maintains the same O(N) time complexity as the unoptimized version.
**Cons:** The logic might be slightly less direct to grasp initially compared to the version with full DP arrays.
### Explanation
Instead of using two arrays, we use four variables to track the states. `prev_keep` and `prev_swap` hold the minimum swap counts for the prefix ending at `i-1` (without and with a swap at `i-1`, respectively). `curr_keep` and `curr_swap` are used to calculate these values for the current index `i`.

We start by initializing `prev_keep = 0` and `prev_swap = 1`, which represent the base case at index 0. Then, we iterate from `i = 1` to `n-1`. In each iteration, we calculate `curr_keep` and `curr_swap` using the exact same transition logic as the O(N) space approach, but reading from `prev_keep` and `prev_swap` instead of `keep[i-1]` and `swap[i-1]`. After the calculation for index `i` is complete, we update `prev_keep` and `prev_swap` with the `curr_keep` and `curr_swap` values to prepare for the next iteration. This rolling update mechanism effectively discards old state information that is no longer needed, leading to constant space usage.

```java
class Solution {
    public int minSwap(int[] nums1, int[] nums2) {
        int n = nums1.length;

        // prev_keep: min swaps for prefix i-1, without swapping at i-1
        // prev_swap: min swaps for prefix i-1, with a swap at i-1
        int prev_keep = 0;
        int prev_swap = 1;

        for (int i = 1; i < n; i++) {
            int curr_keep = Integer.MAX_VALUE;
            int curr_swap = Integer.MAX_VALUE;

            boolean noSwapCondition = nums1[i] > nums1[i - 1] && nums2[i] > nums2[i - 1];
            boolean swapCondition = nums1[i] > nums2[i - 1] && nums2[i] > nums1[i - 1];

            if (noSwapCondition) {
                curr_keep = prev_keep;
                curr_swap = prev_swap + 1;
            }

            if (swapCondition) {
                curr_keep = Math.min(curr_keep, prev_swap);
                curr_swap = Math.min(curr_swap, prev_keep + 1);
            }
            
            prev_keep = curr_keep;
            prev_swap = curr_swap;
        }

        return Math.min(prev_keep, prev_swap);
    }
}
```
### Algorithm
- Initialize four variables:
  - `prev_keep`: Stores the minimum swaps for the prefix ending at `i-1` without a swap at `i-1`. Initialize to `0`.
  - `prev_swap`: Stores the minimum swaps for the prefix ending at `i-1` with a swap at `i-1`. Initialize to `1`.
  - `curr_keep`: A temporary variable to compute the `keep` value for the current index `i`.
  - `curr_swap`: A temporary variable to compute the `swap` value for the current index `i`.
- Iterate from `i = 1` to `n-1`:
  - Initialize `curr_keep` and `curr_swap` to a large value (e.g., `Integer.MAX_VALUE`).
  - Check the same two conditions as in the previous approach: `noSwapCondition` and `swapCondition`.
  - If `noSwapCondition` is true:
    - `curr_keep = prev_keep`
    - `curr_swap = prev_swap + 1`
  - If `swapCondition` is true:
    - `curr_keep = min(curr_keep, prev_swap)`
    - `curr_swap = min(curr_swap, prev_keep + 1)`
  - After computing the values for the current index `i`, update the `prev` variables for the next iteration:
    - `prev_keep = curr_keep`
    - `prev_swap = curr_swap`
- **Final Result:**
  - After the loop finishes, the answer is `min(prev_keep, prev_swap)`.

# Solutions
### Java

```java
class Solution {
public
  int minSwap(int[] nums1, int[] nums2) {
    int a = 0, b = 1;
    for (int i = 1; i < nums1.length; ++i) {
      int x = a, y = b;
      if (nums1[i - 1] >= nums1[i] || nums2[i - 1] >= nums2[i]) {
        a = y;
        b = x + 1;
      } else {
        b = y + 1;
        if (nums1[i - 1] < nums2[i] && nums2[i - 1] < nums1[i]) {
          a = Math.min(a, y);
          b = Math.min(b, x + 1);
        }
      }
    }
    return Math.min(a, b);
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minSwap(vector<int> &nums1, vector<int> &nums2) {
    int a = 0, b = 1, n = nums1.size();
    for (int i = 1; i < n; ++i) {
      int x = a, y = b;
      if (nums1[i - 1] >= nums1[i] || nums2[i - 1] >= nums2[i]) {
        a = y, b = x + 1;
      } else {
        b = y + 1;
        if (nums1[i - 1] < nums2[i] && nums2[i - 1] < nums1[i]) {
          a = min(a, y);
          b = min(b, x + 1);
        }
      }
    }
    return min(a, b);
  }
};

```

### Python

```python
class Solution:
    def minSwap(self, nums1: List[int], nums2: List[int]) -> int: a, b = 0, 1 for i in range(1, len(nums1)): x, y = a, b if nums1[i - 1] >= nums1[i] or nums2[i - 1] >= nums2[i]: a, b = y, x + 1 else: b = y + 1 if nums1[i - 1] < nums2[i] and nums2[i - 1] < nums1[i]: a, b = min(a, y), min(b, x + 1) return min(a, b)

```