SalesForce OA-5 2023

Problem Description

You are given an M * N binary matrix representing the shape of an item that is supposed to be packed for shipping. The item is contiguous, meaning it consists of a connected group of 1s, either horizontally or vertically. The shipping agency only has rectangular boxes available, and they want to minimize the area of the box that can fit the item.

Your task is to find the smallest rectangular area that can completely contain the item.

For example, given the matrix:

[[0, 1, 0],
[0, 1, 1],
[0, 0, 0]]

The smallest rectangle that can pack the item has an area of 2*2 = 4.

Input Format:

• A 2D binary array grid where each element is either 0 or 1:
  • 0 represents an empty area.
  • 1 represents a part of the item.

Output Format:

• Return an integer representing the smallest area of the rectangle needed to fit the item.

Constraints:

• 0<=grid[i][j]<=1
• There is only one contiguous item of 1's in the matrix, i.e., the item is connected either horizontally or vertically.

Sample Testcases:

Sample Case 1:

Input:

0 1 0
0 1 1
0 0 0

Output:

4

Explanation:

The smallest rectangle needed to fit the item starts from index (0, 1) and ends at
(1, 2), resulting in a rectangle of size 2*2 = 4.

Sample Case 2:

Input:

0 1 0
0 1 0
0 1 0

Output:

3

Explanation:

The smallest rectangle needed to fit the item has the same shape as the item itself, which is a 1*3 rectangle, resulting in an area of 3.