DP and not greedy explaination
Thoughts\n\n- Greedy is not the solution, why?\n\t- First thought came of greedy, i.e. iterate over all the indices (A and B same), then wherever condition brea
***Thoughts***\n\n- ***Greedy is not the solution, why?***\n\t- First thought came of greedy, i.e. iterate over all the indices (A and B same), then wherever condition breaks, swap it, do moves++ and move further\n\t- But in the above approach, whenever condition fails, we are swapping current index elements, we could also have swapped previous index elements, which could have given us the best answer.\n\t- Consider the example :\n\t\t\t-  1, 7, 8, 9\n\t\t\t-  6, 2, 3, 4\n\t-  In the above example, if we do greedy, then we would end up swapping 2, 3, 4, thus 3 moves, but answer is 1 move\n\t- But now, thought comes, what if we calculate moves using greedy, and return min(moves, n - moves)\n\t- But there is problem with this approach, consider the array is divided into 3 sections, Left, middle and right section.\n\t- Left section has problem, we calculate moves in left as leftMoves, similarly for right as rightMoves, and say middle section is perfect, strictly increasing.\n\t- Now we cannot do min (leftMoves+rightMoves, n - (leftMoves+rightMoves))\n\t- Because second part in minimum says, swap middle part also, which is not required, we should have just done min in leftPart + min in rightPart\n\t- Thus, this question cannot be solved using greedy\n\n\n- ***Recursion (or Dynamic Programming)***\n\t- Now we know that whenever condition breaks, we could have either swapped previous one or current one.\n\t- But if we swapped previous one, it could have broken the previous part of array\n\t- So for each index, we will calculate 2 answers, min swaps required till now, if current one is not swapped and min swaps requried till now, if current one is swapped.\n\t- This way, current both answers can be used to caclulate next both answers\n\t- But in this approach, calculate answers, if possible, i.e. it could be possible to swap only, not leave the arrays as it is (without swapping), as may not lead to strictly increasing arrays\n\t- Moreover, we will not use DP of space N, since current both answers just depend upon previous 2 answers, thus 4 variables will solve the problem\n\t- Otherwise, we could have required 2D array for DP = new int[N][2]\n\t- Time : O(N), Space : O(1)\n\n***Solution***\n\n```\nclass Solution {\n    public int minSwap(int[] A, int[] B) {\n        if (A == null || A.length == 0) return 0;\n        int len = A.length;\n        int prevNonSwap = 0, prevSwap = 1, currSwap = len, currNonSwap = len;\n        for (int idx = 1; idx < len; idx++) {\n            if ((A[idx] > A[idx-1]) && (B[idx] > B[idx-1])) {\n                currNonSwap = prevNonSwap;\n                currSwap = prevSwap+1;\n            }\n            if ((A[idx] > B[idx-1]) && (B[idx] > A[idx-1])) {\n                currNonSwap = Math.min(currNonSwap, prevSwap);\n                currSwap = Math.min(currSwap, prevNonSwap+1);\n            }\n            prevSwap = currSwap;\n            prevNonSwap = currNonSwap;\n            currSwap = len;\n            currNonSwap = len;\n        }\n        return Math.min(prevSwap, prevNonSwap);\n    }\n}\n```
[]