Watch 10 video solutions for Minimum Swaps To Make Sequences Increasing, a hard level problem involving Array, Dynamic Programming. This walkthrough by code_report has 26,944 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given two integer arrays of the same length nums1 and nums2. In one operation, you are allowed to swap nums1[i] with nums2[i].
nums1 = [1,2,3,8], and nums2 = [5,6,7,4], you can swap the element at i = 3 to obtain nums1 = [1,2,3,4] and nums2 = [5,6,7,8].Return the minimum number of needed operations to make nums1 and nums2 strictly increasing. The test cases are generated so that the given input always makes it possible.
An array arr is strictly increasing if and only if arr[0] < arr[1] < arr[2] < ... < arr[arr.length - 1].
Example 1:
Input: nums1 = [1,3,5,4], nums2 = [1,2,3,7] Output: 1 Explanation: Swap nums1[3] and nums2[3]. Then the sequences are: nums1 = [1, 3, 5, 7] and nums2 = [1, 2, 3, 4] which are both strictly increasing.
Example 2:
Input: nums1 = [0,3,5,8,9], nums2 = [2,1,4,6,9] Output: 1
Constraints:
2 <= nums1.length <= 105nums2.length == nums1.length0 <= nums1[i], nums2[i] <= 2 * 105Problem Overview: You are given two equal-length integer arrays. At any index you may swap the elements between the arrays. The goal is to perform the minimum number of swaps so both arrays become strictly increasing.
Approach 1: Brute Force Recursion (Exponential Time, O(2^n) time, O(n) space)
At every index you have two choices: keep the pair as is or swap the elements between the arrays. Recursively explore both options while checking whether the sequences remain strictly increasing relative to the previous index. If the current values violate the increasing condition, prune that branch. The recursion tracks the last chosen values and counts swaps. This approach demonstrates the core decision structure but quickly becomes impractical because it explores up to 2^n states.
Approach 2: Dynamic Programming with State Arrays (O(n) time, O(n) space)
The key observation: at each index you only care about two states — whether you swapped at this index or not. Maintain two arrays: keep[i] (minimum swaps if index i is not swapped) and swap[i] (minimum swaps if index i is swapped). Transition based on whether the current elements maintain the strictly increasing order relative to the previous index. If A[i] > A[i-1] and B[i] > B[i-1], the previous state can carry forward. If A[i] > B[i-1] and B[i] > A[i-1], a cross transition (swap vs keep) is also valid. This dynamic programming formulation reduces the exponential search to a linear scan.
Approach 3: Space Optimized Dynamic Programming (O(n) time, O(1) space)
You only need results from the previous index, so the keep and swap arrays can be compressed into two variables. Iterate from left to right and update the next state using temporary variables. For each position, evaluate the two ordering conditions and update the minimum swaps accordingly. This keeps the logic identical to the DP formulation but reduces memory usage to constant space. The algorithm performs a single pass through the arrays, making it the optimal solution.
Recommended for interviews: The space‑optimized dynamic programming approach. It shows you recognized the two-state dependency and reduced the DP table to constant memory. Interviewers often expect candidates to first reason about the decision (swap vs keep), derive the DP transition, and then optimize space. The problem strongly tests reasoning with ordered sequences in arrays and state transitions in dynamic programming.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Recursion | O(2^n) | O(n) | Conceptual understanding of swap vs keep decisions |
| Dynamic Programming (DP Arrays) | O(n) | O(n) | Clear DP formulation when teaching or debugging transitions |
| Space Optimized Dynamic Programming | O(n) | O(1) | Production or interview solution with minimal memory usage |