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^5nums2.length == nums1.length0 <= nums1[i], nums2[i] <= 2 * 10^5A valid sequence of swaps always exists
Hints for Minimum Swaps To Make Sequences Increasing
Hint 1
Whether index
ican be swapped depends only on whether indexi - 1was swapped.Hint 2
Track two numbers per index: the fewest swaps with index
ikept as is (keep) and with indexiswapped (swap).Hint 3
If both arrays already increase at
iwith 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
keep = 0,swap = 1for index 0.- For
i >= 1, startnk = ns = ∞. - If
nums1[i-1] < nums1[i]andnums2[i-1] < nums2[i]: same orientation works —nk = min(nk, keep),ns = min(ns, swap + 1). - If
nums1[i-1] < nums2[i]andnums2[i-1] < nums1[i]: crossed orientation works —nk = min(nk, swap),ns = min(ns, keep + 1). - Set
keep = nk,swap = ns; returnmin(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