[554. Brick Wall] C++_Hash Table


  • 0

    Previously, i tried to use vector to store the number of bricks which crosses the interval nodes (n-1 nodes). But it will lead Memory Exceed Limit.

    Try another way: How about if we use hash table to store the end points of each bricks? The node with the largest end points will be the one we choose. Also remember the marginal cases: if all of these bricks have the same length, the result will be the number of vertical edges.

    class Solution {
    public:
    int leastBricks(vector<vector<int>>& wall) {
        if(wall.empty()) return 0;
        unordered_map<int, int> mp;
        int start = 0, m = wall.size();
        for(int i = 0; i < m; ++i){
            start = 0;
            for(int j = 0; j < wall[i].size() - 1; ++j){
                int end = start + wall[i][j];
                mp[end]++;
                start = end;
            }
        }
        pair<int,int> cur(INT_MIN, INT_MIN);
        for(auto e : mp){
            if(e.second > cur.second) cur = e;
        }
        return m - (mp.empty() ? 0 : cur.second);
    }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.