grid47 Exploring patterns and algorithms
Sep 12, 2024
6 min read
Solution to LeetCode 554: Brick Wall Problem
Given a rectangular wall made up of bricks with varying widths, your task is to determine the minimum number of bricks that a vertical line crosses. The line should be drawn such that it does not cross any brick’s edge, and you cannot place the line at the edges of the wall.
Problem
Approach
Steps
Complexity
Input: The input is a 2D array 'wall' where each row represents a row of bricks. Each brick in a row is represented by its width.
• Explanation: The vertical line crossing the edge between the second and third bricks of the first row results in crossing only 2 bricks across all rows.
Approach: The approach involves tracking the positions of the edges of the bricks in each row and counting the frequency of these positions across all rows. The position that occurs most frequently is where the least number of bricks are crossed.
Observations:
• If the vertical line is placed at the edges where the most bricks align, fewer bricks will be crossed.
• We need to avoid crossing any edges of the bricks and aim for positions where the least number of bricks will be affected.
• This can be done efficiently by tracking the frequency of edge positions and selecting the one that minimizes the number of crossed bricks.
Steps:
• Initialize a map to store the frequency of edge positions.
• Iterate through each row and calculate the positions of the brick edges.
• Update the frequency map for each edge position.
• The answer is the number of rows minus the maximum frequency of any edge position.
Empty Inputs:
• The input will never be empty as the number of rows is guaranteed to be at least 1.
Large Inputs:
• The solution should efficiently handle up to 10^4 rows and total brick widths up to 2 * 10^4.
Special Values:
• If the wall has only one column, the vertical line will cross all bricks, and the answer is equal to the number of rows.
Constraints:
• The algorithm should work efficiently within the problem's constraints, particularly with large inputs.
Defines the function `leastBricks`, which takes a 2D vector `wall` representing the brick wall and returns the minimum number of bricks that a vertical line intersects.
2 : Hash Map Initialization
unordered_map<int, int> edge_freq;
Initializes an unordered map `edge_freq` to store the frequency of each edge position encountered while iterating over the wall.
3 : Variable Initialization
int max_freq =0;
Initializes a variable `max_freq` to track the highest frequency of any edge position encountered.
4 : Outer Loop (Row Traversal)
for(int row =0; row < wall.size(); row++) {
Begins a loop to traverse each row of the wall.
5 : Edge Position Initialization
int edge_pos =0;
Initializes `edge_pos` to keep track of the current edge position as we iterate through the bricks in a row.
