801. Minimum Swaps To Make Sequences Increasing LeetCode Solution

In this guide, you will get 801. Minimum Swaps To Make Sequences Increasing LeetCode Solution with the best time and space complexity. The solution to Minimum Swaps To Make Sequences Increasing problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

1. Problem Statement
2. Complexity Analysis
3. Minimum Swaps To Make Sequences Increasing solution in C++
4. Minimum Swaps To Make Sequences Increasing solution in Java
5. Minimum Swaps To Make Sequences Increasing solution in Python
6. Additional Resources

Problem Statement of 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

Complexity Analysis

• Time Complexity: O(n)
• Space Complexity: O(n)

801. Minimum Swaps To Make Sequences Increasing LeetCode Solution in C++

class Solution {
 public:
  int minSwap(vector<int>& nums1, vector<int>& nums2) {
    vector<int> keepAt(nums1.size(), INT_MAX);
    vector<int> swapAt(nums1.size(), INT_MAX);
    keepAt[0] = 0;
    swapAt[0] = 1;

    for (int i = 1; i < nums1.size(); ++i) {
      if (nums1[i] > nums1[i - 1] && nums2[i] > nums2[i - 1]) {
        keepAt[i] = keepAt[i - 1];
        swapAt[i] = swapAt[i - 1] + 1;
      }
      if (nums1[i] > nums2[i - 1] && nums2[i] > nums1[i - 1]) {
        keepAt[i] = min(keepAt[i], swapAt[i - 1]);
        swapAt[i] = min(swapAt[i], keepAt[i - 1] + 1);
      }
    }

    return min(keepAt.back(), swapAt.back());
  }
};
/* code provided by PROGIEZ */

801. Minimum Swaps To Make Sequences Increasing LeetCode Solution in Java

class Solution {
  public int minSwap(int[] nums1, int[] nums2) {
    final int n = nums1.length;
    int[] keepAt = new int[n];
    int[] swapAt = new int[n];
    Arrays.fill(keepAt, Integer.MAX_VALUE);
    Arrays.fill(swapAt, Integer.MAX_VALUE);
    keepAt[0] = 0;
    swapAt[0] = 1;

    for (int i = 1; i < n; ++i) {
      if (nums1[i] > nums1[i - 1] && nums2[i] > nums2[i - 1]) {
        keepAt[i] = keepAt[i - 1];
        swapAt[i] = swapAt[i - 1] + 1;
      }
      if (nums1[i] > nums2[i - 1] && nums2[i] > nums1[i - 1]) {
        keepAt[i] = Math.min(keepAt[i], swapAt[i - 1]);
        swapAt[i] = Math.min(swapAt[i], keepAt[i - 1] + 1);
      }
    }

    return Math.min(keepAt[n - 1], swapAt[n - 1]);
  }
}
// code provided by PROGIEZ

801. Minimum Swaps To Make Sequences Increasing LeetCode Solution in Python

class Solution:
  def minSwap(self, nums1: list[int], nums2: list[int]) -> int:
    keepAt = [math.inf] * len(nums1)
    swapAt = [math.inf] * len(nums1)
    keepAt[0] = 0
    swapAt[0] = 1

    for i in range(1, len(nums1)):
      if nums1[i] > nums1[i - 1] and nums2[i] > nums2[i - 1]:
        keepAt[i] = keepAt[i - 1]
        swapAt[i] = swapAt[i - 1] + 1
      if nums1[i] > nums2[i - 1] and nums2[i] > nums1[i - 1]:
        keepAt[i] = min(keepAt[i], swapAt[i - 1])
        swapAt[i] = min(swapAt[i], keepAt[i - 1] + 1)

    return min(keepAt[-1], swapAt[-1])
 # code by PROGIEZ

Additional Resources

• Explore all LeetCode problem solutions at Progiez here
• Explore all problems on LeetCode website here

Happy Coding! Keep following PROGIEZ for more updates and solutions.