Simple O(n) C++ solution


  • 0
    T

    We need to keep track of the cut at each point.

    class Solution {
    public:
        int leastBricks(vector<vector<int>>& wall) {
            if (wall.size() == 0) return 0;
            unordered_map<int, int> dp;
            int maxVal = 0;
            int maxwidth = 0;
            for (auto w:wall[0])
                maxwidth+=w;
            for (auto wal:wall){
                int w = 0;
                for (auto width:wal){
                    w+=width;
                    dp[w]++;
                    if ((w!=maxwidth) && (dp[w]>maxVal))
                        maxVal = dp[w];
                }
            }
            
            return wall.size() - maxVal;
        }
    };
    

Log in to reply
 

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