PPractick

The problem

A solar-farm planner has a grid map where 1 is usable flat land and 0 is an obstacle, and wants the largest rectangular panel array that sits entirely on usable land. Checking every rectangle is O(R²C²). The trick is to reduce it to the histogram problem: process the grid row by row, and for each column keep the number of consecutive 1s ending at the current row. That array is a histogram whose bars stand on the current row, and the largest rectangle in it is the best rectangle whose bottom edge is this row.

Example: rows 10100 / 10111 / 11111 / 10010 → 6.

Function signature

int maximalRectangle(const vector<string>& matrix);  // characters '0' and '1'

Test cases

Input (rows)	Output	Explanation
10100 / 10111 / 11111 / 10010	6	Rows 2–3, columns 2–4 (0-based)
0	0
1	1
11 / 11	4
101 / 111 / 111	6	The bottom two rows

(Confirm: the rectangle must contain only 1s and be axis-aligned; the matrix may be empty.)

How interviewers phrase it

• "Given a rows x cols binary matrix, find the largest rectangle containing only 1s and return its area" (LeetCode 85).

Clarifying questions to ask

1. Rectangle or square? (Rectangle; the square version is a simple DP.)
2. Is the input chars or ints?
3. How large is the matrix? (Up to 200 × 200.)

Follow-ups to expect

1. "How do you build the histogram for a row?"
2. "Why does this find the optimum?"
3. "What's the complexity?"
4. "What about the largest square?"
5. "Alternative?"

Related questions

• Sum of Subarray Minimums Medium
• Split array - largest sum Hard
• Word Search Hard
• Rat in a Maze Hard
• Implement Min Stack Hard
• Trapping Rainwater Hard

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in