Minimum Swaps To Make Sequences Increasing
HardPrompt
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].
- For example, if
nums1 = [1,2,3,8], andnums2 = [5,6,7,4], you can swap the element ati = 3to obtainnums1 = [1,2,3,4]andnums2 = [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 * 105
Approaches
2 approaches with complexity analysis and trade-offs.
A classic approach for this type of problem is dynamic programming. We can determine the minimum swaps for a prefix of the arrays by building upon the solution for the previous, smaller prefix. We define two states for each index i: the minimum swaps needed if we don't swap nums1[i] and nums2[i], and the minimum swaps needed if we do swap them. By iterating through the arrays, we can compute these values for each index based on the values of the previous index.
Algorithm
- Create two integer arrays,
keepandswap, of the same lengthnas the input arrays. keep[i]will store the minimum swaps for the prefix0...ito be strictly increasing, with no swap at indexi.swap[i]will store the minimum swaps for the prefix0...ito be strictly increasing, with a swap at indexi.- Base Case (i=0):
keep[0] = 0(no swaps needed for the first element if we don't swap).swap[0] = 1(one swap is needed for the first element if we swap).
- Transitions (i > 0):
- Iterate from
i = 1ton-1. - For each
i, we consider two possibilities for the state ati-1(kept or swapped) to determine the cost for the state ati. - Let
noSwapCondition = (nums1[i] > nums1[i-1] && nums2[i] > nums2[i-1]). - Let
swapCondition = (nums1[i] > nums2[i-1] && nums2[i] > nums1[i-1]). - If
noSwapConditionis true, it means we can maintain the increasing property without cross-swapping betweeni-1andi.keep[i] = keep[i-1]swap[i] = swap[i-1] + 1
- If
swapConditionis true, it means we can maintain the increasing property by cross-swapping betweeni-1andi.keep[i] = min(keep[i], swap[i-1])swap[i] = min(swap[i], keep[i-1] + 1)
- Iterate from
- Final Result:
- The minimum total swaps is the minimum of the two possibilities at the last index:
min(keep[n-1], swap[n-1]).
- The minimum total swaps is the minimum of the two possibilities at the last index:
Walkthrough
We use two DP arrays, keep and swap, of size n. keep[i] stores the minimum swaps to make prefixes nums1[0...i] and nums2[0...i] strictly increasing, with the condition that we do not swap elements at index i. Similarly, swap[i] stores the minimum swaps if we do swap elements at index i.
The base cases are at index 0. keep[0] is 0 because not swapping the first pair of elements costs 0 swaps. swap[0] is 1 because swapping them costs 1 swap.
For any subsequent index i > 0, the values of keep[i] and swap[i] depend on the values at i-1. We check two main conditions:
nums1[i] > nums1[i-1] && nums2[i] > nums2[i-1]: If this is true, the arrays remain increasing if we either kept bothi-1andias they are, or swapped both. This allows a transition fromkeep[i-1]tokeep[i]and fromswap[i-1]toswap[i].nums1[i] > nums2[i-1] && nums2[i] > nums1[i-1]: If this is true, the arrays remain increasing if we swapped at one index (i-1ori) but not the other. This allows a transition fromswap[i-1]tokeep[i]and fromkeep[i-1]toswap[i].
We combine these possibilities to find the minimum costs for keep[i] and swap[i]. The final answer is the minimum of keep[n-1] and swap[n-1]. This same logic can also be implemented using top-down recursion with memoization.
class Solution { public int minSwap(int[] nums1, int[] nums2) { int n = nums1.length; int[] keep = new int[n]; int[] swap = new int[n]; // Base case keep[0] = 0; swap[0] = 1; for (int i = 1; i < n; i++) { keep[i] = Integer.MAX_VALUE; swap[i] = Integer.MAX_VALUE; boolean noSwapCondition = nums1[i] > nums1[i - 1] && nums2[i] > nums2[i - 1]; boolean swapCondition = nums1[i] > nums2[i - 1] && nums2[i] > nums1[i - 1]; if (noSwapCondition) { keep[i] = keep[i - 1]; swap[i] = swap[i - 1] + 1; } if (swapCondition) { keep[i] = Math.min(keep[i], swap[i - 1]); swap[i] = Math.min(swap[i], keep[i - 1] + 1); } } return Math.min(keep[n - 1], swap[n - 1]); }}Complexity
Time
O(N), where N is the length of the arrays. We perform a single pass through the arrays to fill the DP tables.
Space
O(N), where N is the length of the arrays. We use two arrays, `keep` and `swap`, each of size N.
Trade-offs
Pros
Provides a clear and structured way to solve the problem.
The logic is relatively straightforward to follow.
Cons
Uses O(N) extra space, which is not optimal for this problem.
Solutions
Solution
class Solution {public int minSwap(int[] nums1, int[] nums2) { int a = 0, b = 1; for (int i = 1; i < nums1.length; ++i) { int x = a, y = b; if (nums1[i - 1] >= nums1[i] || nums2[i - 1] >= nums2[i]) { a = y; b = x + 1; } else { b = y + 1; if (nums1[i - 1] < nums2[i] && nums2[i - 1] < nums1[i]) { a = Math.min(a, y); b = Math.min(b, x + 1); } } } return Math.min(a, b); }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.