Search⌘ K
AI Features
Home
Courses
Grokking the Coding Interview Patterns

Smallest Rectangle Enclosing Black Pixels

Explore how to determine the smallest axis-aligned rectangle enclosing all connected black pixels in a binary matrix. Understand the problem constraints and develop an efficient algorithm with runtime below O(m × n). This lesson enhances your skills in matrix operations and algorithmic problem solving.

We'll cover the following...

Statement

You are given an m×nm \times n binary matrix image, where 00 represents a white pixel and 11 represents a black pixel.

All black pixels in the matrix form a single connected region, where connectivity is defined by horizontal or vertical adjacency.

Given two integers x and y that represent the coordinates of one of the black pixels, write an algorithm to find the area of the smallest axis-aligned rectangle that encloses all the black ...