Minimum Number of Swaps to Make Sequences Increasing

Problem Statement

Given two integer arrays nums1 and nums2 of equal length, you may swap nums1[i] with nums2[i] at any index. Return the minimum number of swaps to make both arrays strictly increasing (a valid answer is guaranteed to exist).

Example

Input:  nums1 = [1,3,5,4], nums2 = [1,2,3,7]
Output: 1
Explanation: Swap index 3 -> nums1 = [1,3,5,7], nums2 = [1,2,3,4].

Approach (Linear DP Scan)

Honest note: a greedy two pointer sweep does not solve this — the correct method is a linear dynamic-programming pass that scans both arrays together (one index pointer) while carrying two running costs: keep (no swap at i) and swap (swap at i). At each step we decide based on how position i relates to i-1.

• If both arrays are already increasing at i: we may keep both or swap both.
• If they are increasing only when crossed: we must swap exactly one of i-1 / i.

Complexity

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

Solution Code

Python

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

Java

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

C++

int minSwap(vector<int>& nums1, vector<int>& nums2) {
    int keep = 0, swap = 1;
    for (int i = 1; i < (int)nums1.size(); i++) {
        int newKeep = INT_MAX, newSwap = INT_MAX;
        if (nums1[i] > nums1[i-1] && nums2[i] > nums2[i-1]) {
            newKeep = min(newKeep, keep);
            newSwap = min(newSwap, swap + 1);
        }
        if (nums1[i] > nums2[i-1] && nums2[i] > nums1[i-1]) {
            newKeep = min(newKeep, swap);
            newSwap = min(newSwap, keep + 1);
        }
        keep = newKeep; swap = newSwap;
    }
    return min(keep, swap);
}

Key Takeaways

• This is DP, not a greedy two pointer — shown here for honest comparison.
• Two rolling states (keep/swap) keep the space at O(1).
• It still runs as a single left-to-right scan, like many pointer problems.