Leetcode 819 Solution

This article provides solution to leetcode question 819 (minimum-swaps-to-make-sequences-increasing)
Categories:
Tags:
Access this page by simply typing in "lcs 819" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/minimum-swaps-to-make-sequences-increasing

Solution

class Solution {
public:
    int minSwap(vector<int>& A, vector<int>& B) {
        int n = A.size();

        if (n == 0)
            return 0;

        vector<int> dp1(n, INT_MAX);
        vector<int> dp2(n, INT_MAX);

        dp1[0] = 0;
        dp2[0] = 1;

        for (int i = 1; i < n; i++)
        {
            if (A[i] > A[i - 1] && B[i] > B[i - 1])
                dp1[i] = min(dp1[i - 1], dp1[i]);

            if (A[i] > B[i - 1] && B[i] > A[i - 1])
                dp1[i] = min(dp2[i - 1], dp1[i]);

            if (B[i] > A[i - 1] && A[i] > B[i - 1])
                dp2[i] = min(dp1[i - 1] + 1, dp2[i]);

            if (B[i] > B[i - 1] && A[i] > A[i - 1])
                dp2[i] = min(dp2[i - 1] + 1, dp2[i]);
        }

        return min(dp1[n - 1], dp2[n - 1]);
    }
};