Most Efficient Way🔥| Time And Space Optimized| 4 Different Ways| Complexity Analysis
Complexity\n\n\n\n\n# Pure Recursion\n\nclass Solution {\npublic:\n    int solve(vector<int>& nums1, vector<int>& nums2, int index, int isSwapped) {\n        //
# Complexity\n![image.png](https://assets.leetcode.com/users/images/95ce3b73-93f9-42cb-becc-c60e0c207adc_1719415538.917883.png)\n\n\n\n# Pure Recursion\n```\nclass Solution {\npublic:\n    int solve(vector<int>& nums1, vector<int>& nums2, int index, int isSwapped) {\n        // Base case: if index is out of bounds, no more swaps needed\n        if (index >= nums1.size()) return 0;\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);\n        }\n\n        // Case 2: Swap at current index\n        if (nums1[index] > prev2 && nums2[index] > prev1) {\n            minSwaps = min(minSwaps, 1 + solve(nums1, nums2, index + 1, 1));\n        }\n\n        return 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        // Start solving from the first actual element, with no swaps initially\n        return solve(nums1, nums2, 1, 0);\n    }\n};\n```\n\n# Memoization\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: Swap at current index\n        if (nums1[index] > prev2 && nums2[index] > prev1) {\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# Tabulation \n```\nclass Solution {\npublic:\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 DP table with default values\n        vector<vector<int>> dp(nums1.size() + 1, vector<int>(2, 0));\n\n        // Iterate from the end to the beginning\n        for (int i = nums1.size() - 1; i >= 1; --i) {\n            for (int isSwapped = 1; isSwapped >= 0; --isSwapped) {\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[i - 1];\n                int prev2 = nums2[i - 1];\n\n                // If the previous elements are needed to swap then swap them for comparison\n                if (isSwapped) swap(prev1, prev2);\n\n                // Case 1: No swap at current index\n                if (nums1[i] > prev1 && nums2[i] > prev2) {\n                    minSwaps = dp[i + 1][0];\n                }\n\n                // Case 2: Swap at current index\n                if (nums1[i] > prev2 && nums2[i] > prev1) {\n                    minSwaps = min(minSwaps, 1 + dp[i + 1][1]);\n                }\n\n                // Store the result in the DP table\n                dp[i][isSwapped] = minSwaps;\n            }\n        }\n\n        // Return the minimum number of swaps needed to make both arrays strictly increasing\n        return dp[1][0];\n    }\n};\n```\n\n# Tabulation With Space Optimization\n```\nclass Solution {\npublic:\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 variables to store the results of the previous iteration\n        int noSwapPrev = 0, swapPrev = 0;\n        int noSwapCurr = 0, swapCurr = 0;\n\n        // Iterate from the end to the beginning\n        for (int i = nums1.size() - 1; i >= 1; --i) {\n            for (int isSwapped = 1; isSwapped >= 0; --isSwapped) {\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[i - 1];\n                int prev2 = nums2[i - 1];\n\n                // If the previous elements are needed to swap then swap them for comparison\n                if (isSwapped) swap(prev1, prev2);\n\n                // Case 1: No swap at current index\n                if (nums1[i] > prev1 && nums2[i] > prev2) {\n                    minSwaps = noSwapPrev;\n                }\n\n                // Case 2: Swap at current index\n                if (nums1[i] > prev2 && nums2[i] > prev1) {\n                    minSwaps = min(minSwaps, 1 + swapPrev);\n                }\n\n                // Store the result for the current iteration\n                if (isSwapped == 0) {\n                    noSwapCurr = minSwaps;\n                } else {\n                    swapCurr = minSwaps;\n                }\n            }\n\n            // Update the results for the next iteration\n            noSwapPrev = noSwapCurr;\n            swapPrev = swapCurr;\n        }\n\n        // Return the minimum number of swaps needed to make both arrays strictly increasing\n        return noSwapCurr;\n    }\n};\n```
['Dynamic Programming', 'Backtracking', 'Recursion', 'Memoization', 'C++']