<p>You are given a 2D <strong>binary</strong> array <code>grid</code>. You need to find 3 <strong>non-overlapping</strong> rectangles having <strong>non-zero</strong> areas with horizontal and vertical sides such that all the 1&#39;s in <code>grid</code> lie inside these rectangles.</p>

<p>Return the <strong>minimum</strong> possible sum of the area of these rectangles.</p>

<p><strong>Note</strong> that the rectangles are allowed to touch.</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 = [[1,0,1],[1,1,1]]</span></p>

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

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

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

<ul>
	<li>The 1&#39;s at <code>(0, 0)</code> and <code>(1, 0)</code> are covered by a rectangle of area 2.</li>
	<li>The 1&#39;s at <code>(0, 2)</code> and <code>(1, 2)</code> are covered by a rectangle of area 2.</li>
	<li>The 1 at <code>(1, 1)</code> is covered by a rectangle of area 1.</li>
</ul>
</div>

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

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

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

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

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

<ul>
	<li>The 1&#39;s at <code>(0, 0)</code> and <code>(0, 2)</code> are covered by a rectangle of area 3.</li>
	<li>The 1 at <code>(1, 1)</code> is covered by a rectangle of area 1.</li>
	<li>The 1 at <code>(1, 3)</code> is covered by a rectangle of area 1.</li>
</ul>
</div>

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

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

class Solution:
    def minimumArea(self, grid: List[List[int]], x1: int, y1: int, x2: int, y2: int) -> int:
        lX = -1
        rX = -1
        uY = -1
        dY = -1
        
        for y in range(y1, y2):
            for x in range(x1, x2):
                if grid[y][x] == 1:
                    if lX == -1 or x < lX:
                        lX = x
                    
                    if rX == -1 or x > rX:
                        rX = x
                        
                    if uY == -1 or y < uY:
                        uY = y
                        
                    if dY == -1 or y > dY:
                        dY = y

        if rX == -1:
            return 0

        return (rX - lX + 1) * (dY - uY + 1)

    def minimumSum(self, grid: List[List[int]]) -> int:                
        minimum = sys.maxsize
        height = len(grid)
        width = len(grid[0])

        for y in range(1, len(grid)):
            for x in range(1, len(grid[y])):
                leftAll = self.minimumArea(grid, 0, 0, x, height)
                rightUp = self.minimumArea(grid, x, 0, width, y)
                rightDown = self.minimumArea(grid, x, y, width, height)

                a = leftAll + rightUp + rightDown

                leftUp = self.minimumArea(grid, 0, 0, x, y)
                leftDown = self.minimumArea(grid, 0, y, x, height)
                rightAll = self.minimumArea(grid, x, 0, width, height)

                b = leftUp + leftDown + rightAll

                topAll = self.minimumArea(grid, 0, 0, width, y)
                bottomAll = self.minimumArea(grid, 0, y, width, height)

                c = topAll + leftDown + rightDown
                d = bottomAll + leftUp + rightUp

                minimum = min(a, b, c, d, minimum)

        for y1 in range(height - 1):
            for y2 in range(y1 + 1, height):
                up = self.minimumArea(grid, 0, 0, width, y1)
                middle = self.minimumArea(grid, 0, y1, width, y2)
                down = self.minimumArea(grid, 0, y2, width, height)

                area = up + middle + down
                minimum = min(area, minimum)

        for x1 in range(width - 1):
            for x2 in range(x1 + 1, width):
                left = self.minimumArea(grid, 0, 0, x1, height)
                middle = self.minimumArea(grid, x1, 0, x2, height)
                right = self.minimumArea(grid, x2, 0, width, height)
            
                area = left + middle + right
                minimum = min(area, minimum)
                
        return minimum
1504