801. Minimum Swaps To Make Sequences Increasing

Problem Description

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 such that the given input always makes it possible.

Two arrays arr1 and arr2 are strictly increasing if and only if arr1[i] < arr1[i+1] and arr2[i] < arr2[i+1] for each i (0-based).

Examples:

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.

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

Constraints:

• 2 ≤ nums1.length ≤ 10^5
• nums2.length == nums1.length
• 0 ≤ nums1[i], nums2[i] ≤ 2 * 10^5

Python Solution

class Solution:
    def minSwap(self, nums1: List[int], nums2: List[int]) -> int:
        n = len(nums1)
        keep = [float('inf')] * n
        swap = [float('inf')] * n
        
        keep[0] = 0
        swap[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])

Implementation Notes:

• Uses dynamic programming with two arrays: keep and swap
• keep[i] represents minimum swaps needed if we don't swap at position i
• swap[i] represents minimum swaps needed if we swap at position i
• Time complexity: O(n)
• Space complexity: O(n)

Java Solution

class Solution {
    public int minSwap(int[] nums1, int[] nums2) {
        int n = nums1.length;
        int[] keep = new int[n];
        int[] swap = new int[n];
        Arrays.fill(keep, Integer.MAX_VALUE);
        Arrays.fill(swap, Integer.MAX_VALUE);
        
        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] = 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]);
    }
}

C++ Solution

class Solution {
public:
    int minSwap(vector& nums1, vector& nums2) {
        int n = nums1.size();
        vector keep(n, INT_MAX);
        vector 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]);
    }
};

JavaScript Solution

function minSwap(nums1, nums2) {
    const n = nums1.length;
    const keep = new Array(n).fill(Infinity);
    const swap = new 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]);
}

C# Solution

public class Solution {
    public int MinSwap(int[] nums1, int[] nums2) {
        int n = nums1.Length;
        int[] keep = new int[n];
        int[] swap = new int[n];
        Array.Fill(keep, int.MaxValue);
        Array.Fill(swap, int.MaxValue);
        
        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] = 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]);
    }
}

Implementation Notes:

• Uses dynamic programming approach
• Maintains two arrays to track minimum swaps needed
• Time complexity: O(n)
• Space complexity: O(n)