Minimum Swaps To Make Sequences Increasing

Hard

#0755Time: 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.

Patterns

Dynamic Programming

Data structures

Array

Prompt

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], 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 <= 10⁵
nums2.length == nums1.length
0 <= nums1[i], nums2[i] <= 2 * 10⁵

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, keep and swap, of the same length n as the input arrays.
keep[i] will store the minimum swaps for the prefix 0...i to be strictly increasing, with no swap at index i.
swap[i] will store the minimum swaps for the prefix 0...i to be strictly increasing, with a swap at index i.
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 = 1 to n-1.
- For each i, we consider two possibilities for the state at i-1 (kept or swapped) to determine the cost for the state at i.
- 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 noSwapCondition is true, it means we can maintain the increasing property without cross-swapping between i-1 and i.
  - keep[i] = keep[i-1]
  - swap[i] = swap[i-1] + 1
- If swapCondition is true, it means we can maintain the increasing property by cross-swapping between i-1 and i.
  - keep[i] = min(keep[i], swap[i-1])
  - swap[i] = min(swap[i], keep[i-1] + 1)
Final Result:
- The minimum total swaps is the minimum of the two possibilities at the last index: min(keep[n-1], swap[n-1]).

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 both i-1 and i as they are, or swapped both. This allows a transition from keep[i-1] to keep[i] and from swap[i-1] to swap[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-1 or i) but not the other. This allows a transition from swap[i-1] to keep[i] and from keep[i-1] to swap[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.

1class Solution {2    public int minSwap(int[] nums1, int[] nums2) {3        int n = nums1.length;4        int[] keep = new int[n];5        int[] swap = new int[n];6 7        // Base case8        keep[0] = 0;9        swap[0] = 1;10 11        for (int i = 1; i < n; i++) {12            keep[i] = Integer.MAX_VALUE;13            swap[i] = Integer.MAX_VALUE;14 15            boolean noSwapCondition = nums1[i] > nums1[i - 1] && nums2[i] > nums2[i - 1];16            boolean swapCondition = nums1[i] > nums2[i - 1] && nums2[i] > nums1[i - 1];17 18            if (noSwapCondition) {19                keep[i] = keep[i - 1];20                swap[i] = swap[i - 1] + 1;21            }22 23            if (swapCondition) {24                keep[i] = Math.min(keep[i], swap[i - 1]);25                swap[i] = Math.min(swap[i], keep[i - 1] + 1);26            }27        }28 29        return Math.min(keep[n - 1], swap[n - 1]);30    }31}

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.

The previous dynamic programming approach can be optimized in terms of space. Notice that the calculations for keep[i] and swap[i] only depend on the values from the immediately preceding index, i-1. This means we don't need to store the entire history of keep and swap values in arrays. We only need to keep track of the values from the previous step, which allows us to reduce the space complexity from O(N) to O(1).

Algorithm

Initialize four variables:
- prev_keep: Stores the minimum swaps for the prefix ending at i-1 without a swap at i-1. Initialize to 0.
- prev_swap: Stores the minimum swaps for the prefix ending at i-1 with a swap at i-1. Initialize to 1.
- curr_keep: A temporary variable to compute the keep value for the current index i.
- curr_swap: A temporary variable to compute the swap value for the current index i.
Iterate from i = 1 to n-1:
- Initialize curr_keep and curr_swap to a large value (e.g., Integer.MAX_VALUE).
- Check the same two conditions as in the previous approach: noSwapCondition and swapCondition.
- If noSwapCondition is true:
  - curr_keep = prev_keep
  - curr_swap = prev_swap + 1
- If swapCondition is true:
  - curr_keep = min(curr_keep, prev_swap)
  - curr_swap = min(curr_swap, prev_keep + 1)
- After computing the values for the current index i, update the prev variables for the next iteration:
  - prev_keep = curr_keep
  - prev_swap = curr_swap
Final Result:
- After the loop finishes, the answer is min(prev_keep, prev_swap).

Walkthrough

Instead of using two arrays, we use four variables to track the states. prev_keep and prev_swap hold the minimum swap counts for the prefix ending at i-1 (without and with a swap at i-1, respectively). curr_keep and curr_swap are used to calculate these values for the current index i.

We start by initializing prev_keep = 0 and prev_swap = 1, which represent the base case at index 0. Then, we iterate from i = 1 to n-1. In each iteration, we calculate curr_keep and curr_swap using the exact same transition logic as the O(N) space approach, but reading from prev_keep and prev_swap instead of keep[i-1] and swap[i-1]. After the calculation for index i is complete, we update prev_keep and prev_swap with the curr_keep and curr_swap values to prepare for the next iteration. This rolling update mechanism effectively discards old state information that is no longer needed, leading to constant space usage.

1class Solution {2    public int minSwap(int[] nums1, int[] nums2) {3        int n = nums1.length;4 5        // prev_keep: min swaps for prefix i-1, without swapping at i-16        // prev_swap: min swaps for prefix i-1, with a swap at i-17        int prev_keep = 0;8        int prev_swap = 1;9 10        for (int i = 1; i < n; i++) {11            int curr_keep = Integer.MAX_VALUE;12            int curr_swap = Integer.MAX_VALUE;13 14            boolean noSwapCondition = nums1[i] > nums1[i - 1] && nums2[i] > nums2[i - 1];15            boolean swapCondition = nums1[i] > nums2[i - 1] && nums2[i] > nums1[i - 1];16 17            if (noSwapCondition) {18                curr_keep = prev_keep;19                curr_swap = prev_swap + 1;20            }21 22            if (swapCondition) {23                curr_keep = Math.min(curr_keep, prev_swap);24                curr_swap = Math.min(curr_swap, prev_keep + 1);25            }26            27            prev_keep = curr_keep;28            prev_swap = curr_swap;29        }30 31        return Math.min(prev_keep, prev_swap);32    }33}

Complexity

Time

O(N), where N is the length of the arrays. We still need to iterate through the arrays once.

Space

O(1). We only use a constant number of variables to store the states of the previous and current steps, regardless of the input size.

Trade-offs

Pros

Highly efficient, with optimal O(1) space complexity.
Maintains the same O(N) time complexity as the unoptimized version.

Cons

The logic might be slightly less direct to grasp initially compared to the version with full DP arrays.

Solutions

Solution

1class Solution {2public3  int minSwap(int[] nums1, int[] nums2) {4    int a = 0, b = 1;5    for (int i = 1; i < nums1.length; ++i) {6      int x = a, y = b;7      if (nums1[i - 1] >= nums1[i] || nums2[i - 1] >= nums2[i]) {8        a = y;9        b = x + 1;10      } else {11        b = y + 1;12        if (nums1[i - 1] < nums2[i] && nums2[i - 1] < nums1[i]) {13          a = Math.min(a, y);14          b = Math.min(b, x + 1);15        }16      }17    }18    return Math.min(a, b);19  }20}

1class Solution {2public:3  int minSwap(vector<int> &nums1, vector<int> &nums2) {4    int a = 0, b = 1, n = nums1.size();5    for (int i = 1; i < n; ++i) {6      int x = a, y = b;7      if (nums1[i - 1] >= nums1[i] || nums2[i - 1] >= nums2[i]) {8        a = y, b = x + 1;9      } else {10        b = y + 1;11        if (nums1[i - 1] < nums2[i] && nums2[i - 1] < nums1[i]) {12          a = min(a, y);13          b = min(b, x + 1);14        }15      }16    }17    return min(a, b);18  }19};

1class Solution:2    def minSwap(self, nums1: List[int], nums2: List[int]) -> int: a, b = 0, 1 for i in range(1, len(nums1)): x, y = a, b if nums1[i - 1] >= nums1[i] or nums2[i - 1] >= nums2[i]: a, b = y, x + 1 else: b = y + 1 if nums1[i - 1] < nums2[i] and nums2[i - 1] < nums1[i]: a, b = min(a, y), min(b, x + 1) return 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.

← Previous

Previous problem

Next problem