Skip to content

Instantly share code, notes, and snippets.

@SuryaPratapK

SuryaPratapK/Find the Minimum Area to Cover All Ones II | Leetcode 3197

Created August 23, 2025 07:53
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save SuryaPratapK/99bdc9426b0442e081d65b3cb7c161f5 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save SuryaPratapK/99bdc9426b0442e081d65b3cb7c161f5 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
Find the Minimum Area to Cover All Ones II | Leetcode 3197
// C++: O(M^2 + N^2 + MN) * (log M + log N) Solution
class Solution {
vector<vector<int>> prefix_sum;
void computePrefixSum(vector<vector<int>>& grid){
for(int i=0;i<grid.size();++i){
for(int j=0;j<grid[0].size();++j){
prefix_sum[i+1][j+1] = grid[i][j] + prefix_sum[i+1][j] + prefix_sum[i][j+1] - prefix_sum[i][j];
}
}
}
int getBoxSum(int x1,int x2,int y1,int y2){
return prefix_sum[x2+1][y2+1] - prefix_sum[x1][y2+1] - prefix_sum[x2+1][y1] + prefix_sum[x1][y1];
}
void findBoundingCoordinates(vector<vector<int>>& grid,int& low_x,int& high_x,int& low_y,int& high_y){
for(int i=0;i<grid.size();++i){
for(int j=0;j<grid[0].size();++j){
if(grid[i][j]==1){
low_x = min(low_x,i);
high_x = max(high_x,i);
low_y = min(low_y,j);
high_y = max(high_y,j);
}
}
}
}
int findMinArea(int x1,int x2,int y1,int y2,vector<vector<int>>& grid){
int total_ones = getBoxSum(x1,x2,y1,y2);
if(total_ones == 0) return 0;
int min_x, max_x, min_y, max_y;
// Binary search to find optimal bounding box
// Find min_x
min_x = x2;
int low = x1, high = x2, mid;
while(low <= high){
mid = low + (high - low)/2;
if(getBoxSum(x1,mid,y1,y2) > 0){
min_x = mid;
high = mid-1;
}else{
low = mid+1;
}
}
// Find max_x
max_x = x1;
low = x1, high = x2;
while(low <= high){
mid = low + (high-low)/2;
if(getBoxSum(mid,x2,y1,y2) > 0){
max_x = mid;
low = mid+1;
}else{
high = mid-1;
}
}
// Find min_y
min_y = y2;
low = y1, high = y2;
while(low <= high){
mid = low + (high-low)/2;
if(getBoxSum(x1,x2,y1,mid) > 0){
min_y = mid;
high = mid-1;
}else{
low = mid+1;
}
}
// Find max_y
max_y = y1;
low = y1, high = y2;
while(low <= high){
mid = low + (high-low)/2;
if(getBoxSum(x1,x2,mid,y2) > 0){
max_y = mid;
low = mid+1;
}else{
high = mid-1;
}
}
return (max_x - min_x + 1) * (max_y - min_y + 1);
}
public:
int minimumSum(vector<vector<int>>& grid) {
int m = grid.size();
int n = grid[0].size();
prefix_sum.assign(m+1,vector<int>(n+1));
computePrefixSum(grid);
int low_x = INT_MAX, high_x = -1;
int low_y = INT_MAX, high_y = -1;
findBoundingCoordinates(grid,low_x,high_x,low_y,high_y);
int lowest_area = INT_MAX;
int area;
for(int i=low_x;i<high_x;++i){
for(int j=low_y;j<high_y;++j){
for(int count=1;count<=4;++count){
switch(count){
case 1://Up
area = findMinArea(low_x,i,low_y,j,grid) +
findMinArea(low_x,i,j+1,high_y,grid) +
findMinArea(i+1,high_x,low_y,high_y,grid);
break;
case 2://Right
area = findMinArea(low_x,high_x,low_y,j,grid) +
findMinArea(low_x,i,j+1,high_y,grid) +
findMinArea(i+1,high_x,j+1,high_y,grid);
break;
case 3://Down
area = findMinArea(low_x,i,low_y,high_y,grid) +
findMinArea(i+1,high_x,low_y,j,grid) +
findMinArea(i+1,high_x,j+1,high_y,grid);
break;
case 4://Left
area = findMinArea(low_x,i,low_y,j,grid) +
findMinArea(i+1,high_x,low_y,j,grid) +
findMinArea(low_x,high_x,j+1,high_y,grid);
break;
}
lowest_area = min(lowest_area,area);
}
}
}
//Case-5: Horizontal Slicing
for(int i=low_x;i<high_x-1;++i){
for(int j=i+1;j<high_x;++j){
lowest_area = min(lowest_area, findMinArea(low_x,i,low_y,high_y,grid) +
findMinArea(i+1,j,low_y,high_y,grid) +
findMinArea(j+1,high_x,low_y,high_y,grid));
}
}
//Case-6: Vertical Slicing
for(int i=low_y;i<high_y-1;++i){
for(int j=i+1;j<high_y;++j){
lowest_area = min(lowest_area, findMinArea(low_x,high_x,low_y,i,grid) +
findMinArea(low_x,high_x,i+1,j,grid) +
findMinArea(low_x,high_x,j+1,high_y,grid));
}
}
return lowest_area;
}
};
/*
//JAVA : O(M^2 + N^2 + MN) * (log M + log N) Solution
import java.util.*;
public class Solution {
private int[][] pref;
private void computePrefixSum(int[][] grid){
int m = grid.length, n = grid[0].length;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
pref[i+1][j+1] = grid[i][j] + pref[i+1][j] + pref[i][j+1] - pref[i][j];
}
}
}
private int getBoxSum(int x1, int x2, int y1, int y2){
if (x1 > x2 || y1 > y2) return 0;
return pref[x2+1][y2+1] - pref[x1][y2+1] - pref[x2+1][y1] + pref[x1][y1];
}
private void findBoundingCoordinates(int[][] grid, int[] bounds){
int m = grid.length, n = grid[0].length;
int low_x = Integer.MAX_VALUE, high_x = -1;
int low_y = Integer.MAX_VALUE, high_y = -1;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] == 1) {
low_x = Math.min(low_x, i);
high_x = Math.max(high_x, i);
low_y = Math.min(low_y, j);
high_y = Math.max(high_y, j);
}
}
}
bounds[0] = low_x; bounds[1] = high_x; bounds[2] = low_y; bounds[3] = high_y;
}
private int findMinArea(int x1, int x2, int y1, int y2, int[][] grid){
if (x1 > x2 || y1 > y2) return 0;
int total = getBoxSum(x1, x2, y1, y2);
if (total == 0) return 0;
// min_x: first row in [x1..x2] that contains a 1 in cols [y1..y2]
int min_x = x2;
int lo = x1, hi = x2;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (getBoxSum(x1, mid, y1, y2) > 0) {
min_x = mid;
hi = mid - 1;
} else lo = mid + 1;
}
// max_x: last row in [x1..x2] that contains a 1 in cols [y1..y2]
int max_x = x1;
lo = x1; hi = x2;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (getBoxSum(mid, x2, y1, y2) > 0) {
max_x = mid;
lo = mid + 1;
} else hi = mid - 1;
}
// min_y: first col in [y1..y2] that contains a 1 in rows [x1..x2]
int min_y = y2;
lo = y1; hi = y2;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (getBoxSum(x1, x2, y1, mid) > 0) {
min_y = mid;
hi = mid - 1;
} else lo = mid + 1;
}
// max_y: last col in [y1..y2] that contains a 1 in rows [x1..x2]
int max_y = y1;
lo = y1; hi = y2;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (getBoxSum(x1, x2, mid, y2) > 0) {
max_y = mid;
lo = mid + 1;
} else hi = mid - 1;
}
return (max_x - min_x + 1) * (max_y - min_y + 1);
}
public int minimumSum(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
pref = new int[m + 1][n + 1];
computePrefixSum(grid);
int[] bounds = new int[4];
findBoundingCoordinates(grid, bounds);
int low_x = bounds[0], high_x = bounds[1], low_y = bounds[2], high_y = bounds[3];
// if no 1s
if (high_x == -1) return 0;
int lowest_area = Integer.MAX_VALUE;
// Case 1..4
for (int i = low_x; i < high_x; ++i) {
for (int j = low_y; j < high_y; ++j) {
for (int count = 1; count <= 4; ++count) {
int area = 0;
switch (count) {
case 1: // Up
area = findMinArea(low_x, i, low_y, j, grid)
+ findMinArea(low_x, i, j+1, high_y, grid)
+ findMinArea(i+1, high_x, low_y, high_y, grid);
break;
case 2: // Right
area = findMinArea(low_x, high_x, low_y, j, grid)
+ findMinArea(low_x, i, j+1, high_y, grid)
+ findMinArea(i+1, high_x, j+1, high_y, grid);
break;
case 3: // Down
area = findMinArea(low_x, i, low_y, high_y, grid)
+ findMinArea(i+1, high_x, low_y, j, grid)
+ findMinArea(i+1, high_x, j+1, high_y, grid);
break;
case 4: // Left
area = findMinArea(low_x, i, low_y, j, grid)
+ findMinArea(i+1, high_x, low_y, j, grid)
+ findMinArea(low_x, high_x, j+1, high_y, grid);
break;
}
lowest_area = Math.min(lowest_area, area);
}
}
}
// Case-5: Horizontal slicing
for (int i = low_x; i < high_x - 1; ++i) {
for (int j = i + 1; j < high_x; ++j) {
int area = findMinArea(low_x, i, low_y, high_y, grid)
+ findMinArea(i+1, j, low_y, high_y, grid)
+ findMinArea(j+1, high_x, low_y, high_y, grid);
lowest_area = Math.min(lowest_area, area);
}
}
// Case-6: Vertical slicing
for (int i = low_y; i < high_y - 1; ++i) {
for (int j = i + 1; j < high_y; ++j) {
int area = findMinArea(low_x, high_x, low_y, i, grid)
+ findMinArea(low_x, high_x, i+1, j, grid)
+ findMinArea(low_x, high_x, j+1, high_y, grid);
lowest_area = Math.min(lowest_area, area);
}
}
return (lowest_area == Integer.MAX_VALUE) ? 0 : lowest_area;
}
}
#Python : O(M^2 + N^2 + MN) * (log M + log N) Solution
from typing import List
class Solution:
def __init__(self):
self.pref = []
def computePrefixSum(self, grid: List[List[int]]) -> None:
m, n = len(grid), len(grid[0])
# pref is (m+1) x (n+1)
self.pref = [[0] * (n+1) for _ in range(m+1)]
for i in range(m):
for j in range(n):
self.pref[i+1][j+1] = grid[i][j] + self.pref[i+1][j] + self.pref[i][j+1] - self.pref[i][j]
def getBoxSum(self, x1: int, x2: int, y1: int, y2: int) -> int:
if x1 > x2 or y1 > y2:
return 0
return self.pref[x2+1][y2+1] - self.pref[x1][y2+1] - self.pref[x2+1][y1] + self.pref[x1][y1]
def findBoundingCoordinates(self, grid: List[List[int]]):
m, n = len(grid), len(grid[0])
low_x, high_x = float('inf'), -1
low_y, high_y = float('inf'), -1
for i in range(m):
for j in range(n):
if grid[i][j] == 1:
low_x = min(low_x, i)
high_x = max(high_x, i)
low_y = min(low_y, j)
high_y = max(high_y, j)
if high_x == -1:
return None
return (low_x, high_x, low_y, high_y)
def findMinArea(self, x1: int, x2: int, y1: int, y2: int, grid: List[List[int]]) -> int:
if x1 > x2 or y1 > y2:
return 0
total = self.getBoxSum(x1, x2, y1, y2)
if total == 0:
return 0
# find min_x
min_x = x2
lo, hi = x1, x2
while lo <= hi:
mid = (lo + hi) // 2
if self.getBoxSum(x1, mid, y1, y2) > 0:
min_x = mid
hi = mid - 1
else:
lo = mid + 1
# find max_x
max_x = x1
lo, hi = x1, x2
while lo <= hi:
mid = (lo + hi) // 2
if self.getBoxSum(mid, x2, y1, y2) > 0:
max_x = mid
lo = mid + 1
else:
hi = mid - 1
# find min_y
min_y = y2
lo, hi = y1, y2
while lo <= hi:
mid = (lo + hi) // 2
if self.getBoxSum(x1, x2, y1, mid) > 0:
min_y = mid
hi = mid - 1
else:
lo = mid + 1
# find max_y
max_y = y1
lo, hi = y1, y2
while lo <= hi:
mid = (lo + hi) // 2
if self.getBoxSum(x1, x2, mid, y2) > 0:
max_y = mid
lo = mid + 1
else:
hi = mid - 1
return (max_x - min_x + 1) * (max_y - min_y + 1)
def minimumSum(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
self.computePrefixSum(grid)
bounds = self.findBoundingCoordinates(grid)
if bounds is None:
return 0
low_x, high_x, low_y, high_y = bounds
lowest_area = float('inf')
# Case 1..4
for i in range(low_x, high_x):
for j in range(low_y, high_y):
for count in range(1, 5):
if count == 1:
area = ( self.findMinArea(low_x, i, low_y, j, grid)
+ self.findMinArea(low_x, i, j+1, high_y, grid)
+ self.findMinArea(i+1, high_x, low_y, high_y, grid) )
elif count == 2:
area = ( self.findMinArea(low_x, high_x, low_y, j, grid)
+ self.findMinArea(low_x, i, j+1, high_y, grid)
+ self.findMinArea(i+1, high_x, j+1, high_y, grid) )
elif count == 3:
area = ( self.findMinArea(low_x, i, low_y, high_y, grid)
+ self.findMinArea(i+1, high_x, low_y, j, grid)
+ self.findMinArea(i+1, high_x, j+1, high_y, grid) )
else: # count == 4
area = ( self.findMinArea(low_x, i, low_y, j, grid)
+ self.findMinArea(i+1, high_x, low_y, j, grid)
+ self.findMinArea(low_x, high_x, j+1, high_y, grid) )
lowest_area = min(lowest_area, area)
# Case-5: Horizontal slicing
for i in range(low_x, high_x - 1):
for j in range(i+1, high_x):
area = ( self.findMinArea(low_x, i, low_y, high_y, grid)
+ self.findMinArea(i+1, j, low_y, high_y, grid)
+ self.findMinArea(j+1, high_x, low_y, high_y, grid) )
lowest_area = min(lowest_area, area)
# Case-6: Vertical slicing
for i in range(low_y, high_y - 1):
for j in range(i+1, high_y):
area = ( self.findMinArea(low_x, high_x, low_y, i, grid)
+ self.findMinArea(low_x, high_x, i+1, j, grid)
+ self.findMinArea(low_x, high_x, j+1, high_y, grid) )
lowest_area = min(lowest_area, area)
return 0 if lowest_area == float('inf') else int(lowest_area)
*/
// C++: O((M^2 + N^2)* MN) Simple Solution
class Solution {
void findBoundingCoordinates(vector<vector<int>>& grid,int& low_x,int& high_x,int& low_y,int& high_y){
for(int i=0;i<grid.size();++i){
for(int j=0;j<grid[0].size();++j){
if(grid[i][j]==1){
low_x = min(low_x,i);
high_x = max(high_x,i);
low_y = min(low_y,j);
high_y = max(high_y,j);
}
}
}
}
int findMinArea(int x1,int x2,int y1,int y2,vector<vector<int>>& grid){
int min_x = INT_MAX;
int max_x = -1;
int min_y = INT_MAX;
int max_y = -1;
for(int i=x1;i<=x2;++i){
for(int j=y1;j<=y2;++j){
if(grid[i][j]==1){
min_x = min(min_x,i);
max_x = max(max_x,i);
min_y = min(min_y,j);
max_y = max(max_y,j);
}
}
}
if(min_x==INT_MAX or max_x==-1 or min_y==INT_MAX or max_y==-1)
return 0;
return (max_x - min_x + 1) * (max_y - min_y + 1);
}
public:
int minimumSum(vector<vector<int>>& grid) {
int low_x = INT_MAX, high_x = -1;
int low_y = INT_MAX, high_y = -1;
findBoundingCoordinates(grid,low_x,high_x,low_y,high_y);
int lowest_area = INT_MAX;
int area;
for(int i=low_x;i<high_x;++i){
for(int j=low_y;j<high_y;++j){
for(int count=1;count<=4;++count){
switch(count){
case 1://Up
area = findMinArea(low_x,i,low_y,j,grid) +
findMinArea(low_x,i,j+1,high_y,grid) +
findMinArea(i+1,high_x,low_y,high_y,grid);
break;
case 2://Right
area = findMinArea(low_x,high_x,low_y,j,grid) +
findMinArea(low_x,i,j+1,high_y,grid) +
findMinArea(i+1,high_x,j+1,high_y,grid);
break;
case 3://Down
area = findMinArea(low_x,i,low_y,high_y,grid) +
findMinArea(i+1,high_x,low_y,j,grid) +
findMinArea(i+1,high_x,j+1,high_y,grid);
break;
case 4://Left
area = findMinArea(low_x,i,low_y,j,grid) +
findMinArea(i+1,high_x,low_y,j,grid) +
findMinArea(low_x,high_x,j+1,high_y,grid);
break;
}
lowest_area = min(lowest_area,area);
}
}
}
//Case-5: Horizontal Slicing
for(int i=low_x;i<high_x-1;++i){
for(int j=i+1;j<high_x;++j){
lowest_area = min(lowest_area, findMinArea(low_x,i,low_y,high_y,grid) +
findMinArea(i+1,j,low_y,high_y,grid) +
findMinArea(j+1,high_x,low_y,high_y,grid));
}
}
//Case-6: Vertical Slicing
for(int i=low_y;i<high_y-1;++i){
for(int j=i+1;j<high_y;++j){
lowest_area = min(lowest_area, findMinArea(low_x,high_x,low_y,i,grid) +
findMinArea(low_x,high_x,i+1,j,grid) +
findMinArea(low_x,high_x,j+1,high_y,grid));
}
}
return lowest_area;
}
};
/*
//JAVA: O((M^2 + N^2)* MN) Simple Solution
class Solution {
private void findBoundingCoordinates(int[][] grid, int[] bounds) {
int m = grid.length, n = grid[0].length;
int low_x = Integer.MAX_VALUE, high_x = -1, low_y = Integer.MAX_VALUE, high_y = -1;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] == 1) {
low_x = Math.min(low_x, i);
high_x = Math.max(high_x, i);
low_y = Math.min(low_y, j);
high_y = Math.max(high_y, j);
}
}
}
bounds[0] = low_x;
bounds[1] = high_x;
bounds[2] = low_y;
bounds[3] = high_y;
}
private int findMinArea(int x1, int x2, int y1, int y2, int[][] grid) {
int min_x = Integer.MAX_VALUE, max_x = -1, min_y = Integer.MAX_VALUE, max_y = -1;
for (int i = x1; i <= x2; ++i) {
for (int j = y1; j <= y2; ++j) {
if (grid[i][j] == 1) {
min_x = Math.min(min_x, i);
max_x = Math.max(max_x, i);
min_y = Math.min(min_y, j);
max_y = Math.max(max_y, j);
}
}
}
if (min_x == Integer.MAX_VALUE || max_x == -1 || min_y == Integer.MAX_VALUE || max_y == -1)
return 0;
return (max_x - min_x + 1) * (max_y - min_y + 1);
}
public int minimumSum(int[][] grid) {
int[] b = new int[4];
findBoundingCoordinates(grid, b);
int low_x = b[0], high_x = b[1], low_y = b[2], high_y = b[3];
if (low_x == Integer.MAX_VALUE) return 0; // no 1s
int lowest_area = Integer.MAX_VALUE;
// 4-way L-shaped splits
for (int i = low_x; i < high_x; ++i) {
for (int j = low_y; j < high_y; ++j) {
for (int count = 1; count <= 4; ++count) {
int area = 0;
switch (count) {
case 1: // Up
area = findMinArea(low_x, i, low_y, j, grid)
+ findMinArea(low_x, i, j + 1, high_y, grid)
+ findMinArea(i + 1, high_x, low_y, high_y, grid);
break;
case 2: // Right
area = findMinArea(low_x, high_x, low_y, j, grid)
+ findMinArea(low_x, i, j + 1, high_y, grid)
+ findMinArea(i + 1, high_x, j + 1, high_y, grid);
break;
case 3: // Down
area = findMinArea(low_x, i, low_y, high_y, grid)
+ findMinArea(i + 1, high_x, low_y, j, grid)
+ findMinArea(i + 1, high_x, j + 1, high_y, grid);
break;
case 4: // Left
area = findMinArea(low_x, i, low_y, j, grid)
+ findMinArea(i + 1, high_x, low_y, j, grid)
+ findMinArea(low_x, high_x, j + 1, high_y, grid);
break;
}
lowest_area = Math.min(lowest_area, area);
}
}
}
// Case-5: Horizontal slicing (three horizontal strips)
for (int i = low_x; i < high_x - 1; ++i) {
for (int j = i + 1; j < high_x; ++j) {
lowest_area = Math.min(lowest_area,
findMinArea(low_x, i, low_y, high_y, grid)
+ findMinArea(i + 1, j, low_y, high_y, grid)
+ findMinArea(j + 1, high_x, low_y, high_y, grid));
}
}
// Case-6: Vertical slicing (three vertical strips)
for (int i = low_y; i < high_y - 1; ++i) {
for (int j = i + 1; j < high_y; ++j) {
lowest_area = Math.min(lowest_area,
findMinArea(low_x, high_x, low_y, i, grid)
+ findMinArea(low_x, high_x, i + 1, j, grid)
+ findMinArea(low_x, high_x, j + 1, high_y, grid));
}
}
return (lowest_area == Integer.MAX_VALUE) ? 0 : lowest_area;
}
}
#Python: O((M^2 + N^2)* MN) Simple Solution
# Python translation of the provided C++ solution
class Solution:
def findBoundingCoordinates(self, grid):
m, n = len(grid), len(grid[0])
low_x, high_x = float('inf'), -1
low_y, high_y = float('inf'), -1
for i in range(m):
for j in range(n):
if grid[i][j] == 1:
low_x = min(low_x, i)
high_x = max(high_x, i)
low_y = min(low_y, j)
high_y = max(high_y, j)
return low_x, high_x, low_y, high_y
def findMinArea(self, x1, x2, y1, y2, grid):
min_x, max_x = float('inf'), -1
min_y, max_y = float('inf'), -1
for i in range(x1, x2 + 1):
for j in range(y1, y2 + 1):
if grid[i][j] == 1:
min_x = min(min_x, i)
max_x = max(max_x, i)
min_y = min(min_y, j)
max_y = max(max_y, j)
if min_x == float('inf') or max_x == -1 or min_y == float('inf') or max_y == -1:
return 0
return (max_x - min_x + 1) * (max_y - min_y + 1)
def minimumSum(self, grid):
low_x, high_x, low_y, high_y = self.findBoundingCoordinates(grid)
if low_x == float('inf'):
return 0
lowest_area = float('inf')
# 4-way L-shaped splits
for i in range(low_x, high_x):
for j in range(low_y, high_y):
for count in range(1, 5):
if count == 1: # Up
area = (self.findMinArea(low_x, i, low_y, j, grid)
+ self.findMinArea(low_x, i, j + 1, high_y, grid)
+ self.findMinArea(i + 1, high_x, low_y, high_y, grid))
elif count == 2: # Right
area = (self.findMinArea(low_x, high_x, low_y, j, grid)
+ self.findMinArea(low_x, i, j + 1, high_y, grid)
+ self.findMinArea(i + 1, high_x, j + 1, high_y, grid))
elif count == 3: # Down
area = (self.findMinArea(low_x, i, low_y, high_y, grid)
+ self.findMinArea(i + 1, high_x, low_y, j, grid)
+ self.findMinArea(i + 1, high_x, j + 1, high_y, grid))
else: # Left
area = (self.findMinArea(low_x, i, low_y, j, grid)
+ self.findMinArea(i + 1, high_x, low_y, j, grid)
+ self.findMinArea(low_x, high_x, j + 1, high_y, grid))
lowest_area = min(lowest_area, area)
# Case-5: Horizontal slicing (three horizontal strips)
for i in range(low_x, high_x - 1):
for j in range(i + 1, high_x):
candidate = (self.findMinArea(low_x, i, low_y, high_y, grid)
+ self.findMinArea(i + 1, j, low_y, high_y, grid)
+ self.findMinArea(j + 1, high_x, low_y, high_y, grid))
lowest_area = min(lowest_area, candidate)
# Case-6: Vertical slicing (three vertical strips)
for i in range(low_y, high_y - 1):
for j in range(i + 1, high_y):
candidate = (self.findMinArea(low_x, high_x, low_y, i, grid)
+ self.findMinArea(low_x, high_x, i + 1, j, grid)
+ self.findMinArea(low_x, high_x, j + 1, high_y, grid))
lowest_area = min(lowest_area, candidate)
return 0 if lowest_area == float('inf') else int(lowest_area)
*/
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment