85. Maximal Rectangle

HardStackArrayDynamic ProgrammingMatrixMonotonic Stack
Leetcode Link

Problem Description

This problem involves a binary matrix, which is a grid (rows x cols) containing only 0s and 1s. The objective is to find the largest rectangle, which is composed entirely of 1s, and return the area of that rectangle. To clarify, the area of a rectangle is calculated by multiplying its width by its height.

Intuition

The solution approach capitalizes on a pattern that can be observed by examining the matrix row by row. By treating each row as the base, we can convert the problem into a series of "largest rectangle in histogram" problems.

Here's how it works:

  1. We start with a heights array to keep track of the heights of the 'bars' of 1s above each column at each row. As we move from one row to another, we update the heights: if we see a 1, the height increases by 1; if a 0, the height resets to 0.

  2. With the updated heights array for each row, we determine the area of the largest rectangle that could be formed in the histogram represented by the heights.

  3. For the histogram, we need to identify the limits of expansion for each 'bar' to form the largest rectangle under it. We do this by keeping track of the indices of the previous smaller bar on the left and the next smaller bar on the right for each bar. We use stacks to manage this efficiently as we scan the heights from left to right and then right to left.

  4. Finally, for each height, now knowing how far it can expand to the left and right without encountering a shorter bar, we can calculate the largest rectangle that includes that bar as the highest bar in the rectangle. The maximum such area encountered is kept as the answer.

By performing these steps, we gradually build up and keep track of potential rectangle areas through each row, and by the end, we will have found the largest rectangle possible in the entire matrix.

Learn more about Stack, Dynamic Programming and Monotonic Stack patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece

How does quick sort divide the problem into subproblems?

Solution Approach

The solution to the problem involves two main functions: maximalRectangle and largestRectangleArea.

maximalRectangle Function

The maximalRectangle function employs dynamic programming by scanning through each row of the matrix and updating the heights array where the value at each index represents the height of the rectangle ending at that index. Specifically:

  • It initializes an array heights with a length equal to the number of columns in the matrix. This array stores the height of the 'bars' which contribute to forming the potential rectangles.
  • It iterates through each row in the matrix and for each element:
    • It checks if the element is a 1. If so, it increments the corresponding height in heights by 1 (because we have an additional 'bar' of height 1).
    • If the element is a 0, it resets the corresponding height in heights to 0 (as there's no 'bar' at this column for the current row base).
  • After updating the heights for a row, it calls the largestRectangleArea to compute the largest rectangle that can be formed in the histogram described by heights.
  • It keeps track of the maximum area encountered after processing each row.

largestRectangleArea Function

The largestRectangleArea function calculates the largest rectangle area in a histogram given by heights:

  • It initializes two arrays, left and right, with lengths equal to the number of elements (n) in heights. These arrays store the indices of the next smaller element to the left and right, respectively, for each bar. By default, the left array is filled with -1 and the right array is filled with n.
  • It then uses two passes (left to right and right to left) with a stack stk to figure out for each bar the bounds within which the rectangle with that bar as the tallest can extend:
    • In the left to right pass, it keeps index positions in the stack where the bar heights are in non-decreasing order. When a bar at current index i is shorter than the one at the top of the stack, it means we found a right boundary for the bar at the stack's top. We can then update the right bound for that position and pop the stack. If the stack becomes empty, it means there's no smaller bar to the left.
    • The process is similar in the right to left pass, which updates the left bounds.
  • At the end of these passes, for each bar, we know how far left and right it can extend to form the largest rectangle under it. Using this information, we calculate the maximum possible area for each bar, which is height[i] * (right[i] - left[i] - 1) (since we've found the bounds excluding the current bar).
  • The function finally returns the maximum area found, which the maximalRectangle function uses to determine the largest area in the matrix.

By using the dynamic programming approach with histogram area calculations, this solution helps efficiently solve the problem by breaking it down into a series of subproblems (finding the largest rectangle in a histogram) that build on each other to give the overall answer.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8
1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12
1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

Example Walkthrough

Let's take a small binary matrix to walk through the solution approach:

Suppose we have the following 3x4 binary matrix:

11 0 1 0
21 1 1 1
30 1 1 0

We will apply the maximalRectangle function and break down the process:

Step 1: Initialize the heights array with a length equal to the number of columns (4 in this case).

Step 2: Process the first row [1 0 1 0]. The heights array is now [1 0 1 0].

Step 3: Call largestRectangleArea:

  • The stack initially is empty.
  • Iterating from the left, we keep track of 'left limits,' and at the end, the left array is [-1, -1, -1, -1].
  • Iterating from the right, we keep track of 'right limits,' and the right array is [1, 4, 3, 4].
  • Since the first and third bars are of the same height, the largest area is 1 * (1 - (-1) - 1) = 1 for each.

Step 4: Process the second row [1 1 1 1]. The heights array is updated to [2 1 2 1].

Step 5: Call largestRectangleArea again:

  • The stack will keep track of bars and will find that the 'left limits' are [-1, -1, -1, -1] and 'right limits' are [4, 4, 4, 4].
  • The largest rectangle includes all four bars with smallest height 1, so the area is 1 * (4 - (-1) - 1) = 4.

Step 6: Process the third row [0 1 1 0]. The heights array is now [0 2 3 0].

Step 7: Call largestRectangleArea:

  • The 'left limits' are [-1, -1, 1, -1] and the 'right limits' are [4, 2, 4, 4].
  • The largest rectangle can be formed by the third bar of height 3, with the area being 3 * (4 - (1) - 1) = 6.

In the end, the largest rectangle area found in the matrix is 6, and that is the output of our maximalRectangle function.

By performing each of these steps, we iteratively found the largest rectangle after each row and ended up with the largest rectangle in the entire matrix.

Solution Implementation

1from typing import List
2
3class Solution:
4    def maximalRectangle(self, matrix: List[List[str]]) -> int:
5        # This function finds the maximal rectangle of '1's in a binary matrix.
6      
7        # Initialize the heights array with zeros based on the width of the matrix
8        heights = [0] * len(matrix[0])
9        # Initialize the answer to 0, which will hold the area of the largest rectangle
10        max_area = 0
11      
12        # Iterate through each row in the binary matrix
13        for row in matrix:
14            # Update heights reflecting continuous '1's in a column
15            for col_idx, val in enumerate(row):  # col_idx is the index, val is the value at that position
16                if val == "1":
17                    # Increase the current column's height if the row value is a '1'
18                    heights[col_idx] += 1
19                else:
20                    # Reset the height to 0 if the row value is '0'
21                    heights[col_idx] = 0
22          
23            # Update the max_area with the largest rectangle found in the current histogram of heights
24            max_area = max(max_area, self.largestRectangleArea(heights))
25      
26        # Return the maximal rectangle area found
27        return max_area
28
29    def largestRectangleArea(self, heights: List[int]) -> int:
30        # This function calculates the largest rectangle in a histogram.
31      
32        # Length of the heights list
33        num_heights = len(heights)
34      
35        # Stack to keep track of indices for heights
36        stack = []
37      
38        # Arrays to store indices of previous and next smaller heights
39        prev_smaller = [-1] * num_heights
40        next_smaller = [num_heights] * num_heights
41      
42        # Forward pass to find previous smaller heights
43        for i, height in enumerate(heights):
44            # If the current height is lesser than the height at the stack's top index,
45            # pop the stack until a smaller height is found
46            while stack and heights[stack[-1]] >= height:
47                stack.pop()
48            if stack:
49                prev_smaller[i] = stack[-1]
50            stack.append(i)
51      
52        # Reset stack for next pass
53        stack = []
54      
55        # Backward pass to find next smaller heights
56        for i in range(num_heights - 1, -1, -1):
57            cur_height = heights[i]
58            while stack and heights[stack[-1]] >= cur_height:
59                stack.pop()
60            if stack:
61                next_smaller[i] = stack[-1]
62            stack.append(i)
63      
64        # Calculate the largest rectangle area by finding the maximum area
65        # for each height, considering the distance to the previous and next smaller heights.
66        max_area = max(
67            height * (next_smaller[i] - prev_smaller[i] - 1) for i, height in enumerate(heights)
68        )
69      
70        # Return the maximum area found
71        return max_area
72
1class Solution {
2    public int maximalRectangle(char[][] matrix) {
3      
4        // Get the number of columns in the matrix
5        int numColumns = matrix[0].length;
6      
7        // Create an array to store the heights of '1's in histogram-like form
8        int[] heights = new int[numColumns];
9      
10        // Variable to store the maximum area of rectangle
11        int maxArea = 0;
12      
13        // Iterate over each row of the matrix
14        for (char[] row : matrix) {
15            // Update the heights array to reflect the current row
16            for (int j = 0; j < numColumns; ++j) {
17                // Adjacent '1's in a column are treated as consecutive bar heights in the histogram
18                heights[j] = row[j] == '1' ? heights[j] + 1 : 0;
19            }
20            // Find the largest rectangle in the current histogram
21            maxArea = Math.max(maxArea, largestRectangleArea(heights));
22        }
23      
24        return maxArea;
25    }
26
27    private int largestRectangleArea(int[] heights) {
28        // Variable for the maximum area found
29        int maxArea = 0;
30      
31        // Stack to keep track of the indices of the heights array
32        Deque<Integer> stack = new ArrayDeque<>();
33      
34        // Array to keep track of the left boundary of each bar
35        int[] left = new int[heights.length];
36      
37        // Array to keep track of the right boundary of each bar
38        int[] right = new int[heights.length];
39      
40        // Initialize all right boundaries to point to the end of the heights array
41        Arrays.fill(right, heights.length);
42      
43        // Iterate over the heights array to compute the left and right boundaries for each bar
44        for (int i = 0; i < heights.length; ++i) {
45            // Remove all bars from the stack which are taller than the current bar
46            while (!stack.isEmpty() && heights[stack.peek()] >= heights[i]) {
47                // Set the right boundary for the bar at the top of the stack
48                right[stack.pop()] = i;
49            }
50            // Set the left boundary for the current bar
51            left[i] = stack.isEmpty() ? -1 : stack.peek();
52            // Push the current index onto the stack
53            stack.push(i);
54        }
55      
56        // Compute the area based on the heights and boundaries of each bar
57        for (int i = 0; i < heights.length; ++i) {
58            maxArea = Math.max(maxArea, heights[i] * (right[i] - left[i] - 1));
59        }
60      
61        // Return the maximum area found
62        return maxArea;
63    }
64}
65
1#include <vector>
2#include <stack>
3using namespace std;
4
5class Solution {
6public:
7    // Function to compute the maximal rectangle area in a 2D binary matrix
8    int maximalRectangle(vector<vector<char>>& matrix) {
9        if (matrix.empty() || matrix[0].empty()) return 0;  // handle empty matrix input
10      
11        int num_columns = matrix[0].size();
12        vector<int> heights(num_columns, 0);
13        int max_area = 0;
14
15        // Process each row of the matrix
16        for (auto& row : matrix) {
17            // Update the heights of the histogram representation
18            for (int j = 0; j < num_columns; ++j) {
19                if (row[j] == '1') {
20                    ++heights[j];  // Increase height for continuous '1's
21                } else {
22                    heights[j] = 0;  // Reset height if '0' is encountered
23                }
24            }
25            // Get the max rectangle area in histogram and update max_area
26            max_area = max(max_area, largestRectangleArea(heights));
27        }
28        return max_area;
29    }
30
31    // Helper function to calculate the area of the largest rectangle in a histogram
32    int largestRectangleArea(vector<int>& heights) {
33        int result = 0;
34        int n = heights.size();
35        stack<int> index_stack;
36        vector<int> left(n, -1);
37        vector<int> right(n, n);
38
39        // Calculate the indices of the next smaller element on the left and right
40        for (int i = 0; i < n; ++i) {
41            while (!index_stack.empty() && heights[index_stack.top()] >= heights[i]) {
42                right[index_stack.top()] = i;  // Update right index
43                index_stack.pop();
44            }
45            left[i] = index_stack.empty() ? -1 : index_stack.top();  // Update left index
46            index_stack.push(i);
47        }
48      
49        // Compute the area for each bar considering the range [left, right]
50        for (int i = 0; i < n; ++i) {
51            result = max(result, heights[i] * (right[i] - left[i] - 1));
52        }
53      
54        return result;
55    }
56};
57
1// Assuming that we have the following global declarations
2// of interface and enums to match the C++ types
3interface ICharMatrix extends Array<Array<string>> {}
4
5// Global variable for maximum area, initialized to zero
6let maxArea: number = 0;
7
8// Function to compute the maximal rectangle area in a 2D binary matrix
9function maximalRectangle(matrix: ICharMatrix): number {
10  if (matrix.length === 0 || matrix[0].length === 0) return 0; // handle empty matrix input
11
12  const numColumns: number = matrix[0].length;
13  const heights: number[] = new Array(numColumns).fill(0);
14
15  // Process each row of the matrix
16  for (const row of matrix) {
17    // Update the heights of the histogram representation
18    for (let j = 0; j < numColumns; ++j) {
19      if (row[j] === '1') {
20        ++heights[j]; // Increase height for continuous '1's
21      } else {
22        heights[j] = 0; // Reset height if '0' is encountered
23      }
24    }
25    // Get the max rectangle area in histogram and update maxArea
26    maxArea = Math.max(maxArea, largestRectangleArea(heights));
27  }
28  return maxArea;
29}
30
31// Helper function to calculate the area of the largest rectangle in a histogram
32function largestRectangleArea(heights: number[]): number {
33  let result: number = 0;
34  const n: number = heights.length;
35  const indexStack: number[] = [];
36  const left: number[] = new Array(n).fill(-1);
37  const right: number[] = new Array(n).fill(n);
38
39  // Calculate the indices of the next smaller element on the left and right
40  for (let i = 0; i < n; ++i) {
41    while (indexStack.length !== 0 && heights[indexStack[indexStack.length - 1]] >= heights[i]) {
42      right[indexStack[indexStack.length - 1]] = i; // Update right index
43      indexStack.pop();
44    }
45    left[i] = indexStack.length === 0 ? -1 : indexStack[indexStack.length - 1]; // Update left index
46    indexStack.push(i);
47  }
48
49  // Compute the area for each bar considering the range [left, right]
50  for (let i = 0; i < n; ++i) {
51    result = Math.max(result, heights[i] * (right[i] - left[i] - 1));
52  }
53
54  return result;
55}
56
Not Sure What to Study? Take the 2-min Quiz

Which two pointer techniques do you use to check if a string is a palindrome?

Time and Space Complexity

The code provided has two parts that contribute to the overall computational complexity: the iteration through the matrix to calculate the height of histograms (maximalRectangle function) and the calculation of the largest rectangle in a histogram (largestRectangleArea function).

Time Complexity:

  1. For maximalRectangle: The function iterates through each element in the matrix once. If the matrix size is m * n, where m is the number of rows and n is the number of columns, this part has a time complexity of O(m*n).

  2. For largestRectangleArea within maximalRectangle: For each row, we calculate the largest rectangle area, which involves iterating through the histogram heights twice (once for calculating left limits and once for right limits), both of which are O(n). Then we compute the area for each bar, also in O(n). As this process is repeated for every row m times, the total time complexity for this part is O(m*n).

Thus, the overall time complexity of the code is O(m*n + m*n), which simplifies to O(m*n).

Space Complexity:

  1. The space required for the heights, left, right, and stk in largestRectangleArea is n each, which amounts to 4*n. Since n is the size of the largest dimension (number of columns), the space complexity is O(n).

  2. No additional space proportional to the size of the input matrix is required outside the largestRectangleArea function.

Therefore, the total space complexity of the code is O(n).

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

A person thinks of a number between 1 and 1000. You may ask any number questions to them, provided that the question can be answered with either "yes" or "no".

What is the minimum number of questions you needed to ask so that you are guaranteed to know the number that the person is thinking?

Recommended Readings

Stack Intro

Stack Intro Imagine you have a pile of books on your desk If you want to add a new book you place it on top If you want to read a book you take it from the top And if you simply want to see which book is on the top you

Dynamic Programming Introduction and Patterns

What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution

Monotonic Stack/Queue Intro

Monotonic Stack Deque Intro If you'd prefer a video iframe width 560 height 315 src https www youtube com embed Dq_ObZwTY_Q title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe The word monotonic means a list or a

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA đŸ‘šâ€đŸ«