You are given a 2D grid of integers. Write a function to find the "battle ship" with the…
- User
You are given a 2D grid of integers. Write a function to find the "battle ship" with the largest area. A battleship is a rectangle of
1s. Please this is the "Maximal Rectangle" problem, write a function that solves this problem, and explain how this problem can be reduced to the "Largest Rectangle in Histogram" problem for each row. - Assistant
We are given a 2D grid of integers (presumably 0s and 1s). We need to find the largest rectangle (area) consisting entirely of 1s. This is the classic "Maximal Rectangle" problem.
Common solution: For each row, we can treat it as the base of a histogram where the height of each column is the number of consecutive 1s ending at that row (i.e., if grid[i][j] is 1, then height[j] = height[j] + 1; else height[j] = 0). Then for each row, we compute the largest rectangle in that histogram (which is a well-known problem solvable in O(n) per row). The overall complexity is O(rows * cols).
Explanation of reduction: For each row i, we define an array heights[0..n-1] where heights[j] = number of consecutive 1s in column j from the top until row i (including row i). That is, if grid[i][j] == 1, then heights[j] = (if i==0 then 1 else heights_prev[j] + 1) else 0. Then, any rectangle of 1s that ends at row i (i.e., having bottom edge at row i) corresponds to a rectangle in the histogram where the bars are the heights. Specifically, for a rectangle of 1s with width w and height h (where h <= the heights in the chosen columns), it corresponds to a rectangle in the histogram of height h and width w (spanning w consecutive columns with heights at least h). Conversely, any rectangle in the histogram corresponds to a rectangle of 1s in the grid that ends at row i and has area = h * w. So by computing the largest rectangle in the histogram for each row, we get the maximal rectangle ending at that row. The overall maximum is the answer.
We need to write a function that returns the maximal rectangle area.
Let's define the function:
def maximalRectangle(grid: List[List[int]]) -> int:
We'll assume grid is a list of lists of integers, with values 0 or 1.
Steps:
- If grid is empty, return 0.
- Let m = number of rows, n = number of columns.
- Initialize an array heights of length n with zeros.
- max_area = 0.
- For each row i in range(m):
- For each column j in range(n): if grid[i][j] == 1: heights[j] += 1 else: heights[j] = 0
- Compute largest rectangle area in histogram heights.
- Update max_area.
- Return max_area.
Now we need a helper function to compute largest rectangle in histogram. That's also a classic: using a stack to track indices with increasing heights. Algorithm: Append a zero at the end to flush stack. Initialize stack with -1. For each index i from 0 to len(heights): while stack top is not -1 and heights[i] < heights[stack[-1]]: h = heights[stack.pop()] w = i - stack[-1] - 1 area = h * w update max. push i onto stack.
Alternatively, we can use a more standard approach.
We'll implement that.
Now, the explanation: We need to explain how the problem reduces to the largest rectangle in histogram for each row. That is, as described above.
Let's structure the answer:
- Brief description of the problem.
- Explanation of the reduction: For each row, compute consecutive 1s heights, then each rectangle ending at that row corresponds to a rectangle in the histogram. So solving for each row and taking maximum yields the answer.
- Code implementation.
- Complexity analysis.
I'll produce a detailed response.
Note: The user said "Please this is the 'Maximal Rectangle' problem, write a function that solves this problem, and explain how this problem can be reduced to the 'Largest Rectangle in Histogram' problem for each row." So they want the explanation and code.
Let's write the code accordingly.
Potential edge cases: empty grid, grid with no 1s.
We'll use type hints.
Implementation:
def maximalRectangle(matrix: List[List[int]]) -> int: if not matrix or not matrix[0]: return 0 m, n = len(matrix), len(matrix[0]) heights = [0] * n max_area = 0 for i in range(m): for j in range(n): if matrix[i][j] == 1: heights[j] += 1 else: heights[j] = 0 # Compute largest rectangle in histogram for heights max_area = max(max_area, largestRectangleArea(heights)) return max_area
We need to define largestRectangleArea.
def largestRectangleArea(heights: List[int]) -> int: stack = [-1] # stack of indices, start with -1 sentinel max_area = 0 # Append a zero at the end to ensure all bars get popped for i, h in enumerate(heights + [0]): while stack[-1] != -1 and h < heights[stack[-1]]: height = heights[stack.pop()] width = i - stack[-1] - 1 max_area = max(max_area, height * width) stack.append(i) return max_area
But careful: when we append 0, we need to treat heights[stack[-1]] when stack[-1] is the index in the original heights. Since we appended a zero, we need to handle that the last element is not part of original heights? Actually, in the loop we are iterating over heights + [0], so the indices for original heights are 0..n-1, and the appended zero is at index n. But when we access heights[stack[-1]], if stack[-1] is n (the last appended index), that would be out of range. However, we never push the appended zero onto the stack? Actually we do: in the for loop, we push i at each iteration, including when i = n (the appended zero). But then when we later pop, we might be popping an index that is n, but then we access heights[stack[-1]]? That would cause index error because heights only has indices 0..n-1. So we need to adjust: either we use a separate array that includes the appended zero, or we handle differently.
Common approach: Instead of modifying heights, we can loop i from 0 to n (inclusive) and when i == n, we treat current height as 0. But we still need to have the heights array for indices 0..n-1. Then when we compute width, we use i and stack[-1] which are indices within the extended range. But when we pop an index j (which is from 0..n-1) and compute height = heights[j], that's fine. So we should not push the index n onto the stack? Actually we do push it, but then we will never use it as a bar because when we later pop, we will only pop indices that have been pushed before, and when we compute height = heights[stack.pop()], if stack.pop() returns n, that would be out of range. So we must avoid pushing the sentinel zero? Actually, many implementations do:
stack = [] for i in range(len(heights)+1): cur = heights[i] if i < len(heights) else 0 while stack and cur < heights[stack[-1]]: h = heights[stack.pop()] w = i if not stack else i - stack[-1] - 1 ... stack.append(i)
But then when i == len(heights), we push i (which is len(heights)) onto the stack. Then later, if we never pop it? Actually, after the loop, we don't need to pop it because it's sentinel. It won't cause error because we only access heights[stack[-1]] when we are inside the while condition. But when we are at i = len(heights)+1? No, the loop ends. So the last element (i = n) is pushed, but then the loop ends. That's okay because we never use it to compute height. But if we later have another iteration? No. So it's safe. However, if we push n, then stack[-1] becomes n. But then the condition "cur < heights[stack[-1]]" would try to access heights[n] which is out of bounds. But at i = n, cur = 0, and we are inside the loop. While condition: stack is not empty, and cur (0) < heights[stack[-1]]. If stack[-1] is n? That happened only if we pushed n in a previous iteration? But we push n at the end of the iteration for i=n. But at the beginning of iteration i=n, stack might contain indices from previous rows. So we need to check: at i=n, we set cur=0. Then we check while stack and cur < heights[stack[-1]]: but stack[-1] is some index j from 0 to n-1. That's fine. After popping all bars that are >0, we then push i (n). So at the end of the iteration for i=n, stack = [n] if we popped everything? Or maybe stack has some indices if heights were non-decreasing? But then after pushing n, the loop ends. So we never access heights[stack[-1]] after that? That's fine. But what about the next iteration? There is none. So safe.
But there is a subtlety: when we compute width, we do: w = i if not stack else i - stack[-1] - 1. After popping the top, stack might become empty? Then we set w = i. That's correct.
So the common implementation is:
def largestRectangleArea(heights): stack = [] max_area = 0 for i in range(len(heights)+1): cur = heights[i] if i < len(heights) else 0 while stack and cur < heights[stack[-1]]: h = heights[stack.pop()] w = i if not stack else i - stack[-1] - 1 max_area = max(max_area, h*w) stack.append(i) return max_area
That works.
Alternatively, we can use the sentinel -1 at the start to simplify the width calculation: stack = [-1] initially. Then for i in range(len(heights)+1): cur = ...; while stack[-1] != -1 and cur < heights[stack[-1]]: ...; stack.append(i). But then when we pop, we have stack[-1] which is always not -1? Actually, after popping, stack[-1] might be -1, then width = i - (-1) - 1 = i. That works. But careful: we must not access heights[-1] because stack[-1] might be -1 in the condition? The condition is: while stack[-1] != -1 and cur < heights[stack[-1]]: So if stack[-1] is -1, we break. So that's safe. And when we compute width: after popping, stack[-1] is the new top, which could be -1. Then width = i - stack[-1] - 1. That gives i - (-1) - 1 = i. That's correct. But we need to ensure that we don't use heights[-1]. So that's safe.
We'll use the sentinel version because it's common.
Let's implement:
def largestRectangleArea(heights: List[int]) -> int: stack = [-1] # stack of indices max_area = 0 for i in range(len(heights) + 1): cur_height = heights[i] if i < len(heights) else 0 while stack[-1] != -1 and cur_height < heights[stack[-1]]: h = heights[stack.pop()] w = i - stack[-1] - 1 max_area = max(max_area, h * w) stack.append(i) return max_area
That should work.
Now, test with a simple example.
Example: grid = [[1,0,1,0,0], [1,0,1,1,1], [1,1,1,1,1], [1,0,0,1,0]] The maximal rectangle area is 6.
Let's simulate: Row0: heights = [1,0,1,0,0] -> largest rectangle in histogram: max area? heights: 1,0,1,0,0. Using algorithm:
- stack = [-1] i=0: cur=1, stack[-1]=-1 so push 0. stack=[-1,0] i=1: cur=0, while stack[-1]!=-1 and 0<heights[0]=1: pop 0 -> h=1, w=1 - (-1)-1=1, area=1. max=1. Then push 1. stack=[-1,1] i=2: cur=1, stack[-1]=1, heights[1]=0, 1>=0 so push2. stack=[-1,1,2] i=3: cur=0, while: stack[-1]=2, heights[2]=1>0 -> pop2: h=1, w=3 - stack-1-1=1, area=1. max still1. Now stack[-1]=1, heights[1]=0, 0>=0? Actually condition: cur<heights[stack[-1]]? 0<0 false. So push3. stack=[-1,1,3] i=4: cur=0, while: stack[-1]=3, heights[3]=0, 0<0 false. push4. stack=[-1,1,3,4] i=5: cur=0 (extra), while: stack[-1]=4, heights[4]=0? Actually heights[4] exists? heights has indices 0..4. heights[4]=0. 0<0 false. push5. Then finish. So max=1. That seems low. But actually there is a rectangle of area 2? No, row0: only single 1s. So max=1 is correct.
Row1: update heights: for each col: if grid[1][j]==1 then heights[j]++ else 0. grid[1] = [1,0,1,1,1] heights becomes: [2,0,2,1,1] because: col0: 1 -> 1+1=2? Actually previous row0 heights: [1,0,1,0,0]. So: j0: grid[1][0]=1 -> 1+1=2 j1: 0 -> 0 j2: 1 -> 1+1=2 j3: 1 -> 0+1=1 j4: 1 -> 0+1=1 So heights = [2,0,2,1,1] Largest rectangle in histogram: Compute:
- stack = [-1] i0: cur=2, push0 -> [-1,0] i1: cur=0, pop0: h=2, w=1-(-1)-1=1, area=2. max=2. push1 -> [-1,1] i2: cur=2, stack[-1]=1, heights[1]=0, 2>=0 push2 -> [-1,1,2] i3: cur=1, while stack[-1]=2, heights[2]=2 >1: pop2: h=2, w=3 - stack-1-1=1, area=2. max=2. Then stack[-1]=1, heights[1]=0, 1>=0? condition: 1<0 false. push3 -> [-1,1,3] i4: cur=1, stack[-1]=3, heights[3]=1, 1<1 false. push4 -> [-1,1,3,4] i5: cur=0, while: stack[-1]=4, heights[4]=1>0: pop4: h=1, w=5 - stack-1-1=1, area=1. max=2. Then stack[-1]=3, heights[3]=1>0: pop3: h=1, w=5 - stack-1-1=3, area=3. max=3. Then stack[-1]=1, heights[1]=0, 0<0 false. push5 -> [-1,1,5]. But then finish. So max=3. But there is a rectangle of 2x2? Actually heights: [2,0,2,1,1]. The largest rectangle is of area 3? Let's see: columns 2,3,4 have heights 2,1,1. The largest rectangle that can be formed: if we take height 1 over columns 2,3,4 -> width=3, area=3. Or height 2 only at column2 -> area2. So max=3. But in the grid, the rectangle of 1s: at rows 1-2? Actually row1 and row2? Row1: columns 2,3,4 are 1; row2: columns 2,3,4 are also 1? Row2: [1,1,1,1,1] so columns 2,3,4 are 1. That gives a 2x3 rectangle? But wait, row1 column2 is 1, row1 column3 is 1, row1 column4 is 1; row2 column2 is 1, row2 column3 is 1, row2 column4 is 1. That is a 2x3 rectangle of 1s. But the heights at row1 are [2,0,2,1,1]. For column2, height=2 means consecutive 1s from row0 and row1? But row0 column2 is 1, so yes height=2. For column3, height=1 means only row1 (because row0 column3 is 0). For column4, height=1 similarly. So if we consider a rectangle ending at row1 (bottom at row1), the maximum height we can have over columns 2,3,4 is limited by the minimum height among them, which is 1. So the rectangle of height 2 over columns 2,3,4 is not possible because column3 and 4 only have height 1. So the rectangle of 2x3 would extend to row2, but that is not ending at row1. At row1, we only consider rectangles that end at row1. The rectangle of 2x3 ends at row2, so we will catch it at row2. So at row1, the largest rectangle ending at row1 is indeed 3 (1x3). That's consistent.
Row2: grid[2] = [1,1,1,1,1]. Heights become: col0: 2+1=3? Actually previous heights: [2,0,2,1,1]. Now: j0: grid[2][0]=1 -> 2+1=3 j1: grid[2][1]=1 -> 0+1=1 j2: 1 -> 2+1=3 j3: 1 -> 1+1=2 j4: 1 -> 1+1=2 So heights = [3,1,3,2,2] Largest rectangle in histogram: We compute: i0: cur=3, stack=[-1,0] i1: cur=1, pop0: h=3, w=1-(-1)-1=1, area=3. max=3. push1 -> [-1,1] i2: cur=3, push2 -> [-1,1,2] i3: cur=2, pop2: h=3, w=3-1-1=1, area=3. max=3. Now stack[-1]=1, heights[1]=1, 2>=1? condition: 2<1 false. push3 -> [-1,1,3] i4: cur=2, stack[-1]=3, heights[3]=2, 2<2 false, push4 -> [-1,1,3,4] i5: cur=0, pop4: h=2, w=5-3-1=1, area=2. max=3. pop3: h=2, w=5-1-1=3, area=6. max=6. pop1: h=1, w=5-(-1)-1=5, area=5. max=6. push5. So max=6. That's the answer.
Row3: grid[3] = [1,0,0,1,0]. Heights become: col0: 3+1=4? Actually grid[3][0]=1 -> 3+1=4? But wait, row2 heights: [3,1,3,2,2]. Now: j0: 1 -> 3+1=4? But careful: if grid[3][0]=1, then heights[0] = previous heights[0] + 1 = 3+1=4. j1: 0 -> 0 j2: 0 -> 0 j3: 1 -> 2+1=3? Actually previous heights[3]=2, so 2+1=3. j4: 0 -> 0 So heights = [4,0,0,3,0] Largest rectangle: i0: cur=4, push0. i1: cur=0, pop0: h=4, w=1-(-1)-1=1, area=4. max=4. push1. i2: cur=0, stack[-1]=1, heights[1]=0, 0<0 false, push2. i3: cur=3, push3. i4: cur=0, pop3: h=3, w=4-2-1=1? Actually after popping 3, stack top is 2, so w=4-2-1=1, area=3. max=4. pop2: h=0? Actually heights[2]=0, but condition: cur<heights[stack[-1]]? When we pop 3, then stack[-1] becomes 2, heights[2]=0, and cur=0, 0<0 false, so stop. Then push4. i5: cur=0, pop4: h=0? Actually we push index4? At i=4, we pushed 4. Then at i=5, we have cur=0, stack[-1]=4, heights[4]=0, 0<0 false, so we push5. But we also might have other pops? Actually after i=4, stack = [-1,1,2,4]? Let's trace carefully.
Better to compute systematically:
heights = [4,0,0,3,0] stack = [-1] i=0: cur=4, push -> [-1,0] i=1: cur=0, while stack[-1]!=-1 and 0<heights[0]=4: pop0 -> h=4, w=1-(-1)-1=1, area=4. stack=[-1]. Then push1 -> [-1,1] i=2: cur=0, while: stack[-1]=1, heights[1]=0, 0<0 false. push2 -> [-1,1,2] i=3: cur=3, while: stack[-1]=2, heights[2]=0, 3<0 false. push3 -> [-1,1,2,3] i=4: cur=0, while: stack[-1]=3, heights[3]=3>0: pop3 -> h=3, w=4 - stack-1-1 = 4-2-1=1, area=3. max remains4. Then stack[-1]=2, heights[2]=0, 0<0 false. push4 -> [-1,1,2,4] i=5: cur=0, while: stack[-1]=4, heights[4]=0, 0<0 false. push5 -> [-1,1,2,4,5] end. So max=4.
So overall max = max(1,3,6,4) = 6.
Thus algorithm works.
Now, we need to write the function accordingly.
Also note: the input grid might be given as a list of lists of integers, but sometimes it's given as characters? The problem says "grid of integers", so we assume 0/1 integers.
We'll write the code accordingly.
Now, the explanation: We'll describe step by step.
We'll also mention that the reduction works because for each row, we compute the histogram of consecutive 1s heights, and then any rectangle of 1s that has its bottom edge on that row corresponds exactly to a rectangle in that histogram. So the largest rectangle overall must have its bottom edge on some row, so we consider all rows.
We'll also note that the histogram problem can be solved in O(n) time using a monotonic stack.
Complexity: O(m*n) time, O(n) space.
We'll produce the final answer.
I'll structure the answer:
- Explanation of reduction.
- Algorithm steps.
- Code implementation (with comments).
- Complexity analysis.
Let's write.
Solution Explanation
We are given a 2D grid
gridof sizem x ncontaining only0s and1s.
A battleship is any axis-aligned rectangle consisting entirely of1s.
Our goal is to find the maximum area (number of cells) of such a rectangle.
1. Reduction to "Largest Rectangle in Histogram"
For each row
iwe can treat the columns as a histogram:- Define
height[j]= number of consecutive1s ending at rowiin columnj.- If
grid[i][j] == 1thenheight[j] = height[j] + 1(from previous row). - Otherwise
height[j] = 0.
- If
Any rectangle of
1s whose bottom edge lies on rowicorresponds exactly to a rectangle in this histogram:- The rectangle's width is the number of consecutive columns it spans.
- Its height is the minimum
heightamong those columns. - The area is
width × height.
Conversely, any rectangle found in the histogram corresponds to a rectangle of
1s in the original grid ending at rowi.Thus, if we compute the largest rectangle in a histogram for every row's
heightarray, the overall maximum area among all rows is the answer to the maximal rectangle problem.
2. Algorithm
- Initialize
heightarray of lengthnwith zeros. - For each row
ifrom0tom-1:- Update
height:- If
grid[i][j] == 1→height[j] += 1 - Else →
height[j] = 0
- If
- Compute
max_area_row = largestRectangleArea(height)using a monotonic stack. - Update the global
max_area.
- Update
- Return
max_area.
Largest Rectangle in Histogram (O(n) stack solution):
- Append a sentinel
0to the end ofheightto ensure all bars are popped. - Maintain a stack of indices with increasing bar heights.
- For each index
i(including the sentinel):- While the current height is less than the height of the bar at the stack top:
- Pop the top index
top. - Compute height
h = height[top]. - Width
w = i - stack[-1] - 1(distance between current index and new stack top). - Area
h * wupdates the maximum.
- Pop the top index
- Push
ionto the stack.
- While the current height is less than the height of the bar at the stack top:
3. Correctness Proof
We prove that the algorithm returns the area of the largest all-
1rectangle.Lemma 1: For any row
i, the arrayheightcorrectly stores the number of consecutive1s ending at rowifor each column.Proof: By induction.
- Base: row
0,height[j] = 1ifgrid[0][j]==1else0. Correct. - Inductive step: assuming
heightis correct for rowi-1, for rowiwe either increment (ifgrid[i][j]==1) or reset to0. This exactly counts consecutive1s ending at rowi. ∎
Lemma 2: Any rectangle of
1s with bottom edge at rowicorresponds to a rectangle in the histogramheight(and vice versa).Proof:
Consider a rectangleRwith columns[l, r]and bottom rowi.
For every columnjin[l, r], the rectangle's height cannot exceed the number of consecutive1s ending at rowi, i.e.,height[j]. SinceRconsists entirely of1s, its height must be ≤height[j]for alljin[l, r]. Conversely, if we take any contiguous subarray ofheightwith minimum valueh, we can form a rectangle of heighthand width equal to the subarray length, which corresponds exactly to a rectangle of1s ending at rowi. ∎Lemma 3: For a fixed row
i,largestRectangleArea(height)returns the maximum area of any rectangle of1s whose bottom edge is rowi.Proof: By Lemma 2, such rectangles are in one-to-one correspondence with rectangles in the histogram
height. The stack algorithm for the histogram problem is known to compute the maximum rectangle area correctly (it considers every bar as the limiting height of a maximal width). Hence it returns the maximum area among all rectangles ending at rowi. ∎Theorem: The algorithm returns the area of the largest all-
1rectangle in the grid.Proof: Let
A*be the area of the largest battleship. Consider the rectangle achievingA*; let its bottom row bei*. By Lemma 3, when processing rowi*the algorithm computes an area at leastA*(since it considers all rectangles ending ati*). Thusmax_area ≥ A*. On the other hand, any rectangle considered by the algorithm corresponds to an actual rectangle of1s (by Lemma 2), somax_areacannot exceedA*. Thereforemax_area = A*. ∎
4. Complexity Analysis
- Time: We process each of the
mrows and for each row updateheightin O(n) and compute the histogram maximum in O(n). Total:O(m * n). - Space: The
heightarray usesO(n)and the stack usesO(n)auxiliary space. So overallO(n)extra space.
Reference Implementation (Python)
from typing import List def maximalRectangle(matrix: List[List[int]]) -> int: """ Returns the area of the largest rectangle containing only 1's in a binary matrix. """ if not matrix or not matrix[0]: return 0 m, n = len(matrix), len(matrix[0]) height = [0] * n max_area = 0 for i in range(m): # Update the histogram heights for row i for j in range(n): if matrix[i][j] == 1: height[j] += 1 else: height[j] = 0 # Compute largest rectangle in current histogram max_area = max(max_area, _largestRectangleArea(height)) return max_area def _largestRectangleArea(heights: List[int]) -> int: """ Helper: Largest rectangle area in a histogram (O(n) stack solution). """ stack = [-1] # sentinel index max_area = 0 for i in range(len(heights) + 1): # Current height: 0 for the extra sentinel at the end cur_height = heights[i] if i < len(heights) else 0 # Pop while current height is less than stack top's height while stack[-1] != -1 and cur_height < heights[stack[-1]]: h = heights[stack.pop()] # height of the bar w = i - stack[-1] - 1 # width with that height max_area = max(max_area, h * w) stack.append(i) return max_areaExample Usage:
grid = [ [1, 0, 1, 0, 0], [1, 0, 1, 1, 1], [1, 1, 1, 1, 1], [1, 0, 0, 1, 0] ] print(maximalRectangle(grid)) # Output: 6The function correctly returns
6, corresponding to the2×3rectangle of1s in rows 2–3 and columns 2–4 (0-indexed).