Today I have done leetcode's August LeetCoding Challenge with cpp.

August LeetCoding Challenge 23

Description

Find the Minimum Area to Cover All Ones II

You are given a 2D binary array grid. You need to find 3 non-overlapping rectangles having non-zero areas with horizontal and vertical sides such that all the 1's in grid lie inside these rectangles.

Return the minimum possible sum of the area of these rectangles.

Note that the rectangles are allowed to touch.

Example 1:

Example 2:

Constraints:

• 1 <= grid.length, grid[i].length <= 30
• grid[i][j] is either 0 or 1.
• The input is generated such that there are at least three 1's in grid.

Solution

class Solution {
public:
  // Function to calculate the minimum area of rectangle enclosing all ones in a submatrix 
  int minimumArea(vector<vector<int>>& grid, int mminX, int mmaxX, int mminY, int mmaxY) {
    int minX = 40;
    int minY = 40;
    int maxX = -1;
    int maxY = -1;
    bool found = false;
    for(int i = mminX; i <= mmaxX; i++) {  
      for(int j = mminY; j <= mmaxY; j++){
        if(!grid[i][j]) continue;
        minX = min(minX, i);
        maxX = max(maxX, i);
        maxY = min(maxY, j);
        minY = max(minY, j);
        found = true;
      }
    }
    return found ? ((maxX - minX + 1) * (minY - maxY + 1)) : 0;
  }
  
  int minimumSum(vector<vector<int>>& grid) {
    int x = grid.size();
    int y = grid.front().size();
    int answer = INT_MAX;
    int one, two, three;

    /*
    -------------
    |  (1)  |
    |       |
    -------------
    | (2) | (3) |
    |   |   |
    -------------
    */
    for(int i = 0; i < x; i++){
      one = minimumArea(grid, 0, i, 0, y - 1);
      for(int j = 0; j < y; j++){
        two = minimumArea(grid, i + 1, x - 1, 0, j);
        three = minimumArea(grid, i + 1, x - 1, j+1, y-1);
        answer = min(answer, one + two + three);
      }
    }
    
    /*
    -------------
    |   | (2) |
    |   |   |
      (1) -------
    |   |   |
    |   | (3) |
    -------------
    */
    for(int j = 0; j < y; j++){
      one = minimumArea(grid, 0, x-1, 0, j);
      for(int i = 0; i < x; i++){
        two = minimumArea(grid, 0, i, j+1, y-1);
        three = minimumArea(grid, i + 1, x - 1, j+1, y-1);
        answer = min(answer, one + two + three);
      }
    }
    
    /*
    -------------
    |   |   |
    | (2) |   |
    ------- (1) |
    |   |   |
    | (3) |   |
    -------------
    */
    for(int j = y-1; j >= 0; j--){
      one = minimumArea(grid, 0, x-1, j+1, y-1);
      for(int i = 0; i < x; i++){
        two = minimumArea(grid, 0, i, 0, j);
        three = minimumArea(grid, i + 1, x - 1, 0, j);
        answer = min(answer, one + two + three);
      }
    }
        
        
    /*
    -------------
    | (2) | (3) |
    |   |   |
    ------------
    |       |
    |  (1)  |
    -------------
    */
    for(int i = x-1; i >= 0; i--){
      one = minimumArea(grid, i+1, x-1, 0, y - 1);
      for(int j = 0; j < y; j++){
        two = minimumArea(grid, 0, i, 0, j);
        three = minimumArea(grid, 0, i, j+1, y-1);
        answer = min(answer, one + two + three);
      }
    }
    
    /*
    -------------
    |  (1)  |
    -------------
    |  (2)  |
    -------------
    |  (3)  |
    -------------
    */
    for(int i = 0; i < x; i++){
      for(int j = i+1; j < x; j++){
        one = minimumArea(grid, 0, i, 0, y-1);
        two = minimumArea(grid, i+1, j, 0, y-1);
        three = minimumArea(grid, j+1, x-1, 0, y-1);
        answer = min(answer, one + two + three);
      }
    }
    
     /*
    -------------
    |   |   |   |
    |   |   |   |
    |(1)|(2)|(3)|
    |   |   |   |
    |   |   |   |
    -------------
    */    
    for(int i = 0; i < y; i++){
      for(int j = i + 1; j < y; j++){
        one = minimumArea(grid, 0, x - 1, 0, i);
        two = minimumArea(grid, 0, x - 1, i + 1, j);
        three = minimumArea(grid, 0, x - 1, j + 1, y - 1);
        answer = min(answer, one + two + three);
      }
    }
    
    return answer;
  }
};