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.
In this approach, we use dynamic programming (DP) to solve the problem efficiently. We maintain two arrays, keep and swap, where keep[i] denotes the minimum number of swaps needed to make the sequences increasing up to index i without swapping at i, and swap[i] denotes the minimum swaps with a swap at position i.
Initialize keep[0] = 0 and swap[0] = 1 as the first position doesn't require any operation unless swapped. Then for each index i, we calculate keep[i] and swap[i] based on previous values while ensuring the increasing order condition is maintained.
The above C code uses two arrays to track the minimum swaps required at each index with and without swapping. By initializing keep[0] as 0 and swap[0] as 1, it allows the first position either unswapped or swapped. The logic then calculates for each subsequent index the minimum swaps based on previous indices, ensuring the strictly increasing sequence.
Time Complexity: O(n), where n is the length of the array.
Space Complexity: O(n), due to the use of two arrays for tracking the minimum swaps.
| 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 |
Leetcode Contest 76 Problem 2 - Minimum Swaps To Make Sequences Increasing • code_report • 26,944 views views
Watch 9 more video solutions →Practice Minimum Swaps To Make Sequences Increasing with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor