[Java/Python 3] one pass counting, O(A + B) w/ brief explanation and analysis.
Count the frequency of each number in A and B, respectively; \n2. Count the frequency of A[i] if A[i] == B[i];\n3. If countA[i] + countB[i] - same[i] == A.lengt
1. Count the frequency of each number in A and B, respectively; \n2. Count the frequency of A[i] if A[i] == B[i];\n3. If countA[i] + countB[i] - same[i] == A.length, we find a solution; otherwise, return -1;\n4. min(countA[i], countB[i]) - same[i] is the answer. `countA[i] + countB[i] - same[i]` is like finding the union of two set `A` and set `B` <=> `A + B - (A & B)` -- credit to **@StarInTheNight**\n\n\n```\nclass Solution {\n    public int minDominoRotations(int[] A, int[] B) {\n        if (A.length != B.length) { return -1; }\n        int[] countA = new int[7]; // countA[i] records the occurrence of i in A.\n        int[] countB = new int[7]; // countB[i] records the occurrence of i in B.\n        int[] same = new int[7]; // same[k] records the occurrence of k, where k == A[i] == B[i].\n        for (int i = 0; i < A.length; ++i) {\n            ++countA[A[i]];\n            ++countB[B[i]];\n            if (A[i] == B[i]) { ++same[A[i]]; }\n        }\n        for (int i = 1; i < 7; ++i) {\n            if (countA[i] + countB[i] - same[i] == A.length) {\n                return Math.min(countA[i], countB[i]) - same[i];\n            }\n        }\n        return -1;\n    }\n}\n```\n```\nfrom collections import Counter\n\nclass Solution:\n    def minDominoRotations(self, A: List[int], B: List[int]) -> int:\n        if len(A) != len(B): return -1\n        same, countA, countB = Counter(), Counter(A), Counter(B)\n        for a, b in zip(A, B):\n            if a == b:\n                same[a] += 1\n        for i in range(1, 7):\n            if countA[i] + countB[i] - same[i] == len(A):\n                return min(countA[i], countB[i]) - same[i]        \n        return -1\n```\n\n**Analysis:**\n\nTime: O(A + B), space: O(1).\n\n----\n\n\n**Q & A:**\n\n**Q1**: How do you know that `min(countA[i], countB[i]) - same[i]` is the smallest number?\n**A1**: `countA[i] + countB[i] - same[i]` is like finding the union of two set `A` and set `B` <=> `A + B - (A & B)`. We have only 2 options of minimum rotations to make all `A` and `B` are respectively same:\nrotate\n1. `countA[i] - same[i]`;\n2. `countB[i] - same[i]`;\nObviously, we should choose the smaller one: `min(countA[i] - same[i], countB[i] - same[i])`, which is `min(countA[i], countB[i]) - same[i]`.\n\n**Q2**: The following code:\n```\n        for i in range(1, 7):\n            if countA[i] + countB[i] - same[i] == len(A):\n                return min(countA[i], countB[i]) - same[i]  \n```\nmeans that when we found i = `p` that satisfy countA[p] + countB[p] - same[p] == len(A) then we use `p` to find the min(countA[p], countB[p]) - same[p]. But how about another i = `q` that satisfy countA[q] + countB[q] - same[q] == len(A)? Could it be smaller than the value corresponding to `p`?\n\n**A2**: There are 2 cases, if \n1.) for all 1 <= i <= 6, same[i] == 0, then \ncountA[p] + countB[p] == len(A),\nSince \nsum(countA) + sum(countB) = 2 * len(A),\nit is possible that there exists `q` such that \n`q != p` and countA[q] + countB[q] == len(A), in which case,\ncountA[p] == countB[q] and countA[q] == countB[p]\nTherefore, min(countA[p], countB[p]) == min(CountA[q], countB[q])\n\n2.) same[p] > 0, \n=> countA[p] + countB[p] > len(A), \n=> for any i != p, countA[i] + countB[i] - same[i] < countA[i] + countB[i] < len(A)\nTherefore, \nmin(countA[p], countB[p]) - same[p] is the only option.\n\n**Q3:** Doesn\'t using Counter make the space complexity O(N) ?\n`same, countA, countB = Counter(), Counter(A), Counter(B)`\n\nAnd Time complexity O(A) since you checked the sizes here:\n`if len(A) != len(B): return -1`\n**A3:** It\'s actually `O(1)` space. There are at most `3 X 7 = 21` int used in Java code; and similarly in Py 3. Also, `len()` cost time `O(1)`.\n**End of Q & A**\n
[]