Minimum number of bricks that can be intersected | Java 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
import java . util . ArrayList ; import java . util . Arrays ; import java . util . HashMap ; public class GFG { static void leastBricks ( ArrayList < ArrayList < Integer > > wall ) { HashMap < Integer , Integer > map = new HashMap < > ( ) ; int res = 0 ; for ( ArrayList < Integer > list : wall ) { int width = 0 ; for ( int i = 0 ; i < list . size ( ) - 1 ; i ++ ) { width += list . get ( i ) ; map . put ( width , map . getOrDefault ( width , 0 ) + 1 ) ; res = Math . max ( res , map . getOrDefault ( width , 0 ) ) ; } } System . out . println ( wall . size ( ) - res ) ; } public static void main ( String [ ] args ) { ArrayList < ArrayList < Integer > > arr = new ArrayList < > ( ) ; arr . add ( new ArrayList < > ( Arrays . asList ( 1 , 2 , 2 , 1 ) ) ) ; arr . add ( new ArrayList < > ( Arrays . asList ( 3 , 1 , 2 ) ) ) ; arr . add ( new ArrayList < > ( Arrays . asList ( 1 , 3 , 2 ) ) ) ; arr . add ( new ArrayList < > ( Arrays . asList ( 2 , 4 ) ) ) ; arr . add ( new ArrayList < > ( Arrays . asList ( 3 , 1 , 2 ) ) ) ; arr . add ( new ArrayList < > ( Arrays . asList ( 1 , 3 , 1 , 1 ) ) ) ; leastBricks ( arr ) ; } }