Skip to content

554. Brick Wall 👍

  • Time: $O(n)$, where $n = |\text{bricks}|$
  • Space: 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
 public:
  int leastBricks(vector<vector<int>>& wall) {
    int maxCount = 0;
    unordered_map<int, int> count;

    for (const vector<int>& row : wall) {
      int prefix = 0;
      for (int i = 0; i < row.size() - 1; ++i) {
        prefix += row[i];
        maxCount = max(maxCount, ++count[prefix]);
      }
    }

    return wall.size() - maxCount;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
  public int leastBricks(List<List<Integer>> wall) {
    int maxFreq = 0;
    Map<Integer, Integer> count = new HashMap<>();

    for (List<Integer> row : wall) {
      int prefix = 0;
      for (int i = 0; i < row.size() - 1; ++i) {
        prefix += row.get(i);
        maxFreq = Math.max(maxFreq, count.merge(prefix, 1, Integer::sum));
      }
    }

    return wall.size() - maxFreq;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
  def leastBricks(self, wall: list[list[int]]) -> int:
    maxFreq = 0
    count = collections.defaultdict(int)

    for row in wall:
      prefix = 0
      for i in range(len(row) - 1):
        prefix += row[i]
        count[prefix] += 1
        maxFreq = max(maxFreq, count[prefix])

    return len(wall) - maxFreq