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].

Examples

Example 1

1
2
3
4
5
6

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

1
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

Solution

Method 1 – Dynamic Programming (State Tracking) 1

Intuition

We track two states at each index: the minimum swaps needed if we swap at this index, and if we do not swap. By comparing the previous values and checking the strictly increasing condition, we can update these states efficiently.

Approach

  1. Initialize two arrays or variables: keep (no swap at i) and swap (swap at i).
  2. At each index, check if both sequences are strictly increasing without swap and with swap.
  3. Update keep[i] and swap[i] based on previous values and whether swapping is needed.
  4. The answer is the minimum of the last keep and swap values.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    int minSwap(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size();
        vector<int> keep(n, INT_MAX), swap(n, INT_MAX);
        keep[0] = 0; swap[0] = 1;
        for (int i = 1; i < n; ++i) {
            if (nums1[i] > nums1[i-1] && nums2[i] > nums2[i-1]) {
                keep[i] = keep[i-1];
                swap[i] = swap[i-1] + 1;
            }
            if (nums1[i] > nums2[i-1] && nums2[i] > nums1[i-1]) {
                keep[i] = min(keep[i], swap[i-1]);
                swap[i] = min(swap[i], keep[i-1] + 1);
            }
        }
        return min(keep[n-1], swap[n-1]);
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

func minSwap(nums1, nums2 []int) int {
    n := len(nums1)
    keep := make([]int, n)
    swap := make([]int, n)
    keep[0], swap[0] = 0, 1
    for i := 1; i < n; i++ {
        keep[i], swap[i] = 1<<30, 1<<30
        if nums1[i] > nums1[i-1] && nums2[i] > nums2[i-1] {
            keep[i] = keep[i-1]
            swap[i] = swap[i-1] + 1
        }
        if nums1[i] > nums2[i-1] && nums2[i] > nums1[i-1] {
            keep[i] = min(keep[i], swap[i-1])
            swap[i] = min(swap[i], keep[i-1]+1)
        }
    }
    return min(keep[n-1], swap[n-1])
}
func min(a, b int) int { if a < b { return a }; return b }
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    public int minSwap(int[] nums1, int[] nums2) {
        int n = nums1.length;
        int[] keep = new int[n], swap = new int[n];
        keep[0] = 0; swap[0] = 1;
        for (int i = 1; i < n; ++i) {
            keep[i] = swap[i] = Integer.MAX_VALUE;
            if (nums1[i] > nums1[i-1] && nums2[i] > nums2[i-1]) {
                keep[i] = keep[i-1];
                swap[i] = swap[i-1] + 1;
            }
            if (nums1[i] > nums2[i-1] && nums2[i] > nums1[i-1]) {
                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]);
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    fun minSwap(nums1: IntArray, nums2: IntArray): Int {
        val n = nums1.size
        val keep = IntArray(n) { Int.MAX_VALUE }
        val swap = IntArray(n) { Int.MAX_VALUE }
        keep[0] = 0; swap[0] = 1
        for (i in 1 until n) {
            if (nums1[i] > nums1[i-1] && nums2[i] > nums2[i-1]) {
                keep[i] = keep[i-1]
                swap[i] = swap[i-1] + 1
            }
            if (nums1[i] > nums2[i-1] && nums2[i] > nums1[i-1]) {
                keep[i] = minOf(keep[i], swap[i-1])
                swap[i] = minOf(swap[i], keep[i-1] + 1)
            }
        }
        return minOf(keep[n-1], swap[n-1])
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

def minSwap(nums1: list[int], nums2: list[int]) -> int:
    n = len(nums1)
    keep = [float('inf')] * n
    swap = [float('inf')] * n
    keep[0], swap[0] = 0, 1
    for i in range(1, n):
        if nums1[i] > nums1[i-1] and nums2[i] > nums2[i-1]:
            keep[i] = keep[i-1]
            swap[i] = swap[i-1] + 1
        if nums1[i] > nums2[i-1] and nums2[i] > nums1[i-1]:
            keep[i] = min(keep[i], swap[i-1])
            swap[i] = min(swap[i], keep[i-1] + 1)
    return min(keep[-1], swap[-1])
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

impl Solution {
    pub fn min_swap(nums1: Vec<i32>, nums2: Vec<i32>) -> i32 {
        let n = nums1.len();
        let mut keep = vec![i32::MAX; n];
        let mut swap = vec![i32::MAX; n];
        keep[0] = 0; swap[0] = 1;
        for i in 1..n {
            if nums1[i] > nums1[i-1] && nums2[i] > nums2[i-1] {
                keep[i] = keep[i-1];
                swap[i] = swap[i-1] + 1;
            }
            if nums1[i] > nums2[i-1] && nums2[i] > nums1[i-1] {
                keep[i] = keep[i].min(swap[i-1]);
                swap[i] = swap[i].min(keep[i-1] + 1);
            }
        }
        keep[n-1].min(swap[n-1])
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    minSwap(nums1: number[], nums2: number[]): number {
        const n = nums1.length;
        const keep = Array(n).fill(Infinity);
        const swap = Array(n).fill(Infinity);
        keep[0] = 0; swap[0] = 1;
        for (let i = 1; i < n; ++i) {
            if (nums1[i] > nums1[i-1] && nums2[i] > nums2[i-1]) {
                keep[i] = keep[i-1];
                swap[i] = swap[i-1] + 1;
            }
            if (nums1[i] > nums2[i-1] && nums2[i] > nums1[i-1]) {
                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]);
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n is the length of the arrays. Each index is processed in constant time.
  • 🧺 Space complexity: O(n), for the keep and swap arrays.