99.51 % Faster Runtime ✅✅ || Recursive + Memoization || Easy to Understand
Recursively go to every index and check possibility for swapping\n Describe your first thoughts on how to solve this problem. \n\n# Approach : \n> 1.) If we are
# Recursively go to every index and check possibility for swapping\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach : \n> 1.) If we are at index Zero we can either swap it or not because zero does not have any previous index \n2.) Calculate previous index\'s value for both the vectors and store them in some variables ( prevP and prevQ in my code )\n3.) If it is possible to either swap or not then try out both the possibilities \n4.) If it is mandatory to swap then swap it\n5.) else no need to swap\n<!-- Describe your approach to solving the problem. -->\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```\nint dp[100010][2]; \n// [100010]   -> to keep track of current index \n// [2]        -> to check last index swapped or not \n\nint rec(vector<int> &p,vector<int> &q,int idx,bool prev)\n{\n    if(idx==p.size()) return 0;\n    int ans = 1e6; // some big number \n    \n    if(dp[idx][prev] != -1) return dp[idx][prev]; // memoization\n    \n    int prevP , prevQ; // previous element for both p and q vectors\n    if(idx!=0)\n    {\n        if(prev) // it means previous index was swapped \n        {\n            prevP = q[idx-1];\n            prevQ = p[idx-1];\n        }else \n        {\n            prevP = p[idx-1];\n            prevQ = q[idx-1];\n        }\n    }\n\n    if(idx!=0) // returning big number for cases where nothing can be done \n    {\n        if( (prevP >= p[idx] || prevQ >= q[idx] ) && (prevQ >= p[idx] || prevP >= q[idx]) ) return 1e6;\n    }\n\n\n    if(idx==0)\n    {\n        ans = min(ans,rec(p,q,idx+1,false)); // No Swap\n        ans = min(ans,1+rec(p,q,idx+1,true)); // Swap\n    }else\n    {\n        if( (prevP < p[idx] && prevQ < q[idx]) && (prevQ < p[idx] && prevP < q[idx]) )   \n        {\n            // IF we swap or not this idx does not have any problem So\n            ans = min(ans,rec(p,q,idx+1,false));  // No Swap\n            ans = min(ans,1+rec(p,q,idx+1,true)); // Swap\n        }else if(  prevP >= p[idx] || prevQ >= q[idx] )\n        {\n            // Swap is must \n            ans = min(ans,1+rec(p,q,idx+1,true)); // Swap \n        } else \n        {\n            // No need to swap \n            ans = min(ans,rec(p,q,idx+1,false));\n        }\n    }\n\n    return dp[idx][prev] = ans;\n}\n\n\n\n\nclass Solution {\npublic:\n    int minSwap(vector<int>& p, vector<int>& q) \n    {\n        ios_base::sync_with_stdio(false); cin.tie(NULL);\n        memset(dp,-1,sizeof(dp));\n        return rec(p,q,0,false);   \n    }\n};\n```
['Dynamic Programming', 'Recursion', 'Memoization', 'C++']