class Solution {
 public:
  int leastBricks(vector<vector<int>>& wall) {
    int maxCount = 0;
    unordered_map<int, int> count;

    for (const auto& 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;
  }
};

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);
        count.put(prefix, count.getOrDefault(prefix, 0) + 1);
        maxFreq = Math.max(maxFreq, count.get(prefix));
      }
    }

    return wall.size() - maxFreq;
  }
}

class Solution:
  def leastBricks(self, wall: List[List[int]]) -> int:
    maxFreq = 0
    count = 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