Skip to main content
Talentd

Find the Minimum Area to Cover All Ones I - Solution & Explanation

MediumArrayMatrix15 min readAsked at: Amazon, Microsoft, Salesforce +2
Practice this problem

Problem Statement

You are given a 2D binary array grid. Find a rectangle with horizontal and vertical sides with the smallest area, such that all the 1's in grid lie inside this rectangle.

Return the minimum possible area of the rectangle.

 

Example 1:

Input: grid = [[0,1,0],[1,0,1]]

Output: 6

Explanation:

The smallest rectangle has a height of 2 and a width of 3, so it has an area of 2 * 3 = 6.

Example 2:

Input: grid = [[1,0],[0,0]]

Output: 1

Explanation:

The smallest rectangle has both height and width 1, so its area is 1 * 1 = 1.

 

Constraints:

  • 1 <= grid.length, grid[i].length <= 1000
  • grid[i][j] is either 0 or 1.
  • The input is generated such that there is at least one 1 in grid.

Approach Overview

Problem Overview: You are given a binary grid and need the smallest axis-aligned rectangle that covers every cell containing 1. The rectangle must include all rows and columns where a 1 appears, and the result is the area of that rectangle.

Approach 1: Brute Force Rectangle Search (O(m3 * n3) time, O(1) space)

The brute force idea checks every possible rectangle in the grid and verifies whether it covers all the 1 cells. You iterate over all pairs of top/bottom rows and left/right columns, then scan the rectangle to confirm whether every 1 lies inside it. This method uses nested loops over the grid dimensions and repeated validation scans. It works but quickly becomes impractical as the grid grows. This approach mainly demonstrates the baseline reasoning before optimizing with better observations about the distribution of 1s in the matrix.

Approach 2: Coordinate Compression / Bounding Box (O(m * n) time, O(1) space)

The key observation: the smallest rectangle covering all 1s is defined by the extreme coordinates where 1 appears. While scanning the grid once, track four values: minRow, maxRow, minCol, and maxCol. Each time you encounter a 1, update these boundaries. After the scan, the rectangle height is maxRow - minRow + 1 and the width is maxCol - minCol + 1. Multiplying them gives the minimum area. The idea resembles coordinate compression because you reduce the relevant search space to the coordinates containing 1. This single pass solution leverages simple iteration over the array-based grid and avoids storing extra structures.

Recommended for interviews: Interviewers expect the bounding box scan. It shows you can translate a spatial constraint into tracked boundaries while iterating through a grid. Mentioning the brute force rectangle enumeration shows you understand the naive search space, but recognizing that only the extreme coordinates matter demonstrates stronger algorithmic thinking.

Approach 1: Brute Force Approach

This approach involves iterating through the entire grid to determine the minimum and maximum rows and columns that contain a '1'. By doing this, we can define the top-left and bottom-right corners of the smallest rectangle that can encompass all the '1's. The approach is direct and fairly simple, although it may not be the most efficient for larger grids.

In this C implementation, we scan the entire grid to find the minimum and maximum indices of the rows and columns containing '1's. Once found, we calculate the rectangle's area by using the differences between the maximum and minimum coordinates, plus 1 to account for a zero-based index.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n * m), where n is the number of rows and m is the number of columns. We traverse each element of the grid once.
Space Complexity: O(1). No additional space is used except for a few integers.

Try this approach in the editor →

Approach 2: Coordinate Compression Approach

Coordinate Compression is an optimized method where instead of examining the entire matrix, you 'compress' rows and columns by recording only the necessary indices where a '1' appears. This can potentially reduce the runtime when there are sizable sections of zero-filled areas.

This Python solution implements coordinate compression by tracking only those rows and columns which contain '1's. Using list comprehensions and Python's set operations, the coordinates are efficiently assembled, and the enclosing area is calculated based on these condensed results.

Code

PythonJava

Python

Java

Complexity

Time Complexity: O(n * m), in the worst case when there's a '1' in each row and column, degenerating to complete scan.
Space Complexity: O(n + m) for storing the compressed row and column indices.

Try this approach in the editor →

Approach 3: Find Minimum and Maximum Boundaries

We can traverse grid, finding the minimum boundary of all 1s, denoted as (x_1, y_1), and the maximum boundary, denoted as (x_2, y_2). Then, the area of the minimum rectangle is (x_2 - x_1 + 1) times (y_2 - y_1 + 1).

The time complexity is O(m times n), where m and n are the number of rows and columns in grid, respectively. The space complexity is O(1).

Code

PythonJavaC++GoTypeScriptRustJavaScriptC#

Python

Java

C++

Go

TypeScript

Rust

JavaScript

C#

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Brute Force Approach

Time Complexity: O(n * m), where n is the number of rows and m is the number of columns. We traverse each element of the grid once.
Space Complexity: O(1). No additional space is used except for a few integers.

Coordinate Compression Approach

Time Complexity: O(n * m), in the worst case when there's a '1' in each row and column, degenerating to complete scan.
Space Complexity: O(n + m) for storing the compressed row and column indices.

Find Minimum and Maximum Boundaries—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Rectangle SearchO(m^3 * n^3)O(1)Useful for understanding the full search space of possible rectangles or when explaining the naive baseline in interviews.
Coordinate Compression / Bounding Box ScanO(m * n)O(1)Best general solution. Single pass over the grid to track extreme rows and columns containing 1s.

Video Solution

Find the Minimum Area to Cover All Ones I | Simple Explanation | Leetcode 3195 | codestorywithMIK • codestorywithMIK • 6,034 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Find the Minimum Area to Cover All Ones I easy or hard?
The problem is usually classified as Medium difficulty because it requires recognizing that only the extreme coordinates of 1s matter. The implementation itself is straightforward once that insight is clear, involving a single pass over the matrix.
Find the Minimum Area to Cover All Ones I Python/Java solution
The typical Python or Java implementation iterates through the grid using nested loops. Whenever a cell with value 1 is found, update minRow, maxRow, minCol, and maxCol. After traversal, compute the area using the bounding rectangle formula. This implementation runs in O(m*n) time and O(1) space.
How to solve Find the Minimum Area to Cover All Ones I in O(n)?
Treat the grid as m*n cells and perform a single scan. Track the minimum and maximum row and column indices where a 1 appears. After finishing the scan, compute the rectangle area as (maxRow - minRow + 1) * (maxCol - minCol + 1). This linear scan over the matrix achieves O(m*n) time.
What is the best approach for Find the Minimum Area to Cover All Ones I?
The optimal approach scans the grid once and tracks the extreme coordinates where a 1 appears. Maintain minRow, maxRow, minCol, and maxCol while iterating through the matrix. The rectangle defined by these boundaries is the smallest possible area covering all ones. This runs in O(m*n) time and O(1) extra space.
Is Find the Minimum Area to Cover All Ones I asked at Google/Amazon/Meta?
Matrix scanning and bounding box style problems frequently appear in interviews at companies like Amazon, Google, and Meta. The exact problem may vary, but identifying extreme coordinates of elements in a grid is a common pattern tested in array and matrix interview questions.
What data structure is used in Find the Minimum Area to Cover All Ones I?
The solution primarily uses a 2D array (matrix) traversal. Instead of additional data structures, it keeps four integer variables to track the minimum and maximum row and column indices where a 1 occurs.
What is the time complexity of Find the Minimum Area to Cover All Ones I?
The optimal solution runs in O(m*n) time because every cell of the grid is visited exactly once. Only four boundary variables are updated when a 1 is encountered. Space complexity is O(1) since no additional data structures proportional to the grid size are required.

Ready to solve this problem?

Practice Find the Minimum Area to Cover All Ones I with our built-in code editor and test cases.

Practice on FleetCode
Previous

Smallest Rectangle Enclosing Black Pixels