4 Approaches || Recursion || Memoization || Tabulation || Space Optimization ( O(1) ) || Beats 100%
Approach 1: Recursive Approach\n Describe your approach to solving the problem. \n- The function solve uses recursion to explore all possibilities at each index
# Approach 1: Recursive Approach\n<!-- Describe your approach to solving the problem. -->\n- The function solve uses recursion to explore all possibilities at each index in the sequences.\n- Parameters:\n  - nums1 and nums2: The input sequences.\n  - index: The current index being processed.\n  - swapped: A boolean flag indicating whether the previous elements (at index-1) were swapped.\n- Logic:\n   - Base Case: If index equals the size of the arrays, return 0 because no more swaps are needed.\n   - Previous Values: prev1 and prev2 store the previous elements of nums1 and nums2 respectively. If swapped is true, the values of prev1 and prev2 are swapped to reflect the fact that the previous elements were swapped.\n   - No Swap: If the current elements (nums1[index] and nums2[index]) are greater than their respective previous elements, recursively solve the problem without swapping (swapped = 0).\n   - Swap: If swapping the current elements maintains the strictly increasing property, recursively solve the problem with a swap (swapped = 1) and increment the swap count.\n- Return: The minimum of the results from the two options.\n\n# Complexity\n- Time complexity: O(2^n)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(n)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```cpp []\nclass Solution {\nprivate:\n    int solve(vector<int>& nums1, vector<int>& nums2,int index,int swapped)\n    {\n         //base case\n         if(index==nums1.size()) return 0;\n\n         int ans=INT_MAX;\n\n         int prev1=nums1[index-1];\n         int prev2=nums2[index-1];\n\n         //catch\n         if(swapped) swap(prev1,prev2);\n\n         //noswap\n         if(nums1[index]>prev1 && nums2[index]>prev2) ans=solve(nums1,nums2,index+1,0);\n         \n         //swap\n         if(nums1[index]>prev2 && nums2[index]>prev1)\n         {\n             ans=min(ans,1+solve(nums1,nums2,index+1,1));\n         }\n\n         return ans;\n    }\n\npublic:\n    int minSwap(vector<int>& nums1, vector<int>& nums2) {\n        nums1.insert(nums1.begin(),-1);\n        nums2.insert(nums2.begin(),-1);\n       //it means that the previous indexes were swapped or not \n        bool swapped=0;\n        return solve(nums1,nums2,1,swapped);\n\n    }\n};\n```\n\n# Approach 2: Memoization\n<!-- Describe your approach to solving the problem. -->\n- This approach adds a memoization table dp to store results of subproblems to avoid recomputation.\n- Parameters:\n   - Similar to solve, but with an additional dp table to store results for each (index, swapped) pair.\n- Logic:\n   - If a result for (index, swapped) is already computed, return it from dp.\n   - Otherwise, compute it similarly to solve and store the result in dp.\n\n# Complexity\n- Time complexity: O(n)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(n)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```cpp []\nclass Solution {\nprivate:\n        int solveMem(vector<int>& nums1, vector<int>& nums2,int index,int swapped,vector<vector<int>> &dp)\n    {\n         //base case\n         if(index==nums1.size()) return 0;\n\n         if(dp[index][swapped]!=-1) return dp[index][swapped];\n\n         int ans=INT_MAX;\n\n         int prev1=nums1[index-1];\n         int prev2=nums2[index-1];\n\n         //catch\n         if(swapped) swap(prev1,prev2);\n\n         //noswap\n         if(nums1[index]>prev1 && nums2[index]>prev2) ans=solveMem(nums1,nums2,index+1,0,dp);\n         \n         //swap\n         if(nums1[index]>prev2 && nums2[index]>prev1)\n         {\n             ans=min(ans,1+solveMem(nums1,nums2,index+1,1,dp));\n         }\n\n         return dp[index][swapped]=ans;\n    }\n\n\npublic:\n    int minSwap(vector<int>& nums1, vector<int>& nums2) {\n\n         nums1.insert(nums1.begin(),-1);\n         nums2.insert(nums2.begin(),-1);\n        //it means that the previous indexes were swapped or not \n         bool swapped=0;\n\n         int n=nums1.size();\n\n         vector<vector<int>> dp(n,vector<int> (2,-1));\n         return solveMem(nums1,nums2,1,swapped,dp);\n    }\n};\n```\n\n\n# Approach 3: Tabulation\n<!-- Describe your approach to solving the problem. -->\n- This method builds the solution iteratively from the last index to the first.\n- Parameters:\n   - A dp table is created with dimensions [n+1][2] where n is the size of the arrays, and the second dimension represents the swapped state (0 or 1).\n- Logic:\n   - Iterate backward through the arrays, considering both swap and no swap scenarios.\n    - Fill the dp table based on the conditions described above.\n\n# Complexity\n- Time complexity: O(n)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(n)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```cpp []\nclass Solution {\nprivate:\n    int solveTab(vector<int> &nums1,vector<int> &nums2)\n    {\n        int n=nums1.size();\n        vector<vector<int>> dp(n+1,vector<int> (2,0));\n\n        for(int index=n-1;index>=1;index--)\n        {\n            for(int swapped=1;swapped>=0;swapped--)\n            {\n                 \n                int ans=INT_MAX;\n\n                int prev1=nums1[index-1];\n                int prev2=nums2[index-1];\n\n                //catch\n                if(swapped) swap(prev1,prev2);\n\n                //noswap\n                if(nums1[index]>prev1 && nums2[index]>prev2) ans=dp[index+1][0];\n         \n                //swap\n                if(nums1[index]>prev2 && nums2[index]>prev1)\n                {\n                  ans=min(ans,1+dp[index+1][1]);\n                }\n\n                dp[index][swapped]=ans; \n            }\n        }\n        return dp[1][0];\n    }\npublic:\n    int minSwap(vector<int>& nums1, vector<int>& nums2) {\n             nums1.insert(nums1.begin(),-1);\n             nums2.insert(nums2.begin(),-1);\n\n             return solveTab(nums1,nums2);\n    }\n};\n```\n\n\n# Approach 4: Space Optimization\n<!-- Describe your approach to solving the problem. -->\n- This approach further optimizes space by using only two variables to keep track of the current and previous results (swapp and noswap).\n- Parameters:\n   - Instead of a full dp table, use only two sets of variables (currswap, currnoswap) to store results for the current index.\n- Logic:\n  - Process each index similarly but only keep track of the necessary values for the next iteration.\n\n# Complexity\n- Time complexity: O(n)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(1)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```cpp []\nclass Solution {\nprivate:\n    int solveSO(vector<int> &nums1,vector<int> &nums2)\n    {\n        int n=nums1.size();\n\n        int swapp=0;\n        int noswap=0;\n        int currswap=0;\n        int currnoswap=0;\n\n\n        for(int index=n-1;index>=1;index--)\n        {\n            for(int swapped=1;swapped>=0;swapped--)\n            {\n                 \n                int ans=INT_MAX;\n\n                int prev1=nums1[index-1];\n                int prev2=nums2[index-1];\n\n                //catch\n                if(swapped) swap(prev1,prev2);\n\n                //noswap\n                if(nums1[index]>prev1 && nums2[index]>prev2) ans=noswap;\n         \n                //swap\n                if(nums1[index]>prev2 && nums2[index]>prev1)\n                {\n                  ans=min(ans,1+swapp);\n                }\n\n               if(swapped) currswap=ans;\n               else currnoswap=ans; \n            }\n            swapp=currswap;\n            noswap=currnoswap;\n        }\n        return min(swapp,noswap);\n    }\npublic:\n    int minSwap(vector<int>& nums1, vector<int>& nums2) {\n            nums1.insert(nums1.begin(),-1);\n            nums2.insert(nums2.begin(),-1);\n\n            return solveSO(nums1,nums2);\n\n    }\n};\n```\n![upvote.jpg](https://assets.leetcode.com/users/images/9aa1cda4-239f-43cd-a838-ae52d146ab4d_1724961502.97975.jpeg)\n
['Array', 'Dynamic Programming', 'Recursion', 'Memoization', 'C++']