Approach + Memoization solution
\n## (1) why dp? why not simple linar search - greedy?\nnums1 = [0, 4, 4, 5, 9]\nnums2 = [0, 1, 6, 8, 10]\n\nsometimes we can do only 1 coll, either of them\nbu
\n## (1) why dp? why not simple linar search - greedy?\nnums1 = [0, 4, 4, 5, 9]\nnums2 = [0, 1, 6, 8, 10]\n\nsometimes we can do only 1 coll, either of them\nbut if the: idx = 1\nprev1 = 0 prev2 = 0\ncurr1 = 4 curr2 = 1\n\nin this case both the calls, swap or not swap will be done\nand greedy will not work \nas we meed to find out most optimal \nand for that we need to try all ways using recursion/dynammic programming\n\n---\n\n## (2) why adding -1?\n- 0 <= nums1[i], nums2[i] <= 2 * 105 (non negative elements)\n- you need to compare the "index = 0" element (1st element of the array) with someting\nso we can swap them \n\n---\n\n## (3)\n// Case 2: if you swap the current index - i.e. swap(nums1[index], nums2[index])\n// then the current condition will become \nif (nums2[index] > prev1 && nums1[index] > prev2) {\n\n\n---\n\n## (4) Tabulation: we will make the loop of isSwap from 0 to 1, even when it was not done in memoization\nthen this the reason \nWHY MEMOIZATION DON\'T FILL THE COMPLETE DP TABLE \nAND TABULATION DO ALL TYPE OF CALLS SO IT FILLS UP THE DP TABLE\nand this is why in some problems when we need table we use Tabulation and memo can\'t be used \n(as it don\'t fills up the dp table)\n\n"""\nfor (int i = nums1.size() - 1; i >= 1; --i) {\n    for (int isSwapped = 1; isSwapped >= 0; --isSwapped) {\n"""\n\n---\n\n# Approach + Code\n```\n// https://leetcode.com/problems/minimum-swaps-to-make-sequences-increasing/solutions/5373146/most-efficient-way-time-and-space-optimized-4-different-ways-complexity-analysis/\n/*\n(1) why dp? why not simple linar search - greedy?\nnums1 = [0, 4, 4, 5, 9]\nnums2 = [0, 1, 6, 8, 10]\n\nsometimes we can do only 1 coll, either of them\nbut if the: idx = 1\nprev1 = 0 prev2 = 0\ncurr1 = 4 curr2 = 1\n\nin this case both the calls, swap or not swap will be done\nand greedy will not work \nas we meed to find out most optimal \nand for that we need to try all ways using recursion/dynammic programming\n\n(2) why adding -1?\n- 0 <= nums1[i], nums2[i] <= 2 * 105 (non negative elements)\n- you need to compare the "index = 0" element (1st element of the array) with someting\nso we can swap them \n\n(3)\n// Case 2: if you swap the current index - i.e. swap(nums1[index], nums2[index])\n// then the current condition will become \nif (nums2[index] > prev1 && nums1[index] > prev2) {\n\n(4) Tabulation: we will make the loop of isSwap from 0 to 1, even when it was not done in memoization\nthen this the reason \nWHY MEMOIZATION DON\'T FILL THE COMPLETE DP TABLE \nAND TABULATION DO ALL TYPE OF CALLS SO IT FILLS UP THE DP TABLE\nand this is why in some problems when we need table we use Tabulation and memo can\'t be used \n(as it don\'t fills up the dp table)\n\n"""\nfor (int i = nums1.size() - 1; i >= 1; --i) {\n    for (int isSwapped = 1; isSwapped >= 0; --isSwapped) {\n"""\n */\n\n\nclass Solution {\npublic:\n    int solve(vector<int>& nums1, vector<int>& nums2, int index, int isSwapped, vector<vector<int>>& memo) {\n        // Base case: if index is out of bounds, no more swaps needed\n        if (index >= nums1.size()) return 0;\n\n        // If the result is already computed, return it\n        if (memo[index][isSwapped] != -1) return memo[index][isSwapped];\n\n        // Initialize the minimum number of swaps needed as a large number\n        int minSwaps = INT_MAX;\n\n        // Get the previous elements of nums1 and nums2\n        int prev1 = nums1[index - 1];\n        int prev2 = nums2[index - 1];\n\n        // If the previous elements are needed to swap, swap them for comparison\n        if (isSwapped) swap(prev1, prev2);\n\n        // Case 1: No swap at current index\n        if (nums1[index] > prev1 && nums2[index] > prev2) {\n            minSwaps = solve(nums1, nums2, index + 1, 0, memo);\n        }\n\n        // Case 2: if you swap the current index - i.e. swap(nums1[index], nums2[index])\n        // then the current condition will become         \n        if (nums2[index] > prev1 && nums1[index] > prev2) {\n            minSwaps = min(minSwaps, 1 + solve(nums1, nums2, index + 1, 1, memo));\n        }\n\n        // Store the result in the memoization table and return it\n        return memo[index][isSwapped] = minSwaps;\n    }\n\n    int minSwap(vector<int>& nums1, vector<int>& nums2) {\n        // Insert dummy elements at the beginning to simplify indexing\n        nums1.insert(nums1.begin(), -1);\n        nums2.insert(nums2.begin(), -1);\n\n        // Initialize memoization table with -1\n        vector<vector<int>> memo(nums1.size(), vector<int>(2, -1));\n\n        // Start solving from the first actual element, with no swaps initially\n        return solve(nums1, nums2, 1, 0, memo);\n    }\n};\n```\n\n--- \nthis is solution taught by Love Babbar
['C++']