801. Minimum Swaps To Make Sequences Increasing

HardArrayDynamic Programming
Leetcode Link

Problem Description

In this problem, we have two integer arrays nums1 and nums2 of the same length. Our goal is to make both arrays strictly increasing by swapping elements at the same index in both arrays. To clarify, nums1[i] can be swapped with nums2[i] for any i. What we're trying to find is the minimum number of such swaps required to achieve our goal. An array is strictly increasing if each element is larger than the one before it. The challenge assures us that there is always a way to make the arrays strictly increasing through such swaps.

Intuition

To solve this problem, dynamic programming is employed to keep track of the minimum number of swaps needed. At each index i, we have two choices:

  1. Do not swap elements at index i: We choose this if the current elements of nums1 and nums2 are both greater than the previous elements of their respective arrays, which keeps both arrays strictly increasing without a swap.

  2. Swap elements at index i: If the current elements are not greater than the previous ones, we must swap to maintain the strictly increasing order. In some cases, even when it's not required to maintain the strictly increasing order, swapping might still minimize the total number of swaps.

We maintain two variables:

  • a: The minimum number of swaps needed up to the current index i without swapping nums1[i] and nums2[i].
  • b: The minimum number of swaps needed if we swap nums1[i] and nums2[i].

After considering whether a swap is required or beneficial at each index, and updating a and b accordingly, the solution returns the minimum of a and b after iterating through the arrays, which represents the minimum number of swaps necessary to make both nums1 and nums2 strictly increasing.

Learn more about Dynamic Programming patterns.

Solution Approach

The solution uses a dynamic programming approach to minimize the number of swaps required to make both arrays strictly increasing. Let's walk through the implementation details:

  • We initialize two variables, a and b. Here, a represents the minimum number of swaps required if we do not swap at the current position i, and b is the minimum number of swaps required if we do swap at the current position.
  • a is initially set to 0, because no swaps are performed at the start, and b is set to 1 since performing a swap at the first position would count as one operation.

The main loop of the algorithm starts at index 1 and goes until the end of the arrays as follows:

  • For each index i, we first store the old values of a and b into temporary variables x and y. This is to prevent updating a and b simultaneously in the loop, which would give incorrect results, as the calculation of b may depend on the old value of a.
  • There are conditions that determine if a swap is necessary or if we can move to the next index without a swap:
    • If nums1[i-1] >= nums1[i] or nums2[i-1] >= nums2[i], then the arrays are not strictly increasing, and a swap is necessary. In this case, we set a to y (the old value of b) since we have to swap the previous position, and b to x + 1 because we are performing a swap at the current position, which adds to the swap count.
    • If the arrays are already strictly increasing without a swap, a remains unchanged, and b becomes y + 1 since we continue from the previous swap scenario.
  • Additionally, if nums1[i-1] < nums2[i] and nums2[i-1] < nums1[i], then swapping may yield a better result even if it’s not necessary. In this case, we update a to the minimum of its current value and y, and b to the minimum of its current value and x + 1.

In the end, we return the minimum of a and b, as this would represent either performing no swap or swapping at the last index, whichever has the minimum swaps overall to make the arrays strictly increasing.

By using dynamic programming, we avoid re-computation for each index, evaluating the minimum number of swaps needed at each step. This approach ensures that the final complexity of the algorithm is O(n), where n is the length of the given arrays.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's consider two small integer arrays nums1 and nums2:

nums1: [1, 3, 5, 7]
nums2: [1, 2, 3, 4]

According to the problem, we want to make both arrays strictly increasing by swapping elements at the same index where necessary.

Initialization:

  • No swaps at the start, so a = 0.
  • If we swap at the first position, it would count as one swap, so b = 1.

We start our loop from index 1 and go up to the last index.

At index 1:

  • Current elements are nums1[1] = 3 and nums2[1] = 2.
  • Previous elements are nums1[0] = 1 and nums2[0] = 1.
  • Arrays are already strictly increasing (1 < 3 and 1 < 2), so no swap needed here.
  • We set tempA = a and tempB = b.
  • Checking further, though, we see that swapping might be beneficial for future positions because nums2[1] > nums1[0] and nums1[1] > nums2[0].
  • We update a to the minimum of a and tempB which are both 0.
  • We update b to the minimum of b and tempA + 1, which is 1.

Now our arrays look like this (no change because no swap was done):

nums1: [1, 3, 5, 7]
nums2: [1, 2, 3, 4]

At index 2:

  • Current elements are nums1[2] = 5 and nums2[2] = 3.
  • Previous elements are nums1[1] = 3 and nums2[1] = 2.
  • We cannot move to the next index without a swap since nums2[2] is not greater than nums2[1].
  • Therefore, a swap is necessary for nums2.
  • We again set tempA = a and tempB = b (here tempA = 0 and tempB = 1).
  • We set a to tempB since we are continuing from the previous decision to swap.
  • We set b to tempA + 1 which equals 1.
  • After swapping, our arrays looks like this:
nums1: [1, 3, 3, 7]
nums2: [1, 2, 5, 4]
  • But now we have a problem as nums1 is no longer strictly increasing. We must also swap at index 1 to correct this.

Result after also swapping at index 1:

nums1: [1, 2, 3, 7]
nums2: [1, 3, 5, 4]

At index 3:

  • Arrays are nums1: [1, 2, 3, 7] and nums2: [1, 3, 5, 4].
  • Current elements are fine as 3 < 7 and 5 < 4 requires a swap.
  • We set tempA = a and tempB = b.
  • Since the arrays without the current elements being swapped are increasing, we do not update a.
  • To minimize total swaps, we choose not to swap here, so b = tempB + 1.

Finally, our arrays look like this, which are both strictly increasing:

nums1: [1, 2, 3, 7]
nums2: [1, 3, 5, 4]

The minimum number of swaps required is min(a, b). Given the values of a = 0 and b = 2, the minimum number of swaps is 0.

This small example illustrated the solution approach using dynamic programming, where we made both nums1 and nums2 strictly increasing while minimizing the total number of swaps necessary.

Solution Implementation

1from typing import List
2
3class Solution:
4    def minSwap(self, nums1: List[int], nums2: List[int]) -> int:
5        # Initialize the number of swaps when not swapping or swapping the i-th element
6        no_swap, swap = 0, 1
7      
8        # Iterate over arrays starting from the second element (index 1)
9        for i in range(1, len(nums1)):
10            no_swap_cost, swap_cost = no_swap, swap
11            if nums1[i - 1] >= nums1[i] or nums2[i - 1] >= nums2[i]:
12                # If the current pair or the previous pair is not strictly increasing,
13                # we must swap this pair to make the sequence increasing
14                no_swap, swap = swap_cost, no_swap_cost + 1
15            else:
16                # If it is strictly increasing, no need to swap the previous pair
17                swap = swap_cost + 1  # We can choose to swap the current pair
18                # If swapping makes both arrays increasing,
19                # consider minimum swaps by either swapping or not swapping previous pairs
20                if nums1[i - 1] < nums2[i] and nums2[i - 1] < nums1[i]:
21                    no_swap, swap = min(no_swap, swap_cost), min(swap, no_swap_cost + 1)
22      
23        # Return the minimum number of swaps to make both arrays strictly increasings
24        return min(no_swap, swap)
25
1class Solution {
2    public int minSwap(int[] nums1, int[] nums2) {
3        // Initialize the two states: 'swap' and 'notSwap'.
4        // swap: min swaps needed when the last element is swapped.
5        // notSwap: min swaps needed when the last element is not swapped.
6        int notSwap = 0, swap = 1;
7      
8        // Iterate through each pair of elements starting from the second pair.
9        for (int i = 1; i < nums1.length; ++i) {
10            // 'prevNotSwap' and 'prevSwap' hold the previous state's values.
11            int prevNotSwap = notSwap, prevSwap = swap;
12          
13            // Reset the values for the current state.
14            notSwap = swap = nums1.length;
15          
16            // Check if the current and previous elements of both arrays are strictly increasing.
17            if (nums1[i - 1] < nums1[i] && nums2[i - 1] < nums2[i]) {
18                // If no swap is needed, carry forward the previous notSwap value.
19                notSwap = prevNotSwap;
20                // If we choose to swap the current elements, add 1 to the previous swap value.
21                swap = prevSwap + 1;
22            }
23          
24            // Check if swapping the previous elements makes the current pair strictly increasing.
25            if (nums1[i - 1] < nums2[i] && nums2[i - 1] < nums1[i]) {
26                // If so, notSwap can also be the minimum of itself and the previous swap value.
27                notSwap = Math.min(notSwap, prevSwap);
28                // Similarly, swap can also be the minimum of itself and prevNotSwap+1.
29                swap = Math.min(swap, prevNotSwap + 1);
30            }
31        }
32      
33        // Return the minimum of the two final states.
34        return Math.min(notSwap, swap);
35    }
36}
37
1class Solution {
2public:
3    int minSwap(vector<int>& nums1, vector<int>& nums2) {
4        int noSwap = 0;     // Initialize noSwap, representing the minimum swaps needed without swapping the current element.
5        int swap = 1;       // Initialize swap, representing the minimum swaps needed with swapping the current element.
6        int numElements = nums1.size(); // Get the number of elements in the arrays.
7
8        // Loop through the arrays starting from the second element
9        for (int i = 1; i < numElements; ++i) {
10            int prevNoSwap = noSwap; // Store the previous noSwap value
11            int prevSwap = swap;     // Store the previous swap value
12
13            // Reset noSwap and swap for the current iteration
14            noSwap = numElements;
15            swap = numElements;
16
17            // Check if it is not possible to proceed without swapping (i.e. strictly increasing not maintained)
18            if (nums1[i - 1] >= nums1[i] || nums2[i - 1] >= nums2[i]) {
19                // If an element at index i or index i-1 must be swapped to remain strictly increasing:
20                // Current noSwap takes the value of previous swap
21                // Current swap takes the value of one plus the previous noSwap
22                noSwap = prevSwap;
23                swap = prevNoSwap + 1;
24            } else {
25                // If current configuration already strictly increasing without swapping
26                // swap value should consider at least one more swap (previous swap + 1)
27                swap = prevSwap + 1;
28                // Check if arrays are both strictly increasing if we swapped the previous pair
29                if (nums1[i - 1] < nums2[i] && nums2[i - 1] < nums1[i]) {
30                    // Minimal swaps can be either previous noSwap or swap, take the minimum.
31                    noSwap = min(noSwap, prevSwap);
32                    // Similarly, current swap can also be minimum of it or noSwap plus one (accounting for a swap at the previous step)
33                    swap = min(swap, prevNoSwap + 1);
34                }
35            }
36        }
37
38        // Return the minimum of noSwap and swap for the last element,
39        // it gives the minimum number of swaps to make both sequences strictly increasing.
40        return min(noSwap, swap);
41    }
42};
43
1// Function to calculate the minimum number of swaps required
2// to make two arrays strictly increasing
3function minSwap(nums1: number[], nums2: number[]): number {
4    let noSwap = 0; // Minimum swaps needed without swapping the current element
5    let swap = 1; // Minimum swaps needed with swapping the current element
6    const numElements = nums1.length; // Get the number of elements in the arrays
7
8    // Loop through both arrays, starting from the second element
9    for (let i = 1; i < numElements; ++i) {
10        const prevNoSwap = noSwap; // Store the previous noSwap value
11        const prevSwap = swap; // Store the previous swap value
12
13        // Reset noSwap and swap for the current iteration to a large value
14        noSwap = numElements;
15        swap = numElements;
16
17        // No change required if both arrays are already strictly increasing
18        if (nums1[i - 1] < nums1[i] && nums2[i - 1] < nums2[i]) {
19            // Current configuration is already strictly increasing without swapping
20            noSwap = prevNoSwap;
21            // Increment swap because we consider it's possible
22            // that we may have swapped the previous pair
23            swap = prevSwap + 1;
24        }
25
26        // If either pair can be swapped to maintain a strictly increasing order
27        if (nums1[i - 1] < nums2[i] && nums2[i - 1] < nums1[i]) {
28            // The new noSwap can potentially be the previous swap (if the previous was swapped)
29            noSwap = Math.min(noSwap, prevSwap);
30            // The new swap can potentially be the previous noSwap plus one
31            swap = Math.min(swap, prevNoSwap + 1);
32        }
33    }
34
35    // Return the smaller of noSwap and swap for the final element,
36    // this will yield the minimum number of swaps to make both sequences strictly increasing.
37    return Math.min(noSwap, swap);
38}
39
40// Example usage:
41const nums1 = [1, 3, 5];
42const nums2 = [1, 2, 3];
43console.log(minSwap(nums1, nums2)); // Output will be minimum swaps required
44

Time and Space Complexity

The code provided is a dynamic programming solution designed to determine the minimum number of swaps needed to make two lists strictly increasing.

Time Complexity

To analyze the time complexity of this approach, we need to consider the operations performed with each iteration of the loop that runs len(nums1) times.

  • Within each iteration, the algorithm performs constant-time comparisons and assignments, regardless of the size of the lists.
  • The loop runs for every element of the two lists starting from index 1, which means it runs n-1 times, where n is the number of elements in each list.

As the time taken per iteration does not depend on the size of the dataset, the overall time complexity of the algorithm is O(n), where n is the length of the lists.

Space Complexity

For the space complexity:

  • Two variables, a and b, are used to keep track of the minimum number of swaps when the ith element is not swapped and when it is swapped, respectively.
  • Additionally, temporary variables x and y are used within the loop.

Since the space used does not increase with the size of the input lists, this algorithm has a constant space complexity, thus the space complexity is O(1).

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

Given a sorted array of integers and an integer called target, find the element that equals to the target and return its index. Select the correct code that fills the ___ in the given code snippet.

1def binary_search(arr, target):
2    left, right = 0, len(arr) - 1
3    while left ___ right:
4        mid = (left + right) // 2
5        if arr[mid] == target:
6            return mid
7        if arr[mid] < target:
8            ___ = mid + 1
9        else:
10            ___ = mid - 1
11    return -1
12
1public static int binarySearch(int[] arr, int target) {
2    int left = 0;
3    int right = arr.length - 1;
4
5    while (left ___ right) {
6        int mid = left + (right - left) / 2;
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16
1function binarySearch(arr, target) {
2    let left = 0;
3    let right = arr.length - 1;
4
5    while (left ___ right) {
6        let mid = left + Math.trunc((right - left) / 2);
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

Recommended Readings

Dynamic Programming Introduction and Patterns

What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution

LeetCode Patterns: The Smart, Data-Driven Way to Prepare for Tech Interviews

LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More