Minimum Swaps To Make Sequences Increasing LeetCode Solution

Difficulty Level Hard
Frequently asked in Amazon Apple Facebook Google OracleViews 2147

Problem Statement

Minimum Swaps To Make Sequences Increasing LeetCode Solution – 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].Minimum Swaps To Make Sequences Increasing LeetCode Solution

Example

Test Case 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.

Approach:

The basic idea behind this problem is the same as what we use in 0 1 knapsack.
So what is the idea in 0 1 knapsack? The idea is that we provide some condition during the function call, and if the condition is satisfied then we have two options (i,e) either include the current element or do not include the current element. But if the condition is not satisfied then we have only one option (i,e) we do not include the current element.

We will use that same idea here.
So what are the different conditions here?

Condition 1 – Ok let’s suppose we have two arrays as follows:-
nums1[] = [3,2]
nums2[] = [1,4]
and we are at index 1. We can see that for nums1 we have nums1[ind-1]>= nums1[ind], So for this condition, we have only one option i.e we have to swap the elements so that the array can be made strictly increasing. So we will swap elements and recursively call the next functions.

Condition 2- lets take another example:-
nums1[] = {1,2}
nums2[] = {3,4}
index = 1;

if we do swapping of the current element then our array will be nums1[] = {1,4} and nums2[] = {3,2}. We can see that the elements in nums2 is not in increasing order. Therefore if (nums1[ind-1] >= nums2[ind] || nums2[ind-1] >= nums1[ind] ) we cannot swap the current element.

Condition 3 –
Now lets take another example
nums1[] = {1,5}
nums2[] = {3,4}
index = 1;

Here we have two options either we swap the current element or we do not swap. So here we will take the minimum answer of both the option and return the answer.

Code for Minimum Swaps To Make Sequences Increasing

Java Program

class Solution {
    public int minSwap(int[] nums1, int[] nums2) {

    int dp[] = new int[nums1.length];
    Arrays.fill(dp,-1);
    
    int ans = solve(nums1,nums2,0,dp);
    
    return ans;
}

public int solve(int nums1[],int nums2[],int ind,int[] dp){
    
    if(ind == nums1.length) return 0;
  
    if(ind>0 && (nums1[ind-1]>=nums1[ind] || nums2[ind-1]>=nums2[ind])) {
      
            int t = nums1[ind];
            nums1[ind] = nums2[ind];
            nums2[ind] = t;
            
           int val = 1+solve(nums1,nums2,ind+1,dp);
        
    
            t = nums1[ind];
            nums1[ind] = nums2[ind];
            nums2[ind] = t;
        
        return val;
        
    }  
  
    else if(ind>0 && (nums1[ind-1]>=nums2[ind] || nums2[ind-1]>=nums1[ind])) {
        return solve(nums1,nums2,ind+1,dp);
    } else {
        if(dp[ind] != -1) return dp[ind];
        
            int tempAns1 = solve(nums1,nums2,ind+1,dp);
    
            int t = nums1[ind];
            nums1[ind] = nums2[ind];
            nums2[ind] = t;
    
            int tempAns2 = 1+solve(nums1,nums2,ind+1,dp);
        
            t = nums1[ind];
            nums1[ind] = nums2[ind];
            nums2[ind] = t;
    
         return dp[ind] = Math.min(tempAns1,tempAns2);
    }
    
}
}

C++ Program

class Solution {
public:
    int minSwap(vector<int>& a, vector<int>& b) {
        unsigned cnt[2][100001] = {0};
        memset(cnt, -1, sizeof(cnt));
        cnt[0][0] = 0;
        cnt[1][0] = 1;
        
        for (int i = 1; i < a.size(); ++i) {
            if (a[i] > a[i - 1] && b[i] > b[i - 1]) {
                cnt[0][i] = min(cnt[0][i], cnt[0][i - 1]);
                 cnt[1][i] = min(cnt[1][i], 1 + cnt[1][i - 1]);
            }
            
            if (a[i] > b[i - 1] && b[i] > a[i - 1]) {
                cnt[0][i] = min(cnt[0][i], cnt[1][i - 1]);
                cnt[1][i] = min(cnt[1][i], 1 + cnt[0][i - 1]);
            }
        }
        
        return min(cnt[0][a.size() - 1], cnt[1][a.size() - 1]);
    }
};

Complexity Analysis for Minimum Swaps To Make Sequences Increasing LeetCode Solution

Time Complexity will be 

Space Complexity will be

Reference: https://en.wikipedia.org/?title=0-1_Knapsack_problem

Translate »