<p>You are given a 2D <strong>binary</strong> array <code>grid</code>. Find a rectangle with horizontal and vertical sides with the<strong> smallest</strong> area, such that all the 1&#39;s in <code>grid</code> lie inside this rectangle.</p>

<p>Return the <strong>minimum</strong> possible area of the rectangle.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">grid = [[0,1,0],[1,0,1]]</span></p>

<p><strong>Output:</strong> <span class="example-io">6</span></p>

<p><strong>Explanation:</strong></p>

<p><img alt="" src="https://assets.leetcode.com/uploads/2024/05/08/examplerect0.png" style="padding: 10px; background: rgb(255, 255, 255); border-radius: 0.5rem; width: 279px; height: 198px;" /></p>

<p>The smallest rectangle has a height of 2 and a width of 3, so it has an area of <code>2 * 3 = 6</code>.</p>
</div>

<p><strong class="example">Example 2:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">grid = [[1,0],[0,0]]</span></p>

<p><strong>Output:</strong> <span class="example-io">1</span></p>

<p><strong>Explanation:</strong></p>

<p><img alt="" src="https://assets.leetcode.com/uploads/2024/05/08/examplerect1.png" style="padding: 10px; background: rgb(255, 255, 255); border-radius: 0.5rem; width: 204px; height: 201px;" /></p>

<p>The smallest rectangle has both height and width 1, so its area is <code>1 * 1 = 1</code>.</p>
</div>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= grid.length, grid[i].length &lt;= 1000</code></li>
	<li><code>grid[i][j]</code> is either 0 or 1.</li>
	<li>The input is generated such that there is at least one 1 in <code>grid</code>.</li>
</ul>

class Solution:
    def minimumArea(self, grid):
        def helper(arr, n):
            if 1 in arr:
                l, r = 0, 0
                for i in range(n):
                    if arr[i] == 1:
                        l = i
                        break
                for i in range(n-1, -1, -1):
                    if arr[i] == 1:
                        r = i
                        break
                return [l, r]
            else:
                return -1 

        n, m = len(grid), len(grid[0])
        left, right, top, bot = 1001, -1, 1001, -1

        for i in range(n):
            #print(grid[i])
            #print(helper(grid[i], m))
            if helper(grid[i], m) != -1:
                l, r = helper(grid[i], m)
                left, right = min(l, left), max(r, right)
        #print(left, right)

        print()

        for i in range(m):
            #print([row[i] for row in grid])
            #print(helper([row[i] for row in grid], n))
            if helper([row[i] for row in grid], n) != -1:
                t, b = helper([row[i] for row in grid], n)
                top, bot = min(t, top), max(b, bot)

        #print(top, bot)

        return (right-left+1)*(bot-top+1)
        
2583