What is the time complexity of Maximal Rectangle?

The optimal solution has a time complexity of O(m*n).

What data structures are used to solve Maximal Rectangle?

This problem uses Array, Dynamic Programming, Stack, Matrix, Monotonic Stack. Understanding these concepts is essential for solving this Hard problem efficiently.

What are the key insights for solving Maximal Rectangle?

Insight 1: The problem can be solved by iterating through each row of the matrix and treating the 'height' of consecutive '1's in each column as a histogram. This transforms the 2D problem into a series of 1D largest rectangle in histogram problems. Insight 2: The largest rectangle in a histogram can be efficiently found using a stack to keep track of increasing heights. The stack helps determine the left and right boundaries of a potential rectangle for each height.

Which companies ask LeetCode 85. Maximal Rectangle in interviews?

This problem is frequently asked at Adobe, Amazon, Apple, Bloomberg, DE Shaw and 10 more companies.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Maximal Rectangle - LeetCode 85 Solution

Q: How to solve Maximal Rectangle?

The solution iterates through each row of the matrix. For each row, it calculates the height of consecutive '1's in each column, essentially forming a histogram. Then, it uses a stack-based approach to find the largest rectangular area in that histogram. The maximum area found across all rows is the final result. The stack stores the indices of bars in increasing order of height. When a smaller height is encountered, the stack is popped to calculate areas until the stack's top has a height less than or equal to the current height.

Maximal Rectangle - Complete Solution Guide

Maximal Rectangle is LeetCode problem 85, a Hard level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

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 matr

Detailed Explanation

The problem asks us to find the largest rectangular area containing only '1's within a given binary matrix (a matrix filled with '0's and '1's). The input is a 2D array (matrix) of characters, and the output is an integer representing the area of the largest rectangle found. The matrix can have different dimensions (rows and columns), and the constraints specify the size limits for rows and columns and that matrix elements are either '0' or '1'.

Solution Approach

The solution iterates through each row of the matrix. For each row, it calculates the height of consecutive '1's in each column, essentially forming a histogram. Then, it uses a stack-based approach to find the largest rectangular area in that histogram. The maximum area found across all rows is the final result. The stack stores the indices of bars in increasing order of height. When a smaller height is encountered, the stack is popped to calculate areas until the stack's top has a height less than or equal to the current height.

Step-by-Step Algorithm

Step 1: Initialize an array `heights` of size `cols + 1` with all values set to 0. This array stores the height of the histogram for each column.
Step 2: Iterate through each row of the matrix.
Step 3: For each row, update the `heights` array. If `matrix[r][c]` is '1', increment `heights[c]`; otherwise, set `heights[c]` to 0.
Step 4: Use a stack to find the largest rectangle in the current histogram (represented by `heights`).
Step 5: Initialize the stack with -1. This acts as a sentinel value to simplify the calculation of the width when the stack becomes empty.
Step 6: Iterate through the `heights` array using index `i`.
Step 7: While the stack is not empty and `heights[stack.peek()]` is greater than `heights[i]`, pop elements from the stack.
Step 8: Calculate the area of the rectangle formed by the popped height. The height is `heights[stack.pop()]` and the width is `i - stack.peek() - 1`.
Step 9: Update `max_area` with the maximum area found so far.
Step 10: Push the current index `i` onto the stack.
Step 11: After iterating through all rows, return the final `max_area`.

Key Insights

Insight 1: The problem can be solved by iterating through each row of the matrix and treating the 'height' of consecutive '1's in each column as a histogram. This transforms the 2D problem into a series of 1D largest rectangle in histogram problems.
Insight 2: The largest rectangle in a histogram can be efficiently found using a stack to keep track of increasing heights. The stack helps determine the left and right boundaries of a potential rectangle for each height.
Insight 3: The matrix contains characters '0' and '1', not integers. We need to ensure we properly handle this during processing.

Complexity Analysis

Time Complexity: O(m*n)

Space Complexity: O(n)

Topics

This problem involves: Array, Dynamic Programming, Stack, Matrix, Monotonic Stack.

Companies

Asked at: Adobe, Amazon, Apple, Bloomberg, DE Shaw, Flipkart, Google, Huawei, Intuit, Meta, Microsoft, Oracle, TikTok, Uber, Yahoo.

Maximal Rectangle | LeetCode 85

Hard

Array Dynamic Programming Stack Matrix Monotonic Stack

Time: O(m*n)Space: O(n)

Solution Code

Available in:

class Solution {
    public int maximalRectangle(char[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return 0;
        }

        int rows = matrix.length;
        int cols = matrix[0].length;
        int[] heights = new int[cols + 1];
        int max_area = 0;

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

            java.util.Stack<Integer> stack = new java.util.Stack<>();
            stack.push(-1);
            for (int i = 0; i < heights.length; i++) {
                while (heights[stack.peek()] > heights[i]) {
                    int height = heights[stack.pop()];
                    int width = i - stack.peek() - 1;
                    max_area = Math.max(max_area, height * width);
                }
                stack.push(i);
            }
        }

        return max_area;
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 85: Maximal Rectangle - Detailed explanation and solution approaches.

Topics

Array Dynamic Programming Stack Matrix Monotonic Stack

Companies

AdobeAmazonAppleBloombergDE ShawFlipkartGoogleHuawei

Stats

Difficulty:Hard

Languages:4

Companies:15

Problem #:85

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

11 steps

1
Step 1: Initialize an array `heights` of size `cols + 1` with all values set to 0. This array stores the height of the histogram for each column.
2
Step 2: Iterate through each row of the matrix.
3
Step 3: For each row, update the `heights` array. If `matrix[r][c]` is '1', increment `heights[c]`; otherwise, set `heights[c]` to 0.
4
Step 4: Use a stack to find the largest rectangle in the current histogram (represented by `heights`).
5
Step 5: Initialize the stack with -1. This acts as a sentinel value to simplify the calculation of the width when the stack becomes empty.
6
Step 6: Iterate through the `heights` array using index `i`.
7
Step 7: While the stack is not empty and `heights[stack.peek()]` is greater than `heights[i]`, pop elements from the stack.
8
Step 8: Calculate the area of the rectangle formed by the popped height. The height is `heights[stack.pop()]` and the width is `i - stack.peek() - 1`.
9
Step 9: Update `max_area` with the maximum area found so far.
10
Step 10: Push the current index `i` onto the stack.
11
Step 11: After iterating through all rows, return the final `max_area`.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(m*n)

💾

Space Complexity

O(n)

📦 Linear space - Memory grows with input size.

📝

Why?

The time complexity is determined by the nested loops iterating through the matrix (m*n). The stack operations within the inner loop are amortized O(n), but since they are within the O(m*n) loop, they do not change the overall time complexity. The space complexity is determined by the auxiliary space used for the `heights` array and the stack.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Brute Force

Iterate through all possible rectangles and check if they contain only 1s. This involves checking all possible top-left and bottom-right corners.

Time: O(m^3 * n^3), where m is the number of rows and n is the number of columns.Space: O(1)

Trade-offs: The brute force approach is very inefficient and should be avoided. It has high time complexity and no significant advantages.

Dynamic Programming

Use DP to build up a table of heights, left boundaries and right boundaries of potential rectangles for each cell. Then, iterate through the table and calculate the maximum rectangular area.

Time: O(m*n)Space: O(m*n)

Trade-offs: While the time complexity is the same as the stack-based solution, it typically requires more space and may be slightly harder to implement due to managing three separate DP tables (heights, left boundaries, right boundaries). It can be useful if you are already familiar with DP principles and wish to avoid using a stack.

✨

Key Insights

1Insight 1: The problem can be solved by iterating through each row of the matrix and treating the 'height' of consecutive '1's in each column as a histogram. This transforms the 2D problem into a series of 1D largest rectangle in histogram problems.
2Insight 2: The largest rectangle in a histogram can be efficiently found using a stack to keep track of increasing heights. The stack helps determine the left and right boundaries of a potential rectangle for each height.
3Insight 3: The matrix contains characters '0' and '1', not integers. We need to ensure we properly handle this during processing.

📚

Key Terms Explained

For Students

Array

A collection of items stored at contiguous memory locations. Like a row of boxes.

Dynamic Programming

Breaking complex problems into smaller subproblems and storing results.

Stack

LIFO structure - Last In, First Out. Like a stack of plates!

Edge Cases

Edge case 1: Empty matrix. The solution correctly handles an empty matrix by returning 0.
Edge case 2: Matrix with all zeros. The solution correctly handles a matrix with all zeros, resulting in a maximal area of 0.
Edge case 3: Matrix with a single '1'. The solution finds the '1' and returns the correct area of 1.
Edge case 4: Matrix with only one row or one column. The stack based approach works correctly with histograms of length 1.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Not handling the case where the matrix is empty, leading to errors.

✗Common mistake 2: Incorrectly calculating the width of the rectangle when using the stack, especially when the stack is empty.

✗Common mistake 3: Forgetting to update the heights array correctly for each row, which leads to inaccurate histogram representations.

✗Common mistake 4: Not resetting heights to 0 at the beginning of each row which will cause the heights array to be incorrect.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Finding the largest free block in memory allocation. The memory can be represented as a matrix where '1' represents a free block and '0' represents an occupied block. Finding the largest rectangle of '1's gives the largest contiguous free memory block.

🏦Real-world scenario 2: Image processing and computer vision. Finding the largest rectangular region of a specific color or feature in an image. For instance, detecting the largest object of a particular color in an image.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

When dealing with arrays, always consider if sorting would simplify the problem. Many array problems have O(n) solutions using hash maps or two-pointer technique.

🎯 Interview Tip

It's okay to not finish hard problems in interviews. Show your problem-solving process.

⚠️ Watch Out

Off-by-one errors are the most common mistake. Double-check your loop bounds and array indices.

👨‍💻 From Experience

I encountered a variation of this problem in a system design interview. The key was recognizing the underlying pattern.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: August 25, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

Don't forget to handle the edge case when the input is empty. Many candidates miss this in interviews.

@DevExpert92Jul 13

The key insight here is recognizing the pattern. Once you see it, the solution becomes straightforward.

@AlgoMasterJul 6

I was asked this exact problem at my Google interview. The interviewer wanted me to optimize space complexity.

@InterviewProJun 29

❓

Frequently Asked Questions

When should I use in-place modification vs creating a new array?

Use in-place modification when space complexity matters (O(1) space requirement) and the original array can be modified. Create a new array when you need to preserve the original data or when the problem involves significant restructuring that would complicate in-place logic.

Should I use top-down (memoization) or bottom-up (tabulation)?

Start with top-down (recursion + memoization) as it directly maps to the recursive thinking and handles only needed subproblems. Convert to bottom-up for better space efficiency and to avoid stack overflow. Bottom-up is often faster due to no recursion overhead.

Is it okay to not fully solve hard problems in interviews?

Yes! Interviewers care more about your problem-solving process than the final answer. Demonstrate: clear communication, systematic approach, ability to recognize when to pivot strategies, and graceful handling of hints. Partial progress with good reasoning is valued.

What is the importance of time and space complexity analysis?

Complexity analysis is crucial because: 1) Interviewers always ask about it, 2) It helps you choose between approaches, 3) It demonstrates CS fundamentals. Always state both time and space complexity, and be prepared to explain how you derived them.

What is the optimal approach for "Maximal Rectangle"?

For this hard-level Array problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether dynamic programming techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?