Minimum Domino Rotations For Equal Row

This question is weird. I dislike my solution, but I will post about it anyways because I alksjdaslkjdlaskjd.

Anyways, basically my algo takes the first domino and creates a hashmap using tops[0] and bottoms[0] as keys, where in the [key, value] pair, the value is a pair<int, int> structure with value.first storing the tops count and value.second storing the bottoms count.

It then just iterates through all the dominoes and checks if either keys are present on either side of the domino.

• If one is not present, then the key is erased from the hashmap.
• If one is present, then I increment the side of the value pair corresponding to either the tops side, the bottoms side, or sometimes even both.

Afterwards,

• if the hashmap is empty, we can return -1 since that implies that there does not exist a permutation with a single value present on tops or bottoms.
• if the hashmap is not empty, we can iterate through the remaining keys and calculate the minimum number of flips needed to make the tops or bottoms side all equal; which is just tops.size() - tops_count or tops.size() - bottoms_count

code

class Solution {
public:
    int minDominoRotations(vector<int>& tops, vector<int>& bottoms) {
        unordered_map<int, pair<int, int>> mp;
        ++mp[tops[0]].first;
        ++mp[bottoms[0]].second;
        for (int i = 1; i < tops.size(); ++i) {
            if (mp.size() == 0) break;
            vector<int> erase;
            for (auto& [key, value] : mp) {
                if (key == tops[i] || key == bottoms[i]) {
                    if (key == tops[i]) {
                        ++value.first;
                    }
                    if (key == bottoms[i]) {
                        ++value.second;
                    }
                } else {
                    erase.push_back(key);
                }
            }
            for (int& n : erase) {
                mp.erase(n);
            }
        }
        if (mp.size() == 0) {
            return -1;
        }
        int ans = INT32_MAX;
        for (auto& [key, value] : mp) {
            ans = min(ans, (int)min(tops.size()-value.first, tops.size()-value.second));
        }
        return ans;
    }
};

complexity

• Time: O(n) where n is the size of both tops and bottoms
• Space: O(1)