![image](https://assets.leetcode.com/users/images/d55b627a-2d87-4f09-b064-310a8bce0377_1602342798.4437773.png)\n\n***Intuition:-***\nThe above wall is represented in a 2D Array where each element is the **size** of the respective brick :\n[[1,2,2,1],\n[3,1,2],\n[1,3,2],\n[2,4],\n[3,1,2],\n[1,3,1,1]]\n\nNote : Size of each brick is at least 1 unit.\n\nSo to mininize the number of bricks crossed by line, we want the line to pass through as many edges as possible.\nFor this approach the edge postion will be defined with respect to the leftmost edge.\n![image](https://assets.leetcode.com/users/images/af224f0c-e14b-4117-829c-a6f509c0c519_1602344960.0595038.png)\n\nIn the above picture, the leftmost edge is conscidered to be at *0th* postion. Hence the optimal line crosses from the edge "**4**".\n\nBut how do we figure out that the line which passes from the edge 4 is optimal ?\nWe can do that by storing each brick\'s edge & looking out for common edges through which the line can pass.\n\n![image](https://assets.leetcode.com/users/images/c6f4f639-b41e-4f6f-a678-0ff8be3b9755_1602346638.7041118.png)\n\nAny edge position can be calculated by the sum of the lenghts of bricks observed till that edge.\nLike in the above diagram :\nEdge Position = Length of 1st Brick + Length of 2nd Brick\n=> Edge Position = 1 + 2\n=> Edge Position = 3\n\nNOTE: ***You cannot draw a line just along one of the two vertical edges of the wall, in which case the line will obviously cross no bricks.***\nBecause of this note we won\'t consider the ***edge 0*** & ***edge 6*** to solve the question.\n![image](https://assets.leetcode.com/users/images/db68928a-3baf-4d67-baad-7410dcb8307e_1602358144.364781.png)\n\nOne interesting observation is that for calculating next edge position, we don\'t have to start adding the lengths from the very first brick of the row. Instead, we can add the "Sum of lengths of bricks obervered till the previous edge" + current brick\'s length.\nSo,\nNext Edge Position = (Sum of lengths of bricks observered till the previous edge) + Current Brick\'s Length.\n=> **Next Edge Position = Previous Edge Position + Current Brick\'s Length**\n![image](https://assets.leetcode.com/users/images/ff66fbe5-5aaa-44a0-9867-443658e561e5_1602409975.487065.png)\n\n\nUsing the same logic, we can calculate every edge\'s position in the wall\n![image](https://assets.leetcode.com/users/images/df791514-be1d-496e-8897-b86e8b9ddb6b_1602357507.7656312.png)\n\n**The edge which happens to be in multiple rows will contribute to the optimal solution as the line passing through that common edge will result in minimun crossing/cutting of bricks.**\nHence we wanna find the edge that has higest frequency in the wall.\n\nNow comes an important question, which data structure should we use and why?\n**Suggestion :**\n*How about using a data-structure that stores the 2-dimentional grid information via which we can access any position\'s info (whether its a brick or an edge) in a constant time?*\n**Analysis of Suggestion :** \n*The problem of using a 2D grid is that we will be storing the edge\'s positions as well as the brick\'s positions. So we are wasting space in storing all the brick\'s coordinates.*\n**Optimizing the Suggestion :**\n*So if we look into our requirement, we are only concerned with the pair of "position of the edge" & "its frequency in the wall". We don\'t care about the brick\'s position. HashMap seems like a perfect data structure to store the pair*\n\nHence we will store every calculated edge in a HashMap.\nStructure of the HashMap :\n**Key of HashMap = Edge Position**\n**Value of HashMap = Frequency of Edge in the Entire Wall**\n![image](https://assets.leetcode.com/users/images/ab772be9-7be0-4985-8d01-7515dd73d1c7_1619437012.802769.png)\n\n![image](https://assets.leetcode.com/users/images/0f0a4a61-2c4a-4ff4-9aaa-21099ceef28a_1623125674.4072828.png)\n![image](https://assets.leetcode.com/users/images/eb868c19-89fb-49a8-b3b4-804743ff6197_1623125744.9454632.png)\n![image](https://assets.leetcode.com/users/images/5bf89742-bbe7-4c36-98dd-f0771771c46d_1623125755.2961688.png)\n![image](https://assets.leetcode.com/users/images/b1481576-6511-47de-b440-0be449843699_1623125761.956156.png)\n![image](https://assets.leetcode.com/users/images/4a5fa365-9048-4543-85c2-526a6f8bbf04_1623125769.1751635.png)\n\n![image](https://assets.leetcode.com/users/images/67578355-6f58-458a-9f8f-c8ec72eb4099_1619437107.3954344.png)\n\nFrom the hashmap we can clearly see that **edge 4** is the edge having maximum frequency.\n![image](https://assets.leetcode.com/users/images/9584ee2a-e268-41e3-ac34-7e2bfca8de0b_1602359532.5487833.png)\n\nNow we are sure that the line passing from edge 4 will result in minimum crossing of bricks.\nBut we need to return the number of crossing the line makes.\nIn the above diagram,\n*Red Box = Line passing through an edge*\n*Blue Box = Line crossing through a brick*\n\nHence a fomulae can be derived:\nNumber of Blue Boxes+ Number of Red Boxes = Number of Rows in Wall\n=> Number of Blue Boxes + (Frequency of Most Occuring Edge) = Number of Rows in Wall\n=> (Number of Bricks Crossed by Line) + (Frequency of Most Occuring Edge) = Number of Rows in Wall\n=> (Number of Bricks Crossed by Line) = Number of Rows in Wall - (Frequency of Most Occuring Edge)\n\n***Number of Bricks Crossed by Line* = *Number of Rows in Wall* - *Frequency of Most Occuring Edge***\n\nHence\nNumber of Bricks Crossed by Line = Number of Rows in Wall - Frequency of Most Occuring Edge\n=> Number of Bricks Crossed by Line = 6 - 4\n=> Number of Bricks Crossed by Line = **2** (We return this answer)\n\nBelow is the **C++** Code of the above mentioned logic:\n\n```\nclass Solution {\npublic:\n int leastBricks(vector>& wall) \n {\n unordered_map edge_frequency; //HashMap to store the number of common edges among the rows\n int max_frequency = 0; //Variable to store the frequency of most occuring edge\n \n for(int row=0; row> wall) \n {\n HashMap edge_frequency = new HashMap<>(); //HashMap to store the number of common edges among the rows\n int max_frequency = 0; //Variable to store the frequency of most occuring edge\n \n for(int row=0; row return "wall.size() - 0"\n=> return "3 - 0"\nThat is "3" is returned as the answer.\n\n**Edge Case 2 : wall = [ [1,1,1,1], [1,1,1,1], [1,1,1,1], [1,1,1,1] ]**\n**Expected Output : 0**\n![image](https://assets.leetcode.com/users/images/4f211db3-9e6e-4127-b520-33dc5c83afb9_1602368154.9120328.png)\nJust like the previous edge case, we can\'t cross the walls via *red* lines (i.e. We can\'t cross via the leftmost & the rightmost edge).\nIn this case, we do find some edges (Enrciled in yellow/purple/brown boxes), hence we don\'t need to cut through the bricks like we did in the previous edge case. Note that the occurence of each edge is equal to the number of rows. (Its visible in the hashmap)\nBut since there are multiple maximum frequency present in the hashmap (Three 4s), hence we can select any one of the edges.\nWhich gives us 3 possible lines to draw (blue lines in the diagram)\nSo "edge frequency = number of rows" means that there exists an edge that is aligned in each row from top to bottom such that the line can pass without cutting any brick. Hence the number of bricks cutted is 0. (Clearly visible in the diagram)\nIn our code, the maximum frequency will be setted to "4" (Which is retrived via hashmap)\nHence we\nreturn "wall.size() - max_frequency"\n=> return "wall.size() - 4"\n=> return "4 - 4"\nThat is "0" is returned as the answer.\n\n****************************************** THE END ******************************************\n\n**Doubt (by @astroash):**\nI think that the space complexity will be O(mn) and not O(m). You mentioned "the space complexity would be equal to the maximum number of edges possible in the wall". In the worst case (staggered arrangement of bricks), this value will be equal to the total number of bricks in the wall which is mn. You assumed that this value will be equal to the maximum number of bricks in a single row, but all the bricks might account for a new edge distance too.\n\n**Clarification of space complexity analysis confusion:**\n\tI understand your confusion. Let me elaborate on the same. The worst-case scenario (staggered arrangement of bricks) is covered in **Edge Case 2**. (Picture Link: https://assets.leetcode.com/users/images/4f211db3-9e6e-4127-b520-33dc5c83afb9_1602368154.9120328.png)\n\n**1st Doubt:** "*You assumed that this value will be equal to the maximum number of bricks in a single row*"\n**My Response:** As per your understanding, I\'m assuming that space complexity will be equal to the maximum number of bricks in a SINGLE row. That is incorrect, I\'m looking for DIFFERENT TYPES of edges in the ENTIRE wall. So doesn\'t matter which row I look into.\n\n**2nd Doubt:** "*but all the bricks might account for a new edge distance too.*"\n**My Response:** Does it really account for a new edge distance? And only because the bricks are in a different row?\n\nImagine every row in the wall has an edge distance of 1 unit only. And total rows are 3.\n\t\t1) So the hashmap will have an entry as <(1,3)>. Meaning the ENTIRE wall has only an edge distance of 1 and that occurred 3 times. Now Add a 4th row, with an edge distance of 1 in it.\n\t\t2) Hashmap will now look something like <(1,4)>. Meaning the ENTIRE wall has only an edge distance of 1 and that occurred 4 times. Now Add a 5th row, with an edge distance of 2 in it.\n\t\t3) Hashmap will now look something like <(1,4), (2,1)>. Meaning the ENTIRE wall has an edge distance of 1 that occurred 4 times & an edge distance of 2 that occurred 1 time.\n\nSo what increased the size of the hashmap? Adding the 4th row or the 5th row? \n5th row, right? It was because the 5th row came along with a NEW edge distance that resulted in a new key-value pair in the hashmap.\n\nNow coming back to your question, "won\'t the same edge in a different row account for a new edge distance?"\nLook at what happened when you added the 4th row in the example, the hashmap went from <(1,3)> to <(1,4)>. The edge in the new row was the same as that in all the other rows. Because of which the value of an EXISTING pair in the hashmap changed from 3 to 4 and no new pair was added to the hashmap.\n\nSo m * n will result in counting the same edge multiple times and that is not the actual size of the hashmap. The size of the hashmap is determined by the number of different key-value pairs in it. The MAGNITUDE of the value has NOTHING to do with the space complexity. I hope this answers your question.

Brick Wall

Problem Description

Problem Description

Answer Panel