Q50 Brick Wall - LeetCode
Mon Jan 30 2023 14:29:14 GMT+0000 (Coordinated Universal Time)
Saved by
@Ayush_dabas07
class Solution {
public int leastBricks(List<List<Integer>> wall) {
//make a frequency map of number of splits against index
//whichever index will have maximum split against it , crossing a line
//from that index will cut minimum no. of bricks
//minimum no. bricks = maximum no. of splits in wall
//make prefix sum as we are just given the width and we need index
HashMap<Integer,Integer> map = new HashMap<>();
int ans = 0 ;
for(int i = 0 ; i < wall.size(); i++){
List<Integer> col = wall.get(i);
int psum = 0; //prefix sum
//prefix sum will start from 0 after completing every coloumn
for(int j = 0 ; j < col.size();j++){
psum += col.get(j);
//put split against the index,do not consider last wall
if(j != col.size()-1)
map.put(psum,map.getOrDefault(psum,0)+1);
}
}
//iterate through the hashmap and store the index with maximum split
//max can also be found while updating frequency
for(int idx : map.keySet())
ans = Math.max(ans,map.get(idx));
//ans = total bricks - max gaps
//if ans stays 0 that means all bricks are same size
return wall.size() - ans;
}
}
content_copyCOPY
https://leetcode.com/problems/brick-wall/
Comments