{x}
blog image

Minimum Swaps To Make Sequences Increasing

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

Minimum Swaps To Make Sequences Increasing

This problem asks for the minimum number of swaps needed to make two arrays strictly increasing. A strictly increasing array means each element is greater than the previous one. We can achieve this using dynamic programming, but a more efficient solution exists using a clever iterative approach.

Approach

The solution uses two variables, a and b. At each step i, a represents the minimum number of swaps needed to make the first i elements of nums1 and nums2 strictly increasing without swapping nums1[i] and nums2[i]. b represents the minimum number of swaps needed if we do swap nums1[i] and nums2[i].

The algorithm iterates through the arrays. For each element, we check two conditions:

  1. No swap needed: If swapping isn't necessary (i.e., nums1[i-1] < nums1[i] and nums2[i-1] < nums2[i]), we can keep a as is (no swaps) and increment b (swapping the i-1th pair would be unnecessary for this step).
  2. Swap is required: If a swap is needed (i.e., at least one of nums1[i-1] >= nums1[i] or nums2[i-1] >= nums2[i] is true), we'll need to update a and b. Swapping at step i means that in the previous step i-1 we did not swap (b value). Not swapping at step i implies a swap was necessary at step i-1 (a value). Therefore we update a = b and b = a+1. If we also have a condition where swapping the previous pair would still result in a strictly increasing sequence after this swap (nums1[i-1] < nums2[i] and nums2[i-1] < nums1[i]), then we can choose the minimum between swapping and not swapping at this step.

Finally, we return the minimum of a and b after iterating through all the elements, representing the overall minimum swaps needed.

Time and Space Complexity

  • Time Complexity: O(N), where N is the length of the arrays. The algorithm iterates through the arrays once.
  • Space Complexity: O(1). The algorithm uses a constant amount of extra space to store the variables a and b.

Code Implementation (Python)

def minSwap(nums1, nums2):
    a, b = 0, 1  # Initialize a and b
 
    for i in range(1, len(nums1)):
        x, y = a, b  # Store previous values of a and b
        
        if nums1[i-1] < nums1[i] and nums2[i-1] < nums2[i]:  # No swap needed
            a, b = a, b + 1  
        else:  # Swap is required
            a, b = y, x + 1
            if nums1[i-1] < nums2[i] and nums2[i-1] < nums1[i]: # Consider both swap and no-swap options
                a, b = min(a, y), min(b, x + 1)  
 
    return min(a, b) # Return the minimum swaps overall

The implementations in Java, C++, and Go are analogous, differing only in syntax. The core logic remains identical. The min() function is used appropriately in each language for comparing and selecting the minimum value.

This solution efficiently solves the problem by cleverly utilizing the dynamic programming concept within an iterative framework, resulting in optimal time and space complexity.