Minimum Swaps To Make Sequences Increasing

hard dp arrays case-analysis

Problem

Given two integer arrays nums1 and nums2 of the same length, in one operation you may swap nums1[i] with nums2[i]. Return the minimum number of swaps so that both nums1 and nums2 become strictly increasing.

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

Output1

Swap index 3 to make [1,3,5,7] and [1,2,3,4].

nums1, nums2

def minSwap(nums1, nums2):
    n = len(nums1)
    keep, swap = 0, 1
    for i in range(1, n):
        k, s = float('inf'), float('inf')
        if nums1[i] > nums1[i-1] and nums2[i] > nums2[i-1]:
            k = min(k, keep)
            s = min(s, swap + 1)
        if nums1[i] > nums2[i-1] and nums2[i] > nums1[i-1]:
            k = min(k, swap)
            s = min(s, keep + 1)
        keep, swap = k, s
    return min(keep, swap)

var minSwap = function(nums1, nums2) {
    const n = nums1.length;
    let keep = 0, swap = 1;
    for (let i = 1; i < n; i++) {
        let k = Infinity, s = Infinity;
        if (nums1[i] > nums1[i-1] && nums2[i] > nums2[i-1]) {
            k = Math.min(k, keep); s = Math.min(s, swap + 1);
        }
        if (nums1[i] > nums2[i-1] && nums2[i] > nums1[i-1]) {
            k = Math.min(k, swap); s = Math.min(s, keep + 1);
        }
        keep = k; swap = s;
    }
    return Math.min(keep, swap);
};

class Solution {
    public int minSwap(int[] nums1, int[] nums2) {
        int n = nums1.length, keep = 0, swap = 1;
        for (int i = 1; i < n; i++) {
            int k = Integer.MAX_VALUE, s = Integer.MAX_VALUE;
            if (nums1[i] > nums1[i-1] && nums2[i] > nums2[i-1]) {
                k = Math.min(k, keep); s = Math.min(s, swap + 1);
            }
            if (nums1[i] > nums2[i-1] && nums2[i] > nums1[i-1]) {
                k = Math.min(k, swap); s = Math.min(s, keep + 1);
            }
            keep = k; swap = s;
        }
        return Math.min(keep, swap);
    }
}

class Solution {
public:
    int minSwap(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size(), keep = 0, swap_ = 1;
        for (int i = 1; i < n; i++) {
            int k = INT_MAX, s = INT_MAX;
            if (nums1[i] > nums1[i-1] && nums2[i] > nums2[i-1]) {
                k = min(k, keep); s = min(s, swap_ + 1);
            }
            if (nums1[i] > nums2[i-1] && nums2[i] > nums1[i-1]) {
                k = min(k, swap_); s = min(s, keep + 1);
            }
            keep = k; swap_ = s;
        }
        return min(keep, swap_);
    }
};

Explanation

At every position you face one tiny choice: leave the column alone or swap nums1[i] with nums2[i]. The clever trick is to carry two running answers as you sweep left to right — the fewest swaps so far if the current column was kept, and the fewest if it was swapped.

We call these keep and swap. The base case is the first column: keeping it costs 0 swaps, swapping it costs 1.

For each new index i we look at the two orderings that could be valid. If the columns are already increasing without swapping (nums1[i] > nums1[i-1] and nums2[i] > nums2[i-1]), then the new keep can inherit the old keep, and the new swap comes from the old swap plus 1. If the crossed order works (nums1[i] > nums2[i-1] and nums2[i] > nums1[i-1]), then keeping now pairs with the old swap, and swapping now pairs with the old keep + 1.

Example: nums1 = [1,3,5,4], nums2 = [1,2,3,7]. Everything stays increasing until index 3, where the natural order breaks but the crossed order works, so the cheapest plan is a single swap there — answer 1.

At the end the result is min(keep, swap). Because we only ever keep two numbers and update them in one pass, this runs in linear time with constant extra memory.

Time: O(n) Space: O(1)