Smallest Rectangle Enclosing Black Pixels

Smallest Rectangle Enclosing Black Pixels - Problem

You are given an m x n binary matrix image where 0 represents a white pixel and 1 represents a black pixel.

The black pixels are connected (i.e., there is only one black region). Pixels are connected horizontally and vertically.

Given two integers x and y that represent the location of one of the black pixels, return the area of the smallest (axis-aligned) rectangle that encloses all black pixels.

You must write an algorithm with less than O(mn) runtime complexity.

Input & Output

Example 1 — Basic Connected Region

$ Input: image = [[0,0,1,0],[0,1,1,0],[0,1,0,0]], x = 0, y = 2

› Output: 6

💡 Note: Black pixels form connected region from (0,2) to (2,1). Rectangle bounds: rows [0,2], columns [1,2]. Area = (2-0+1) × (2-1+1) = 3 × 2 = 6

Example 2 — Single Black Pixel

$ Input: image = [[1]], x = 0, y = 0

› Output: 1

💡 Note: Only one black pixel at (0,0). Rectangle is 1×1, so area = 1

Example 3 — Horizontal Line

$ Input: image = [[1,1,1]], x = 0, y = 1

› Output: 3

💡 Note: Black pixels form horizontal line. Rectangle bounds: row [0,0], columns [0,2]. Area = 1 × 3 = 3

Constraints

m == image.length
n == image[i].length
1 ≤ m, n ≤ 100
image[i][j] is either 0 or 1
0 ≤ x < m
0 ≤ y < n
image[x][y] == 1

Visualization

Tap to expand

Understanding the Visualization

Input Matrix

Binary matrix with connected black pixels and known position

Find Boundaries

Determine min/max rows and columns containing black pixels

Calculate Area

Rectangle area from boundary coordinates

Key Takeaway

🎯 Key Insight: Use binary search on boundaries instead of scanning entire matrix to achieve sub-O(mn) complexity

Asked in

G Google 42 f Facebook 28 M Microsoft 23 A Amazon 19

The key insight is that since black pixels are connected, we can use binary search to find the boundaries instead of scanning every cell. The optimal approach uses binary search on rows and columns to find the rectangle boundaries. Time: O(m log n + n log m), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Check All Cells	O(mn)	O(1)	Scan entire matrix to find min/max boundaries of black pixels
Binary Search on Boundaries	O(m log n + n log m)	O(1)	Binary search to find left, right, top, bottom boundaries efficiently

Brute Force - Check All Cells — Algorithm Steps

Scan all cells to find min/max row and column containing black pixels
Calculate rectangle area using (maxRow - minRow + 1) × (maxCol - minCol + 1)

Visualization

Tap to expand

Step-by-Step Walkthrough

Input Matrix

Binary matrix with connected black pixels

Scan All Cells

Check every position for black pixels

Find Boundaries

Track min/max row and column indices

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int** image, int imageSize, int* imageColSize, int x, int y) {
    if (imageSize == 0 || imageColSize[0] == 0) return 0;
    
    int m = imageSize, n = imageColSize[0];
    int minRow = m, maxRow = -1;
    int minCol = n, maxCol = -1;
    
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (image[i][j] == 1) {
                if (i < minRow) minRow = i;
                if (i > maxRow) maxRow = i;
                if (j < minCol) minCol = j;
                if (j > maxCol) maxCol = j;
            }
        }
    }
    
    return (maxRow - minRow + 1) * (maxCol - minCol + 1);
}

int main() {
    // Simplified input parsing for demonstration
    int image[4][4] = {{0,0,1,0},{0,1,1,0},{0,1,0,0},{0,0,0,0}};
    int* imageRows[4];
    int colSizes[4] = {4,4,4,4};
    
    for (int i = 0; i < 4; i++) {
        imageRows[i] = image[i];
    }
    
    int x = 0, y = 2;
    int result = solution(imageRows, 4, colSizes, x, y);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(mn)

Must check every cell in the m×n matrix

✓ Linear Growth

Space Complexity

O(1)

Only uses a few variables to track boundaries

✓ Linear Space

28.5K Views

Medium Frequency

~25 min Avg. Time

987 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Check All Cells — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler