[LeetCode 1504] Count Submatrices With All Ones

문제 바로가기

Description

---

Given an m x n binary matrix mat, return the number of submatrices that have all ones.

Example 1

---

• Input: mat = [[1,0,1],[1,1,0],[1,1,0]]
• Output: 13
• Explanation:
  • There are 6 rectangles of side 1x1.
  • There are 2 rectangles of side 1x2.
  • There are 3 rectangles of side 2x1.
  • There is 1 rectangle of side 2x2.
  • There is 1 rectangle of side 3x1.
  • Total number of rectangles = 6 + 2 + 3 + 1 + 1 = 13.

Example 2

---

• Input: mat = [[0,1,1,0],[0,1,1,1],[1,1,1,0]]
• Output: 24
• Explanation:
  • There are 8 rectangles of side 1x1.
  • There are 5 rectangles of side 1x2.
  • There are 2 rectangles of side 1x3.
  • There are 4 rectangles of side 2x1.
  • There are 2 rectangles of side 2x2.
  • There are 2 rectangles of side 3x1.
  • There is 1 rectangle of side 3x2.
  • Total number of rectangles = 8 + 5 + 2 + 4 + 2 + 2 + 1 = 24.

Constraints

---

• 1 <= m, n <= 150
• mat[i][j] is either 0 or 1.

Hint

---

Hint 1

  For each row i, create an array nums where: if mat[i][j] == 0 then nums[j] = 0 else nums[j] = nums[j-1] +1.
	

Hint 2

  In the row i, number of rectangles between column j and k(inclusive) and ends in row i, is equal to SUM(min(nums[j, .. idx])) where idx go from j to k. Expected solution is O(n^3).
	

Code

---

내 제출

---

class Solution {
    public int numSubmat(int[][] mat) {
        int m = mat.length, n = mat[0].length;
        int[][] g = new int[m][n];
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (mat[i][j] == 1) {
                    g[i][j] = j == 0 ? 1 : 1 + g[i][j - 1];
                }
            }
        }
        int ans = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                int col = 1 << 30;
                for (int k = i; k >= 0 && col > 0; --k) {
                    col = Math.min(col, g[k][j]);
                    ans += col;
                }
            }
        }
        return ans;
    }
}

Runtime	Memory
7 ms	45.9 MB

다른 풀이

---

class Solution {
    public int numSubmat(int[][] mat) {
        int m = mat.length, n = mat[0].length;
        int[] h = new int[n];
        int cnt = 0;

        for(int i=0; i<m; i++) {
            for(int j=0; j<n; j++) {
                h[j] = mat[i][j] == 1 ? h[j] + 1 : 0;
            }

            for(int j=0; j<n; j++) {
                int mn = h[j];
                for(int k=j; k>=0 && mn>0; k--) {
                    mn = Math.min(mn, h[k]);
                    cnt += mn;
                }
            }
        }
        return cnt;
    }
}

Reference

---

• https://github.com/doocs/leetcode/blob/main/solution/1500-1599/1504.Count%20Submatrices%20With%20All%20Ones/Solution.java