14.23 Minimum Swaps to Make Sequences Increasing

14.23.1 Problem Metadata

14.23.2 Description

Given two equal-length arrays A and B that are strictly increasing individually, you may swap elements at the same index. Return the minimum swaps needed to make both arrays strictly increasing.

14.23.3 Examples

Input: A = [1,3,5,4], B = [1,2,3,7]
Output: 1

14.23.4 Constraints

  • 1 <= n <= 10^5
  • 0 <= A[i], B[i] <= 2 * 10^5

14.23.5 Solution - DP with Keep/Swap States

14.23.5.1 Walkthrough

Let keep[i] be the minimum swaps to keep index i un-swapped, and swap[i] when we swap at i. Initialize keep[0] = 0, swap[0] = 1. For each i > 0, consider whether the sequences remain increasing without swap, with swap, or both, and update the states accordingly.

14.23.5.2 Analysis

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

14.23.5.3 Implementation Steps

  1. Initialize keep = 0, swap = 1.
  2. For each index i from 1 to n-1:
    • Set nextKeep = nextSwap = Integer.MAX_VALUE.
    • If A[i] > A[i-1] && B[i] > B[i-1], update nextKeep = min(nextKeep, keep) and nextSwap = min(nextSwap, swap + 1).
    • If A[i] > B[i-1] && B[i] > A[i-1], update nextKeep = min(nextKeep, swap) and nextSwap = min(nextSwap, keep + 1).
    • Assign keep = nextKeep, swap = nextSwap.
  3. Return min(keep, swap).

14.23.5.4 Code - Java

public int minSwap(int[] A, int[] B) {
    int keep = 0;
    int swap = 1;

    for (int i = 1; i < A.length; i++) {
        int nextKeep = Integer.MAX_VALUE;
        int nextSwap = Integer.MAX_VALUE;

        boolean noSwapNeeded = A[i] > A[i - 1] && B[i] > B[i - 1];
        boolean crossSwap = A[i] > B[i - 1] && B[i] > A[i - 1];

        if (noSwapNeeded) {
            nextKeep = Math.min(nextKeep, keep);
            nextSwap = Math.min(nextSwap, swap + 1);
        }
        if (crossSwap) {
            nextKeep = Math.min(nextKeep, swap);
            nextSwap = Math.min(nextSwap, keep + 1);
        }

        keep = nextKeep;
        swap = nextSwap;
    }

    return Math.min(keep, swap);
}