Two approaches very intuitive WITH THOROUGH EXPLANATION in C++ O(N)
Hello guys! \n     When you read this question probably the first thing which came to your mind is to use a greedy approach. One of the approaches is getting th
Hello guys! \n     When you read this question probably the first thing which came to your mind is to use a greedy approach. One of the approaches is getting the most frequent element from A, B and try to find the minimum number of swaps transferring from A to B and vice-versa. However, it\'s possible that there is a result which involves not the most frequent element. But this is an interview, it is definitely better to have a working solution even though it is not the most optimal. Therefore, let\'s try to find the solution for all frequent elements and find the minimum number of swaps among them. \n\n**1**\nHere is the code in C++ which works in superlinear time, i.e. **O(nlogn)**\n```c++\nclass Solution {\npublic:    \n    int minDominoRotations(vector<int>& A, vector<int>& B) {\n        int result = min(getMinimum(A, B, getMostFrequentDominoes(A)),\n                         getMinimum(B, A, getMostFrequentDominoes(B)));\n        return (result == INT_MAX) ? -1 : result;\n    }\nprivate:\n    int getMinimum(const vector<int>& A, const vector<int>& B, const vector<pair<int, int> >& freq) {\n        int result = INT_MAX;    \n        for (const auto& it : freq) {\n            auto mainDomino = it.second;\n            int swaps = 0;\n            for (int i = 0; i < B.size(); ++i) {\n                if (B[i] == mainDomino && A[i] != mainDomino) {\n                    swaps++;\n                } else if (A[i] != mainDomino) {\n                    swaps = INT_MAX;\n                    break;\n                }\n            }\n            result = min(result, swaps);\n        }\n        return result;\n    }\n    \n    vector<pair<int, int> > getMostFrequentDominoes(const vector<int>& dominoes) {\n        vector<int> counter(7, 0);\n        vector<pair<int, int> > freq;\n        for (const auto& domino : dominoes) counter[domino]++;\n        for (int i = 1; i <= 6; ++i) freq.push_back({counter[i], i});\n        sort(rbegin(freq), rend(freq));\n        return freq;\n    }\n};\n```\n**2**\nWe have finished coding it in around 15-20 minutes and it\'s time to optimize it! From the description of the problem we should look closer to the details: \n\t* *The dominoes are in range from 1 to 6*\n\t* *It does not matter whether we transform from A to B or from B to A, the main point is that the number of swaps must be minimum*\n\nWhat about if we try to find the result from left to right for all dominoes in range [1,6]? Then, get the minimum number of swaps for each variation and get the minimum among all of them. It works and the time complexity is O(cn) where c is the number of domino variation.\nTherefore, we do not need any additional space and the time complexity is linear! **O(n)**\n\n```c++\nclass Solution {\npublic:\n    int minDominoRotations(vector<int>& A, vector<int>& B) {\n        int result = INT_MAX;\n        for (int domino = 1; domino <= 6; ++domino) {\n            bool flag = true;\n            int top = 0, bottom = 0;\n            for (int i = 0; i < A.size(); ++i) {\n                if (!(A[i] == domino || B[i] == domino)) {\n                    flag = false;\n                    break;\n                }\n                if (A[i] == domino && B[i] != domino) top++;\n                else if (B[i] == domino && A[i] != domino) bottom++;\n            }\n            if (flag) result = min(result, min(bottom, top));\n        }\n        return (result == INT_MAX) ? -1 : result;\n    }\n};\n```\n\t \nThanks, \nLeetcodeKZ
['Greedy']