The O(n) Club: Minimum Swaps To Make Sequences Increasing (or, Why Parallel Universes Matter)

The O(n) Club: Minimum Swaps To Make Sequences Increasing (or, Why Parallel Universes Matter)

⚡ TL;DR

You get two number arrays. You want both to become strictly increasing, but you’re only allowed to swap elements at the same index. The catch? Minimize your swaps—unless you like making your code (and interviewer) cry. The brute force path is basically launching a recursive bomb (hello, O(2^n)). Dynamic programming, on the other hand, feels like discovering coffee for the first time:

// Brute force baseline (not recommended):
// totalSwaps = tryAllSwaps(A, B, 0, -1, false);
 // Dynamic programming plan:
int keep = 0, swap = 1;
for (int i = 1; i < A.length; ++i) {
    // See the universe split below
}
return Math.min(keep, swap);

🧠 How Devs Usually Mess This Up

Most folks immediately embrace the chaos: try every possible permutation of swaps at every position. Suddenly, your recursion tree is taller than your coffee stack, and your time complexity is O(bye-bye). Even worse? People treat swaps like they’re always optional. In this problem, the arrays sometimes strong-arm you into swapping or not swapping, and if you ignore that, your output will be as scrambled as your brain at 2 AM.

🔍 What’s Actually Going On

Here’s the plot twist: You’re always living in two states—one where you swapped at the current position, one where you heroically (or lazily) avoided it. At each index, you check two things:

• No-Swap Mode: If A[i] > A[i-1] and B[i] > B[i-1], life is good! Keep the streak, no swap required.
• Swap Mode: But if things are misaligned, ask: Would swapping here, given the previous state, magically fix both? Specifically, if A[i] > B[i-1] and B[i] > A[i-1], you can safely flip your swap state (swapped last time? no swap now; no swap last time? swap now).

Tracking only two numbers—keep and swap—gives you all the power of a martial artist in an ’80s movie montage. Less memory juggling, more clean wins.

🛠️ PseudoCode

• Start with

  keep = 0; swap = 1;

  // At index 0: do nothing (glorious), or swap once for science.
• For every position i from 1 to n-1:
  • If both arrays can keep increasing with or without a swap:

    if (A[i] > A[i-1] && B[i] > B[i-1]) {
      nextKeep = Math.min(nextKeep, keep);
      nextSwap = Math.min(nextSwap, swap + 1);
    }

  • If crossways works (by swapping this index):

    if (A[i] > B[i-1] && B[i] > A[i-1]) {
      nextKeep = Math.min(nextKeep, swap);
      nextSwap = Math.min(nextSwap, keep + 1);
    }

  • Prepare for next iteration:

    keep = nextKeep;
    swap = nextSwap;

• Return

  Math.min(keep, swap);

  for the final glory.

💻 The Code

public int minSwap(int[] A, int[] B) {
    int n = A.length;
    int keep = 0, swap = 1;
    for (int i = 1; i < n; i++) {
        int nextKeep = Integer.MAX_VALUE;
        int nextSwap = Integer.MAX_VALUE;
        if (A[i] > A[i-1] && B[i] > B[i-1]) {
            nextKeep = Math.min(nextKeep, keep);
            nextSwap = Math.min(nextSwap, swap + 1);
        }
        if (A[i] > B[i-1] && B[i] > A[i-1]) {
            nextKeep = Math.min(nextKeep, swap);
            nextSwap = Math.min(nextSwap, keep + 1);
        }
        keep = nextKeep;
        swap = nextSwap;
    }
    return Math.min(keep, swap);
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Miss one condition? Your solution will happily pass simple cases—and catastrophically fail when forced swaps sneak in.
• Don’t forget: start with keep = 0 and swap = 1. Start them backwards, and you’ll play yourself.
• If your first instinct is to reach for an array, pause—O(1) space works better and impresses grumpy interviewers.
• Edge case alert: identical starting values. Don’t make assumptions about A[0] == B[0].
• This isn’t your memoization hero moment. Just two variables, no past-life regression needed.
• Runtime is O(n), space is O(1). Reality never felt so sweet.

🧠 Interviewer Brain-Tattoo

“Every coder lives in two states: swapped or unswapped. Don’t let the arrays force-swap your confidence.”