space optimized || using dynamic programming ||  beats (runtime -> 94.41%) (memory-> 90.65%)🔥
Time complexity:\nO(N)\n\n- Space complexity:\nO(1)\n\n# Code\n\nclass Solution {\npublic:\n\nusing recursion\n\n\n    int rec(vector<int>& nums1, vector<int>& 
- Time complexity:\nO(N)\n\n- Space complexity:\nO(1)\n\n# Code\n```\nclass Solution {\npublic:\n```\nusing recursion\n```\n\n    int rec(vector<int>& nums1, vector<int>& nums2, int swaps, int i){\n      if(i>=nums1.size()){\n        return 0;\n      }\n      int prev1 = nums1[i-1];\n      int prev2 = nums2[i-1];\n\n      if(swaps){\n        swap(prev1, prev2);\n      }\n\n      // no swap\n      int ans=INT_MAX;\n\n      if(nums1[i]> prev1 && nums2[i]>prev2){\n        ans = rec(nums1, nums2, 0, i+1);\n      }\n\n      //  swap\n\n      if(nums1[i] > prev2 && nums2[i] > prev1){\n        ans = min(ans, 1+rec(nums1, nums2, 1, i+1));\n      }\n\n      return ans;\n\n    }\n```\nrecursion and memoization\n```\n    int recMem(vector<int>& nums1, vector<int>& nums2, int i , int swaps, vector<vector<int>>& dp){\n      if(i==nums1.size()){\n        return 0;\n      }\n      if(dp[i][swaps] != -1) return dp[i][swaps];\n\n      int prev1 = nums1[i-1];\n      int prev2 = nums2[i-1];\n\n      if(swaps) swap(prev1, prev2);\n\n      int ans = INT_MAX;\n\n    // no swap\n      if(nums1[i]> prev1 && nums2[i]>prev2){\n        ans = recMem(nums1, nums2, i+1, 0,  dp);\n      }\n\n      //  swap\n\n      if(nums1[i] > prev2 && nums2[i] > prev1){\n        ans = min(ans, 1+recMem(nums1, nums2, i+1, 1, dp));\n      }\n\n      return dp[i][swaps]=ans;\n\n    }\n```\n using tabulation\n```\n    int table(vector<int>& nums1, vector<int>& nums2){\n\n        int n = nums1.size();\n\n        vector<vector<int>> dp(n+1, vector<int>(2, 0));\n\n        for(int i = n-1;i>=1;i--){\n            for(int j = 1;j>=0;j--){\n\n                int ans = INT_MAX;\n                int prev1 = nums1[i-1];\n                int prev2 = nums2[i-1];\n\n                if(j) swap(prev1, prev2);\n\n                // no swap\n                if(nums1[i]> prev1 && nums2[i]>prev2){\n                    ans = dp[i+1][0];\n                }\n\n                //  swap\n\n                if(nums1[i] > prev2 && nums2[i] > prev1){\n                    ans = min(ans, 1+dp[i+1][1]);\n                }\n\n                dp[i][j]=ans;\n\n            }\n        }\n\n        return dp[1][0];\n    }\n```\nspace optimaization\n\n```\n    int spaceOPT(vector<int>& nums1, vector<int>& nums2){\n\n        int n = nums1.size();\n\n        int swap =0;\n        int noswap =0;\n        int currswap=0;\n        int currnoswap=0;\n\n        for(int i = n-1;i>=1;i--){\n\n            //  for curr swap------------------\n            int ans = INT_MAX;\n            int prev1 = nums1[i-1];\n            int prev2 = nums2[i-1];\n\n            int temp = prev1;\n            prev1 = prev2;\n            prev2 = temp;\n\n            // no swap\n            if(nums1[i]> prev1 && nums2[i]>prev2){\n                ans = min(ans, noswap);\n            }\n\n            //  swap\n\n            if(nums1[i] > prev2 && nums2[i] > prev1){\n                ans = min(ans, 1+swap);\n            }\n            currswap=ans;\n\n            // --------------------------------------\n            // for curr no swap\n            ans = INT_MAX;\n            prev1 = nums1[i-1];\n            prev2 = nums2[i-1];\n\n            // no swap\n            if(nums1[i]> prev1 && nums2[i]>prev2){\n                ans = min(ans, noswap);\n            }\n\n            //  swap\n\n            if(nums1[i] > prev2 && nums2[i] > prev1){\n                ans = min(ans, 1+swap);\n            }\n\n            currnoswap=ans;\n\n            // --------------------------------\n\n            swap = currswap;\n            noswap = currnoswap;\n\n\n        }\n\n        return min(currswap, currnoswap);\n    }\n\n```\nmain function\n```\n    int minSwap(vector<int>& nums1, vector<int>& nums2) {\n\n      nums1.insert(nums1.begin(), -1);\n      nums2.insert(nums2.begin(), -1);\n      int n = nums1.size();\n      // return rec(nums1, nums2, 0, 1);\n\n    //   vector<vector<int>> dp(n, vector<int>(2, -1));\n    //   return recMem(nums1, nums2, 1, 0, dp);\n\n        return spaceOPT(nums1, nums2);\n\n    }\n};\n```
['Array', 'Dynamic Programming', 'Recursion', 'Memoization', 'Queue', 'C++']