3197. Find the Minimum Area to Cover All Ones II

Intuition

The solution utilizes dynamic programming (DP) with recursion and memoization to efficiently solve the problem of finding three non-overlapping rectangles with the minimum possible sum of their areas.

Approach

1. Dynamic Programming State Definition: - Define a recursive function getNext(i1, j1, i2, j2, k) that computes the minimum possible sum of areas for k rectangles covering the subgrid from (i1, j1) to (i2, j2).
2. Base Case: - If k = 1, calculate the area of the rectangle covering the subgrid directly. This involves finding the smallest rectangle that encloses all 1s in the specified subgrid.
3. Recursive Case: - For k = 2 and k = 3, split the current subgrid into two parts (either horizontally or vertically) and recursively compute the minimum sum of areas for covering these parts using smaller numbers of rectangles (k-1 or k-2).
4. Memoization: - Use memoization to store computed results of getNext for each unique combination of parameters (i1, j1, i2, j2, k). This avoids redundant computations and speeds up the recursive process.
5. Initialization and Execution: - Initialize m and n as the dimensions of the grid. - Start the recursive computation with getNext(0, 0, m - 1, n - 1, 3) to find the answer for covering the entire grid with three rectangles.

Complexity Analysis

• Time Complexity: The time complexity is O(m * n * (m + n)²), where m and n are the dimensions of the grid and k is the number of rectangles (3 in this case). This complexity arises because each recursive call explores subproblems defined by different combinations of i1, j1, i2, j2, k, and each unique subproblem is computed only once due to memoization.
• Space Complexity: The space complexity is O(m * n * k) due to the memoization map storing results for each unique subproblem.

Code Explanation

Overview

This JavaScript code calculates the minimum possible sum of the areas of three non-overlapping rectangles that cover all the 1's in a given 2D binary array grid.

Function: `getOne`

Purpose

The getOne function calculates the area of the smallest rectangle that can cover all the 1's in a given subgrid defined by the coordinates (i1, j1) to (i2, j2).

Detailed Explanation

function getOne(i1, j1, i2, j2, k) {
    let minx = Infinity;
    let maxx = -Infinity;
    let miny = Infinity;
    let maxy = -Infinity;

• Initializes four variables to keep track of the minimum and maximum x and y coordinates of 1's found in the subgrid. Initially, minx and miny are set to Infinity (a very large number) and maxx and maxy are set to -Infinity (a very small number).

for (let i = i1; i <= i2; i++) {
  for (let j = j1; j <= j2; j++) {
    if (grid[i][j] === 1) {
      minx = Math.min(minx, i);
      maxx = Math.max(maxx, i);
      miny = Math.min(miny, j);
      maxy = Math.max(maxy, j);
    }
  }
}

• Iterates through all cells in the subgrid defined by the coordinates (i1, j1) to (i2, j2).
• For each cell (i, j) that contains a 1, updates minx, maxx, miny, and maxy to track the bounds of the rectangle that encompasses all 1's in the subgrid.

if (minx === Infinity) {
  return 0;
}

• Checks if no 1's were found in the subgrid (minx is still Infinity). If so, it returns 0, indicating that the area of the rectangle is zero.

    return (maxx - minx + 1) * (maxy - miny + 1);
}

• Calculates and returns the area of the rectangle by using the formula (maxx - minx + 1) \times (maxy - miny + 1), which is the width times the height of the rectangle.

Function: `getNext`

Purpose

The getNext function calculates the minimum sum of the areas of k rectangles that can cover all the 1's in a given subgrid defined by the coordinates (i1, j1) to (i2, j2).

Detailed Explanation

function getNext(i1, j1, i2, j2, k) {
    let key = [i1, j1, i2, j2, k].join();
    if (map.has(key)) {
        return map.get(key);
    }

• Constructs a unique key for the current subproblem using the coordinates (i1, j1, i2, j2) and the number of rectangles k.
• Checks if the result for this subproblem is already stored in the map. If it is, it returns the cached result to avoid redundant calculations.

let output = Infinity;

• Initializes output to Infinity to ensure that the minimum sum of areas will be found.

if (k === 1) {
  output = getOne(i1, j1, i2, j2, k);
}

• If k is 1, calls getOne to calculate the area of a single rectangle that covers all 1's in the subgrid.

    else if (k === 2) {
        for (let i = i1; i < i2; i++) {
            output = Math.min(output, getNext(i1, j1, i, j2, 1) + getNext(i + 1, j1, i2, j2, 1));
        }
        for (let j = j1; j < j2; j++) {
            output = Math.min(output, getNext(i1, j1, i2, j, 1) + getNext(i1, j + 1, i2, j2, 1));
        }
    }

• If k is 2, iterates over all possible horizontal and vertical splits to divide the subgrid into two parts: - For horizontal splits, divides the grid along row i (from i1 to i2-1) and calculates the sum of the areas of two rectangles covering the top and bottom parts. - For vertical splits, divides the grid along column j (from j1 to j2-1) and calculates the sum of the areas of two rectangles covering the left and right parts. - Updates output with the minimum sum of these areas.

    else if (k === 3) {
        for (let i = i1; i < i2; i++) {
            output = Math.min(output, getNext(i1, j1, i, j2, 1) + getNext(i + 1, j1, i2, j2, 2));
            output = Math.min(output, getNext(i1, j1, i, j2, 2) + getNext(i + 1, j1, i2, j2, 1));
        }
        for (let j = j1; j < j2; j++) {
            output = Math.min(output, getNext(i1, j1, i2, j, 1) + getNext(i1, j + 1, i2, j2, 2));
            output = Math.min(output, getNext(i1, j1, i2, j, 2) + getNext(i1, j + 1, i2, j2, 1));
        }
    }

• If k is 3, iterates over all possible horizontal and vertical splits to divide the subgrid into two parts: - For horizontal splits, calculates the sum of the areas of one rectangle covering the top part and two rectangles covering the bottom part, and vice versa. - For vertical splits, calculates the sum of the areas of one rectangle covering the left part and two rectangles covering the right part, and vice versa. - Updates output with the minimum sum of these areas.

    map.set(key, output);
    return output;
}

• Stores the calculated minimum sum of areas for the current subproblem in map for memoization.
• Returns the output, which is the minimum sum of areas for k rectangles covering all 1's in the given subgrid.

Main Function

let m = grid.length;
let n = grid[0].length;

let ans = getNext(0, 0, m - 1, n - 1, 3);

return ans;

• Gets the dimensions of the grid (m and n).
• Calls getNext on the entire grid with k = 3 to find the minimum sum of areas of 3 rectangles.
• Returns the result.

Conclusion

The solution effectively uses dynamic programming with recursion and memoization to solve the problem of finding three non-overlapping rectangles with the minimum sum of their areas covering all 1s in the grid. By breaking down the problem into smaller subproblems and systematically computing optimal solutions, it ensures both correctness and efficiency in finding the desired result.

Code

C++

class Solution {
public:
    int minimumSum(vector>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        
        unordered_map memo;
        
        function getOne = [&](int i1, int j1, int i2, int j2, int k) {
            int minx = INT_MAX;
            int maxx = INT_MIN;
            int miny = INT_MAX;
            int maxy = INT_MIN;
            
            for (int i = i1; i <= i2; ++i) {
                for (int j = j1; j <= j2; ++j) {
                    if (grid[i][j] == 1) {
                        minx = min(minx, i);
                        maxx = max(maxx, i);
                        miny = min(miny, j);
                        maxy = max(maxy, j);
                    }
                }
            }
            
            if (minx == INT_MAX) {
                return 0;
            }
            
            return (maxx - minx + 1) * (maxy - miny + 1);
        };
        
        function getNext = [&](int i1, int j1, int i2, int j2, int k) {
            string key = to_string(i1) + "," + to_string(j1) + "," + to_string(i2) + "," + to_string(j2) + "," + to_string(k);
            if (memo.find(key) != memo.end()) {
                return memo[key];
            }
            
            int output = INT_MAX;
            
            if (k == 1) {
                output = getOne(i1, j1, i2, j2, k);
            } else if (k == 2) {
                for (int i = i1; i < i2; ++i) {
                    output = min(output, getNext(i1, j1, i, j2, 1) + getNext(i + 1, j1, i2, j2, 1));
                }
                for (int j = j1; j < j2; ++j) {
                    output = min(output, getNext(i1, j1, i2, j, 1) + getNext(i1, j + 1, i2, j2, 1));
                }
            } else if (k == 3) {
                for (int i = i1; i < i2; ++i) {
                    output = min(output, getNext(i1, j1, i, j2, 1) + getNext(i + 1, j1, i2, j2, 2));
                    output = min(output, getNext(i1, j1, i, j2, 2) + getNext(i + 1, j1, i2, j2, 1));
                }
                for (int j = j1; j < j2; ++j) {
                    output = min(output, getNext(i1, j1, i2, j, 1) + getNext(i1, j + 1, i2, j2, 2));
                    output = min(output, getNext(i1, j1, i2, j, 2) + getNext(i1, j + 1, i2, j2, 1));
                }
            }
            
            memo[key] = output;
            return output;
        };
        
        int ans = getNext(0, 0, m - 1, n - 1, 3);
        return ans;
    }
};

Python

class Solution:
    def minimumSum(self, grid: List[List[int]]) -> int:
        map = defaultdict(int)

        def get_one(i1, j1, i2, j2):
            minx = float('inf')
            maxx = float('-inf')
            miny = float('inf')
            maxy = float('-inf')

            for i in range(i1, i2 + 1):
                for j in range(j1, j2 + 1):
                    if grid[i][j] == 1:
                        minx = min(minx, i)
                        maxx = max(maxx, i)
                        miny = min(miny, j)
                        maxy = max(maxy, j)

            if minx == float('inf'):
                return 0

            return (maxx - minx + 1) * (maxy - miny + 1)

        def get_next(i1, j1, i2, j2, k):
            key = (i1, j1, i2, j2, k)
            if key in map:
                return map[key]

            output = float('inf')

            if k == 1:
                output = get_one(i1, j1, i2, j2)
            elif k == 2:
                for i in range(i1, i2):
                    output = min(output, get_next(i1, j1, i, j2, 1) + get_next(i + 1, j1, i2, j2, 1))
                for j in range(j1, j2):
                    output = min(output, get_next(i1, j1, i2, j, 1) + get_next(i1, j + 1, i2, j2, 1))
            elif k == 3:
                for i in range(i1, i2):
                    output = min(output, get_next(i1, j1, i, j2, 1) + get_next(i + 1, j1, i2, j2, 2))
                    output = min(output, get_next(i1, j1, i, j2, 2) + get_next(i + 1, j1, i2, j2, 1))
                for j in range(j1, j2):
                    output = min(output, get_next(i1, j1, i2, j, 1) + get_next(i1, j + 1, i2, j2, 2))
                    output = min(output, get_next(i1, j1, i2, j, 2) + get_next(i1, j + 1, i2, j2, 1))

            map[key] = output
            return output

        m = len(grid)
        n = len(grid[0])

        ans = get_next(0, 0, m - 1, n - 1, 3)

        return ans

Java

class Solution {
    public int minimumSum(int[][] grid) {
        HashMap map = new HashMap<>();

        int m = grid.length;
        int n = grid[0].length;

        int ans = getNext(0, 0, m - 1, n - 1, 3, grid, map);

        return ans;
    }

    private int getOne(int i1, int j1, int i2, int j2, int[][] grid, HashMap map) {
        int minx = Integer.MAX_VALUE;
        int maxx = Integer.MIN_VALUE;
        int miny = Integer.MAX_VALUE;
        int maxy = Integer.MIN_VALUE;

        for (int i = i1; i <= i2; i++) {
            for (int j = j1; j <= j2; j++) {
                if (grid[i][j] == 1) {
                    minx = Math.min(minx, i);
                    maxx = Math.max(maxx, i);
                    miny = Math.min(miny, j);
                    maxy = Math.max(maxy, j);
                }
            }
        }

        if (minx == Integer.MAX_VALUE) {
            return 0;
        }

        return (maxx - minx + 1) * (maxy - miny + 1);
    }

    private int getNext(int i1, int j1, int i2, int j2, int k, int[][] grid, HashMap map) {
        String key = i1 + "," + j1 + "," + i2 + "," + j2 + "," + k;
        if (map.containsKey(key)) {
            return map.get(key);
        }

        int output = Integer.MAX_VALUE;

        if (k == 1) {
            output = getOne(i1, j1, i2, j2, grid, map);
        } else if (k == 2) {
            for (int i = i1; i < i2; i++) {
                output = Math.min(output, getNext(i1, j1, i, j2, 1, grid, map) + getNext(i + 1, j1, i2, j2, 1, grid, map));
            }
            for (int j = j1; j < j2; j++) {
                output = Math.min(output, getNext(i1, j1, i2, j, 1, grid, map) + getNext(i1, j + 1, i2, j2, 1, grid, map));
            }
        } else if (k == 3) {
            for (int i = i1; i < i2; i++) {
                output = Math.min(output, getNext(i1, j1, i, j2, 1, grid, map) + getNext(i + 1, j1, i2, j2, 2, grid, map));
                output = Math.min(output, getNext(i1, j1, i, j2, 2, grid, map) + getNext(i + 1, j1, i2, j2, 1, grid, map));
            }
            for (int j = j1; j < j2; j++) {
                output = Math.min(output, getNext(i1, j1, i2, j, 1, grid, map) + getNext(i1, j + 1, i2, j2, 2, grid, map));
                output = Math.min(output, getNext(i1, j1, i2, j, 2, grid, map) + getNext(i1, j + 1, i2, j2, 1, grid, map));
            }
        }

        map.put(key, output);
        return output;
    }
}

JavaScript

/**
 * @param {number[][]} grid
 * @return {number}
 */
var minimumSum = function (grid) {
  let map = new Map();

  function getOne(i1, j1, i2, j2, k) {
    let minx = Infinity;
    let maxx = -Infinity;
    let miny = Infinity;
    let maxy = -Infinity;

    for (let i = i1; i <= i2; i++) {
      for (let j = j1; j <= j2; j++) {
        if (grid[i][j] === 1) {
          minx = Math.min(minx, i);
          maxx = Math.max(maxx, i);
          miny = Math.min(miny, j);
          maxy = Math.max(maxy, j);
        }
      }
    }

    if (minx === Infinity) {
      return 0;
    }

    return (maxx - minx + 1) * (maxy - miny + 1);
  }

  function getNext(i1, j1, i2, j2, k) {
    let key = [i1, j1, i2, j2, k].join();
    if (map.has(key)) {
      return map.get(key);
    }

    let output = Infinity;

    if (k === 1) {
      output = getOne(i1, j1, i2, j2, k);
    } else if (k === 2) {
      for (let i = i1; i < i2; i++) {
        output = Math.min(
          output,
          getNext(i1, j1, i, j2, 1) + getNext(i + 1, j1, i2, j2, 1)
        );
      }
      for (let j = j1; j < j2; j++) {
        output = Math.min(
          output,
          getNext(i1, j1, i2, j, 1) + getNext(i1, j + 1, i2, j2, 1)
        );
      }
    } else if (k === 3) {
      for (let i = i1; i < i2; i++) {
        output = Math.min(
          output,
          getNext(i1, j1, i, j2, 1) + getNext(i + 1, j1, i2, j2, 2)
        );
        output = Math.min(
          output,
          getNext(i1, j1, i, j2, 2) + getNext(i + 1, j1, i2, j2, 1)
        );
      }
      for (let j = j1; j < j2; j++) {
        output = Math.min(
          output,
          getNext(i1, j1, i2, j, 1) + getNext(i1, j + 1, i2, j2, 2)
        );
        output = Math.min(
          output,
          getNext(i1, j1, i2, j, 2) + getNext(i1, j + 1, i2, j2, 1)
        );
      }
    }

    map.set(key, output);
    return output;
  }

  let m = grid.length;
  let n = grid[0].length;

  let ans = getNext(0, 0, m - 1, n - 1, 3);

  return ans;
};

Go

func minimumSum(grid [][]int) int {
	m := len(grid)
	n := len(grid[0])

	// Memoization map
	memo := make(map[string]int)

	var getOne func(int, int, int, int, int) int
	getOne = func(i1, j1, i2, j2, k int) int {
		minx := math.MaxInt32
		maxx := math.MinInt32
		miny := math.MaxInt32
		maxy := math.MinInt32

		for i := i1; i <= i2; i++ {
			for j := j1; j <= j2; j++ {
				if grid[i][j] == 1 {
					if i < minx {
						minx = i
					}
					if i > maxx {
						maxx = i
					}
					if j < miny {
						miny = j
					}
					if j > maxy {
						maxy = j
					}
				}
			}
		}

		if minx == math.MaxInt32 {
			return 0
		}

		return (maxx - minx + 1) * (maxy - miny + 1)
	}

	var getNext func(int, int, int, int, int) int
	getNext = func(i1, j1, i2, j2, k int) int {
		key := fmt.Sprintf("%d,%d,%d,%d,%d", i1, j1, i2, j2, k)
		if val, ok := memo[key]; ok {
			return val
		}

		output := math.MaxInt32

		if k == 1 {
			output = getOne(i1, j1, i2, j2, k)
		} else if k == 2 {
			for i := i1; i < i2; i++ {
				output = min(output, getNext(i1, j1, i, j2, 1) + getNext(i+1, j1, i2, j2, 1))
			}
			for j := j1; j < j2; j++ {
				output = min(output, getNext(i1, j1, i2, j, 1) + getNext(i1, j+1, i2, j2, 1))
			}
		} else if k == 3 {
			for i := i1; i < i2; i++ {
				output = min(output, getNext(i1, j1, i, j2, 1) + getNext(i+1, j1, i2, j2, 2))
				output = min(output, getNext(i1, j1, i, j2, 2) + getNext(i+1, j1, i2, j2, 1))
			}
			for j := j1; j < j2; j++ {
				output = min(output, getNext(i1, j1, i2, j, 1) + getNext(i1, j+1, i2, j2, 2))
				output = min(output, getNext(i1, j1, i2, j, 2) + getNext(i1, j+1, i2, j2, 1))
			}
		}

		memo[key] = output
		return output
	}

	ans := getNext(0, 0, m-1, n-1, 3)
	return ans
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

C#

public class Solution
{
    public int MinimumSum(int[][] grid)
    {
        Dictionary map = new Dictionary();

        int m = grid.Length;
        int n = grid[0].Length;

        int ans = GetNext(0, 0, m - 1, n - 1, 3, grid, map);

        return ans;
    }

    private int GetOne(int i1, int j1, int i2, int j2, int[][] grid, Dictionary map)
    {
        int minx = int.MaxValue;
        int maxx = int.MinValue;
        int miny = int.MaxValue;
        int maxy = int.MinValue;

        for (int i = i1; i <= i2; i++)
        {
            for (int j = j1; j <= j2; j++)
            {
                if (grid[i][j] == 1)
                {
                    minx = Math.Min(minx, i);
                    maxx = Math.Max(maxx, i);
                    miny = Math.Min(miny, j);
                    maxy = Math.Max(maxy, j);
                }
            }
        }

        if (minx == int.MaxValue)
        {
            return 0;
        }

        return (maxx - minx + 1) * (maxy - miny + 1);
    }

    private int GetNext(int i1, int j1, int i2, int j2, int k, int[][] grid, Dictionary map)
    {
        string key = $\"{i1},{j1},{i2},{j2},{k}\";
        if (map.ContainsKey(key))
        {
            return map[key];
        }

        int output = int.MaxValue;

        if (k == 1)
        {
            output = GetOne(i1, j1, i2, j2, grid, map);
        }
        else if (k == 2)
        {
            for (int i = i1; i < i2; i++)
            {
                output = Math.Min(output, GetNext(i1, j1, i, j2, 1, grid, map) + GetNext(i + 1, j1, i2, j2, 1, grid, map));
            }
            for (int j = j1; j < j2; j++)
            {
                output = Math.Min(output, GetNext(i1, j1, i2, j, 1, grid, map) + GetNext(i1, j + 1, i2, j2, 1, grid, map));
            }
        }
        else if (k == 3)
        {
            for (int i = i1; i < i2; i++)
            {
                output = Math.Min(output, GetNext(i1, j1, i, j2, 1, grid, map) + GetNext(i + 1, j1, i2, j2, 2, grid, map));
                output = Math.Min(output, GetNext(i1, j1, i, j2, 2, grid, map) + GetNext(i + 1, j1, i2, j2, 1, grid, map));
            }
            for (int j = j1; j < j2; j++)
            {
                output = Math.Min(output, GetNext(i1, j1, i2, j, 1, grid, map) + GetNext(i1, j + 1, i2, j2, 2, grid, map));
                output = Math.Min(output, GetNext(i1, j1, i2, j, 2, grid, map) + GetNext(i1, j + 1, i2, j2, 1, grid, map));
            }
        }

        map[key] = output;
        return output;
    }
}