Detailed Explanation of The Solution
You have looked at the solution and you are wondering about the logic behind the if conditions, aren\'t you? Well, you are at the right place. I am writing this
You have looked at the solution and you are wondering about the logic behind the if conditions, aren\'t you? Well, you are at the right place. I am writing this post as there are many posts explaining the code but no one seem to clearly explain the logic and the thought process behind it. \n\n```\nint minSwap(vector<int>& A, vector<int>& B) {\n\tint N = A.size();\n\tint not_swap[1000] = {0};\n\tint swap[1000] = {1};\n\tfor (int i = 1; i < N; ++i) {\n\t\tnot_swap[i] = swap[i] = N;\n\t\tif (A[i - 1] < A[i] && B[i - 1] < B[i]) {\n\t\t\tswap[i] = swap[i - 1] + 1;\n\t\t\tnot_swap[i] = not_swap[i - 1];\n\t\t}\n\t\tif (A[i - 1] < B[i] && B[i - 1] < A[i]) {\n\t\t\tswap[i] = min(swap[i], not_swap[i - 1] + 1);\n\t\t\tnot_swap[i] = min(not_swap[i], swap[i - 1]);\n\t\t}\n\t}\n\treturn min(swap[N - 1], not_swap[N - 1]);\n}\n```\n\nCode Author: @Lee215\n\nHave a look at the problem statement once again:\n\n*Given A and B, return the minimum number of swaps to make both sequences strictly increasing.  **It is guaranteed that the given input always makes it possible.***\n\nThe statement in bold is essential in understanding the logic behind the if conditions in the code. Let me explain why:\n\n```\nif (A[i - 1] < A[i] && B[i - 1] < B[i]) {\n\t\t\tswap[i] = swap[i - 1] + 1;\n\t\t\tnot_swap[i] = not_swap[i - 1];\n\t\t}\n```\n\nThe first if condition is relatively easy and straightforward to understand. It simply means that if there is a situation where A[i - 1] < A[i] && B[i - 1] < B[i] you either swap both A[i] and A[i-1] with B[i] and B[i-1] respectively or do not swap at all. \n\nNow, lets look at the second condition and this one is a bit tricky: \n```\nif (A[i - 1] < B[i] && B[i - 1] < A[i]) {\n\t\t\tswap[i] = min(swap[i], not_swap[i - 1] + 1);\n\t\t\tnot_swap[i] = min(not_swap[i], swap[i - 1]);\n\t\t}\n```\n\nThe reason behind why we have formed this condition ( A[i - 1] < B[i] && B[i - 1] < A[i] ) is because of the fact that the inputs provided are such that it is possible to make the array increasing by swapping A[i] with B[i]. This condition is essential to understand because it eliminates the case which makes it impossible to have swaping of elements resulting in the formation increasing array.\n\n ```\n A = [a1, a2] \n B = [b1, b2]\n```\n\nSay, if a1>b2 and b1>a2 and a1>a2 and b1>b2:\n\nAn example of such case would be:\n\n```\nA = [10, 5]\nB = [6, 3]\n```\n\nThis is an invalid test case to this problem as it is strictly decreasing and follows  a1>b2 and b1>a2 which blocks the possibility of making the sequece increasing by swapping any one of those. \n\nTherefore, the only cases where it is possible to make the sequence increasing is when for any i, either it is already strictly increasing ( *A[i - 1] < A[i] && B[i - 1] < B[i]* ) where we can swap both or do not swap both or if it is possible to get the order correct by a single swap ( *A[i - 1] < B[i] && B[i - 1] < A[i]* ) \n\nI hope this helps. If you still need help, feel free to comment. \n\n\n\n\n
[]