801. Minimum Swaps To Make Sequences Increasing
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:
-
Do not swap elements at index
i
: We choose this if the current elements ofnums1
andnums2
are both greater than the previous elements of their respective arrays, which keeps both arrays strictly increasing without a swap. -
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 indexi
without swappingnums1[i]
andnums2[i]
.b
: The minimum number of swaps needed if we swapnums1[i]
andnums2[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
andb
. Here,a
represents the minimum number of swaps required if we do not swap at the current positioni
, andb
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, andb
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 ofa
andb
into temporary variablesx
andy
. This is to prevent updatinga
andb
simultaneously in the loop, which would give incorrect results, as the calculation ofb
may depend on the old value ofa
. - 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]
ornums2[i-1] >= nums2[i]
, then the arrays are not strictly increasing, and a swap is necessary. In this case, we seta
toy
(the old value ofb
) since we have to swap the previous position, andb
tox + 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, andb
becomesy + 1
since we continue from the previous swap scenario.
- If
- Additionally, if
nums1[i-1] < nums2[i]
andnums2[i-1] < nums1[i]
, then swapping may yield a better result even if itās not necessary. In this case, we updatea
to the minimum of its current value andy
, andb
to the minimum of its current value andx + 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 EvaluatorExample 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
andnums2[1] = 2
. - Previous elements are
nums1[0] = 1
andnums2[0] = 1
. - Arrays are already strictly increasing (
1 < 3
and1 < 2
), so no swap needed here. - We set
tempA = a
andtempB = b
. - Checking further, though, we see that swapping might be beneficial for future positions because
nums2[1] > nums1[0]
andnums1[1] > nums2[0]
. - We update
a
to the minimum ofa
andtempB
which are both0
. - We update
b
to the minimum ofb
andtempA + 1
, which is1
.
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
andnums2[2] = 3
. - Previous elements are
nums1[1] = 3
andnums2[1] = 2
. - We cannot move to the next index without a swap since
nums2[2]
is not greater thannums2[1]
. - Therefore, a swap is necessary for
nums2
. - We again set
tempA = a
andtempB = b
(heretempA = 0
andtempB = 1
). - We set
a
totempB
since we are continuing from the previous decision to swap. - We set
b
totempA + 1
which equals1
. - 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]
andnums2: [1, 3, 5, 4]
. - Current elements are fine as
3 < 7
and5 < 4
requires a swap. - We set
tempA = a
andtempB = 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, wheren
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
andb
, 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
andy
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.
What is an advantages of top-down dynamic programming vs bottom-up dynamic programming?
Recommended Readings
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 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 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!