Asteroid Collision

Problem Link: Leetcode

• Asteroid Collision
  • Problem Statement
  • Hints
    • Approach
  • Solution

Problem Statement

Given a rows x cols binary matrix filled with 0's and 1's, find the largest rectangle containing only 1's and return its area.

Example 1:

Input: matrix = [
    ["1","0","1","0","0"],
    ["1","0","1","1","1"],
    ["1","1","1","1","1"],
    ["1","0","0","1","0"]
]
Output: 6
Explanation: The maximal rectangle is shown in the above picture.

Example 2:

Input: matrix = [["0"]]
Output: 0

Example 3:

Input: matrix = [["1"]]
Output: 1

Constraints:

• rows == matrix.length
• cols == matrix[i].length
• 1 <= row, cols <= 200
• matrix[i][j] is '0' or '1'.

Hints

Approach

1. Prepare the array of heights

We walk through each column and update the value of each cell with the continuous number of cells having '1' before and including the cell.

So for the following input:

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

We can get a 2-D array heights as:

1 0 1 0 0
2 0 2 1 1
3 1 3 2 2
4 0 0 3 0

The code to build the heights is as follows:

for (int i = 0; i < c; i++) {
    int height = 0;
    for (int j = 0; j < r; j++) {
        if (matrix[j][i] == '1') {
            height++;
        } else {
            height = 0;
        }
        heights[j][i] = height;
    }
}

2. Find the maximum area for each row

For each row in heights, we can start with each cell and travel to the right as long as there is possible height. While traversing the row, we can calculate the area of the range at each step, which is dictated by the minimum height in the range.

We keep updating the maximum height at each step.

Code for this step is as follows:

int maxArea = 0;

for (int i = 0; i < r; i++) {
    for (int j = 0; j < c; j++) { // to give a starting min height
        int minHeight = heights[i][j];
        int l = j;
        while (l < c && heights[i][l]) {
            minHeight = min(minHeight, heights[i][l]);
            maxArea = max(maxArea, minHeight * (l - j + 1));
            l++;
        }
    }
}

The above step is of order O(M*N*N) in time complexity which is the overall time complexity of the solution.

We can optimize this by using a stack which is explained below.

Solution

Complete solution using Stack

class Solution {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        int n = matrix[0].size();
        vector<int> heights(n + 1);
        int maxArea = 0;
        
        for (auto row : matrix) {
            for (int i = 0; i < n; i++) {
                heights[i] = row[i] == '1' ? heights[i] + 1 : 0;
            }
            
            stack<int> st;
            st.push(-1);
            for (int i = 0; i < n + 1; i++) {
                while (st.top() != -1 && heights[i] < heights[st.top()]) {
                    int h = heights[st.top()];
                    st.pop();
                    int w = i - st.top() - 1;
                    maxArea = max(maxArea, h * w);
                }
                st.push(i);
            }
        }
        
        return maxArea;        
    }
};

Note how the heights array is updated incrementally for each row. Also note that heights array is N+1 in size, having 0 at the end.

In this solution, at each step, we keep pushing indexes for each number.

And at each step, if the current number is smaller than the top element, we calculate the area upto that index and remove that index from the stack.

Why does this work?

Since we always have a 0 at the end, we can process all segments.