Maximal Rectangle

The given problem is to find the largest rectangle containing only 1’s in a given binary matrix. This problem can be solved by using the Largest Rectangle in Histogram technique by converting each row of the matrix into a histogram of 1’s.

Here’s the code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

class Solution:
    def maximalRectangle(self, matrix: List[List[str]]) -> int:
        if not matrix:
            return 0

        def largestRectangleArea(heights: List[int]) -> int:
            stack = []
            max_area = 0
            heights.append(0)  # Adding sentinel value to handle remaining bars

            for i, h in enumerate(heights):
                while stack and heights[stack[-1]] > h:
                    height = heights[stack.pop()]
                    width = i if not stack else i - stack[-1] - 1
                    max_area = max(max_area, height * width)
                stack.append(i)

            return max_area

        rows, cols = len(matrix), len(matrix[0])
        max_area = 0

        # Convert rows to histograms and find the largest rectangle area
        for r in range(rows):
            if r > 0:
                for c in range(cols):
                    matrix[r][c] = str(int(matrix[r][c]) + int(matrix[r - 1][c])) if matrix[r][c] == "1" else "0"
            heights = [int(h) for h in matrix[r]]
            max_area = max(max_area, largestRectangleArea(heights))

        return max_area

The code defines a helper function largestRectangleArea that calculates the area of the largest rectangle in a histogram using a monotonic stack. The outer function maximalRectangle converts each row of the binary matrix into a histogram of 1’s and invokes the helper function to calculate the area for each row, returning the maximum of these areas.

The given code takes into account the constraints of the problem and provides the correct result for the given input matrix.

Identifying Problem Isomorphism

“Maximal Rectangle” can be approximately mapped to “Maximal Square”.

Reasoning:

Both require you to determine the maximum area of a rectangle (or square, which is a special case of a rectangle) given a 2D matrix.

In “Maximal Rectangle”, you are given a 2D binary matrix filled with 0’s and 1’s, and your task is to find the largest rectangle containing only 1’s and return its area.

In “Maximal Square”, you are also given a 2D binary matrix filled with 0’s and 1’s, but your task is to find the largest square containing only 1’s and return its area.

The mapping between these problems is straightforward: a square is a special case of a rectangle where all sides have the same length. Therefore, any approach you might use to solve the “Maximal Rectangle” problem could potentially be applied to the “Maximal Square” problem as well, with modifications to account for the square-specific constraints.

The mapping is approximate because although they share similarities in the problem structure (finding the maximum area), the actual problem conditions and objectives are different. “Maximal Rectangle” requires finding a rectangle that may have different lengths for height and width, while the “Maximal Square” requires finding a square with the same height and width.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution:
    def maximalRectangle(self, matrix: List[List[str]]) -> int:
        if not matrix:
            return 0

        n = len(matrix[0])
        heights = [0] * (n + 1)
        max_area = 0

        for row in matrix:
            for i in range(n):
                heights[i] = heights[i] + 1 if row[i] == "1" else 0

            stack = [-1]
            for i in range(n + 1):
                while heights[i] < 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

Problem Classification

This involves finding the largest rectangular area, but in a 2D grid of ones and zeros. It’s an example of Area Optimization.

Language Agnostic Coding Drills

  1. Concept: List and List of Lists

    • Drill: Write a function that creates a list and appends a few elements to it. Write another function that creates a list of lists (matrix) and prints each row. Understand how indexing works with list of lists.

  2. Concept: Conditional Statements

    • Drill: Write a function that takes an integer as input, and prints whether it’s even or odd.

  3. Concept: Loops

    • Drill: Write a function that iterates over a list of integers and prints each number. Now modify the function to iterate over a list of lists and prints each inner list.

  4. Concept: Stack Data Structure

    • Drill: Implement a Stack class with ‘push’ and ‘pop’ methods. Test it by pushing a few items onto the stack, popping an item off the stack, and printing the remaining stack.

  5. Concept: Finding the Maximum Value

    • Drill: Write a function that finds the maximum value in a list of integers.

In the given problem solution:

  • The matrix is iterated over row by row.
  • For each row, the “height” of the rectangle that can be made at each point is calculated.
  • The height is reset to 0 if the current cell in the matrix is 0 (or “0” in this case).
  • A stack is used to keep track of the indices of the heights. The stack is maintained in increasing order of heights.
  • For each height, if it is smaller than the height at the top of the stack, we know we’ve encountered a potential maximum rectangle.
  • In such a case, we calculate the area of the potential rectangle and update the max_area if the calculated area is larger.
  • In the end, the largest area of the rectangle is returned.

Targeted Drills in Python

  1. Concept: List and List of Lists

    • Drill:
     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

    # Function to create a list and append elements
def create_list():
    my_list = []
    for i in range(5):
        my_list.append(i)
    print(my_list)

# Function to create a list of lists and print each row
def create_matrix():
    matrix = [[j for j in range(5)] for i in range(5)]
    for row in matrix:
        print(row)

  2. Concept: Conditional Statements

    • Drill:
    1
2
3
4
5
6

    # Function to check if a number is even or odd
def check_even_odd(num):
    if num % 2 == 0:
        print(f"{num} is even")
    else:
        print(f"{num} is odd")

  3. Concept: Loops

    • Drill:
    1
2
3
4
5
6
7
8
9

    # Function to print each number in a list
def print_list(numbers):
    for num in numbers:
        print(num)

# Function to print each row in a matrix
def print_matrix(matrix):
    for row in matrix:
        print(row)

  4. Concept: Stack Data Structure

    • Drill:
     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

    # Stack class
class Stack:
    def __init__(self):
        self.stack = []

    def push(self, item):
        self.stack.append(item)

    def pop(self):
        if len(self.stack) < 1:
            return None
        return self.stack.pop()

    def display(self):
        print(self.stack)

  5. Concept: Finding the Maximum Value

    • Drill:
    1
2
3
4
5
6
7

    # Function to find the maximum number in a list
def find_max(numbers):
    max_num = numbers[0]
    for num in numbers:
        if num > max_num:
            max_num = num
    print(max_num)

The drills here are general. For problem specific drills, it would be good to work with:

  • 2D grid traversal
  • Updating elements in a 2D grid based on conditions
  • Working with stacks in the context of a 2D grid. For example, push an item when a condition is met in the grid, pop when another condition is met, etc.
  • Calculating areas using height and width and updating maximum area.