Minimum Swaps To Make Sequences Increasing

Hard
1498.

Minimum Swaps To Make Sequences Increasing

Minimum Swaps To Make Sequences Increasing is a hard coding problem on arrays and dynamic programming, asked in Amazon, Google and Meta interviews.

You are given two integer arrays nums1 and nums2 of the same length. In one operation you may swap nums1[i] with nums2[i] for some index i.

Return the minimum number of operations needed to make both arrays strictly increasing. The input is generated so that this is always possible.

Example 1

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

Example 2

Input
nums1 = [1,6,3,8], nums2 = [5,2,7,4]
Output
2
Explanation
Swap indices 1 and 3 (or 0 and 2); no single swap works.

Example 3

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
  • A valid sequence of swaps always exists
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var minSwap = function(nums1, nums2) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Minimum Swaps To Make Sequences Increasing — Solution

Minimum Swaps To Make Sequences Increasing solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.

Minimum Swaps To Make Sequences Increasing is a hard coding problem on arrays and dynamic programming, asked in Amazon, Google and Meta interviews.

  • Difficulty: Hard
  • Topics: Arrays, Dynamic Programming
  • Asked at: Amazon, Google, Meta
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You are given two integer arrays nums1 and nums2 of the same length. In one operation you may swap nums1[i] with nums2[i] for some index i.

Return the minimum number of operations needed to make both arrays strictly increasing. The input is generated so that this is always possible.

Example 1

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

Example 2

Input: nums1 = [1,6,3,8], nums2 = [5,2,7,4]
Output: 2
Explanation: Swap indices 1 and 3 (or 0 and 2); no single swap works.

Example 3

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
  • A valid sequence of swaps always exists

Hints for Minimum Swaps To Make Sequences Increasing

  1. Hint 1

    Whether index i can be swapped depends only on whether index i - 1 was swapped.

  2. Hint 2

    Track two numbers per index: the fewest swaps with index i kept as is (keep) and with index i swapped (swap).

  3. Hint 3

    If both arrays already increase at i with the same orientation, keep ← keep, swap ← swap + 1; if they increase crosswise, keep ← swap, swap ← keep + 1. Take minima when both hold.

How to solve Minimum Swaps To Make Sequences Increasing

Two-state DP over indices. Consider only adjacent pairs: the arrays are strictly increasing iff every adjacent pair is, and the pair (i-1, i) only cares whether each of the two indices was swapped.

Approach

  1. keep = 0, swap = 1 for index 0.
  2. For i >= 1, start nk = ns = ∞.
  3. If nums1[i-1] < nums1[i] and nums2[i-1] < nums2[i]: same orientation works — nk = min(nk, keep), ns = min(ns, swap + 1).
  4. If nums1[i-1] < nums2[i] and nums2[i-1] < nums1[i]: crossed orientation works — nk = min(nk, swap), ns = min(ns, keep + 1).
  5. Set keep = nk, swap = ns; return min(keep, swap) at the end.

Why it works

The conditions listed are exactly the ways the pair (i-1, i) can be strictly increasing in both arrays given the swap state of each index. Since only the previous index's state constrains index i, the best cost for each state of i is determined by the best costs for the two states of i - 1.

Complexity

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

Pitfalls

  • Both conditions can hold at once — consider both transitions, not else if.
  • Swapping index 0 costs 1 even though nothing precedes it.
  • The comparisons are strict: equal neighbours are not increasing.

Reference solution

Python

from typing import List

def minSwap(nums1: List[int], nums2: List[int]) -> int:
    INF = 10**9
    keep, swap = 0, 1
    for i in range(1, len(nums1)):
        nk = ns = INF
        if nums1[i - 1] < nums1[i] and nums2[i - 1] < nums2[i]:
            nk = min(nk, keep)
            ns = min(ns, swap + 1)
        if nums1[i - 1] < nums2[i] and nums2[i - 1] < nums1[i]:
            nk = min(nk, swap)
            ns = min(ns, keep + 1)
        keep, swap = nk, ns
    return min(keep, swap)

Java

public static int minSwap(int[] nums1, int[] nums2) {
    final int INF = 1000000000;
    int keep = 0, swap = 1;
    for (int i = 1; i < nums1.length; i++) {
        int nk = INF, ns = INF;
        if (nums1[i - 1] < nums1[i] && nums2[i - 1] < nums2[i]) {
            nk = Math.min(nk, keep);
            ns = Math.min(ns, swap + 1);
        }
        if (nums1[i - 1] < nums2[i] && nums2[i - 1] < nums1[i]) {
            nk = Math.min(nk, swap);
            ns = Math.min(ns, keep + 1);
        }
        keep = nk;
        swap = ns;
    }
    return Math.min(keep, swap);
}

C++

int minSwap(vector<int>& nums1, vector<int>& nums2) {
    const int INF = 1000000000;
    int keep = 0, swp = 1;
    for (size_t i = 1; i < nums1.size(); i++) {
        int nk = INF, ns = INF;
        if (nums1[i - 1] < nums1[i] && nums2[i - 1] < nums2[i]) {
            nk = min(nk, keep);
            ns = min(ns, swp + 1);
        }
        if (nums1[i - 1] < nums2[i] && nums2[i - 1] < nums1[i]) {
            nk = min(nk, swp);
            ns = min(ns, keep + 1);
        }
        keep = nk;
        swp = ns;
    }
    return min(keep, swp);
}

JavaScript

var minSwap = function(nums1, nums2) {
    var INF = 1000000000;
    var keep = 0, swap = 1;
    for (var i = 1; i < nums1.length; i++) {
        var nk = INF, ns = INF;
        if (nums1[i - 1] < nums1[i] && nums2[i - 1] < nums2[i]) {
            nk = Math.min(nk, keep);
            ns = Math.min(ns, swap + 1);
        }
        if (nums1[i - 1] < nums2[i] && nums2[i - 1] < nums1[i]) {
            nk = Math.min(nk, swap);
            ns = Math.min(ns, keep + 1);
        }
        keep = nk;
        swap = ns;
    }
    return Math.min(keep, swap);
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Dynamic Programming