algoadvance

Leetcode 554. Brick Wall

Problem Statement

You are given a rectangular brick wall that is n bricks high and of varying width. Each brick has the same height, but different widths. The wall is represented as a list of lists, where each inner list represents one row of the wall, and each element in the inner list represents the width of a brick.

You want to find the vertical line that cuts through the fewest number of bricks. This vertical line can only run between the bricks.

Write a function that returns the minimum number of crossed bricks.

Example:

Input:

[[1,2,2,1],
 [3,1,2],
 [1,3,2],
 [2,4],
 [3,1,2],
 [1,3,1,1]]

Output: 2

Explanation:

Clarifying Questions

1. What is the range of the number of rows and the number of bricks in each row?
2. Will each row of the wall have at least one brick?
3. Can we assume that the sum of brick widths in each row is the same?
4. Should we consider the edges of the wall as candidates for a vertical line?

Strategy

1. Data Accumulation: We will utilize a hash map to count the number of times a particular edge (excluding the rightmost edge of the wall) appears.
2. Identify Best Vertical Line: The best place to draw the vertical line will be where the number of edges is the highest, hence cutting through the least number of bricks.

Steps:

1. Create a hash map to store edge counts.
2. Traverse through each row, calculating the cumulative width of bricks. Update the hash map with these values.
3. Determine the maximum count in the hash map, which indicates the vertical line with the fewest crossed bricks.
4. Compute the result by subtracting the maximum edge count from the total number of rows.

Code

#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;

class Solution {
public:
    int leastBricks(vector<vector<int>>& wall) {
        unordered_map<int, int> edgeCount;
        for (const auto& row : wall) {
            int width = 0;
            // We do not consider the rightmost edge of the wall
            for (int i = 0; i < row.size() - 1; ++i) {
                width += row[i];
                edgeCount[width]++;
            }
        }
        
        int maxEdges = 0;
        for (const auto& edge : edgeCount) {
            maxEdges = max(maxEdges, edge.second);
        }
        
        return wall.size() - maxEdges;
    }
};

Time Complexity

• Time Complexity: O(n * m), where n is the number of rows and m is the maximum number of bricks in a row. This complexity arises because we are iterating over each brick, updating our hash map.

• Space Complexity: O(n), where n is the number of unique edges in the wall. In the worst case, every brick forms a unique edge, but typically it will be significantly less than the total number of bricks.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?