Minimum number of bricks that can be intersected | C ++ program for the above approach ; Function to find a line across a wall such that it intersects minimum number of bricks ; Declare a hashmap ; Store the maximum number of brick ending a point on x - axis ; Iterate over all the rows ; Initialize width as 0 ; Iterate over individual bricks ; Add the width of the current brick to the total width ; Increment number of bricks ending at this width position ; Update the variable , res ; Print the answer ; Driver Code ; Given Input ; Function Call
#include <bits/stdc++.h> NEW_LINE using namespace std ; void leastBricks ( vector < vector < int > > wall ) { unordered_map < int , int > map ; int res = 0 ; for ( vector < int > list : wall ) { int width = 0 ; for ( int i = 0 ; i < list . size ( ) - 1 ; i ++ ) { width += list [ i ] ; map [ width ] ++ ; res = max ( res , map [ width ] ) ; } } cout << wall . size ( ) - res ; } int main ( ) { vector < vector < int > > arr { { 1 , 2 , 2 , 1 } , { 3 , 1 , 2 } , { 1 , 3 , 2 } , { 2 , 4 } , { 3 , 1 , 2 } , { 1 , 3 , 1 , 1 } } ; leastBricks ( arr ) ; return 0 ; }