819. Minimum Swaps To Make Sequences Increasing¶

Difficulty: Hard

819. Minimum Swaps To Make Sequences Increasing

Hard

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

Solution¶

import java.util.Arrays;

class Solution {
    private int dp[][];
    public int minSwap(int[] nums1, int[] nums2) {
        int n = nums1.length;
        dp = new int[n + 1][2];
        for (int current[] : dp)
            Arrays.fill(current, -1);
        return solve(nums1, nums2, -1, -1, 0, 0);
    }
    private int solve(int arr[], int brr[], int prevA, int prevB, int ind, int swap) {
        if (ind >= arr.length)
            return 0;
        if (dp[ind][swap] != -1)
            return dp[ind][swap];

        int mini = Integer.MAX_VALUE / 10;
        if (arr[ind] > prevA && brr[ind] > prevB)
            mini = Math.min(mini, 0 + solve(arr, brr, arr[ind], brr[ind], ind + 1, 0));
        if (arr[ind] > prevB && brr[ind] > prevA)
            mini = Math.min(mini, 1 + solve(arr, brr, brr[ind], arr[ind], ind + 1, 1));

        return dp[ind][swap] = mini;
    }
}

Complexity Analysis¶

Time Complexity: O(?)
Space Complexity: O(?)

Approach¶

Detailed explanation of the approach will be added here