[LeetCode 3195] Find the Minimum Area to Cover All Ones I

문제 바로가기

Description

---

You are given a 2D binary array grid. Find a rectangle with horizontal and vertical sides with the smallest area, such that all the 1’s in grid lie inside this rectangle.

Return the minimum possible area of the rectangle.

Example 1

---

• Input: grid = [[0,1,0],[1,0,1]]
• Output: 6
• Explanation:
  • 
  • The smallest rectangle has a height of 2 and a width of 3, so it has an area of 2 * 3 = 6.

Example 2

---

• Input: grid = [[1,0],[0,0]]
• Output: 1
• Explanation:
  • 
  • The smallest rectangle has both height and width 1, so its area is 1 * 1 = 1.

Constraints

---

• 1 <= grid.length, grid[i].length <= 1000
• grid[i][j] is either 0 or 1.
• The input is generated such that there is at least one 1 in grid.

Hint

---

Hint 1

  Find the minimum and maximum coordinates of a cell with a value of 1 in both directions.
	

Code

---

내 제출

---

class Solution {
    public int minimumArea(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int x1 = m, y1 = n;
        int x2 = 0, y2 = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 1) {
                    x1 = Math.min(x1, i);
                    y1 = Math.min(y1, j);
                    x2 = Math.max(x2, i);
                    y2 = Math.max(y2, j);
                }
            }
        }
        return (x2 - x1 + 1) * (y2 - y1 + 1);
    }
}

Runtime	Memory
5 ms	196.8 MB

다른 풀이

---

class Solution {
    int groupLength(boolean[] arr) {
        int first = -1, last = -1;

        for (int i = 0; i < arr.length; i++) {
            if (arr[i]) {
                if (first == -1)
                    first = i;

                last = i;
            }
        }

        if (first == -1)
            return 0;

        return last - first + 1;
    }

    public int minimumArea(int[][] grid) {
        int n = grid.length, m = grid[0].length;
        boolean[] row = new boolean[n];
        boolean[] col = new boolean[m];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 1) {
                    row[i] = true;
                    col[j] = true;
                }
            }
        }

        return groupLength(row) * groupLength(col);
    }
}

Reference

---

• https://github.com/doocs/leetcode/blob/main/solution/3100-3199/3195.Find%20the%20Minimum%20Area%20to%20Cover%20All%20Ones%20I/Solution.java