This article has participated in the weekend study program, click the link to see the details of the link

Topic describes

This is 1074 on LeetCode. The number of elements and submatrices for the target value. Difficulty is difficult.

Tag: prefix and hash table

Given the matrix matrix and target value, return the number of non-empty submatrices whose summation of elements is equal to the target value.

The submatrices x1, y1, x2, y2 are the set of all elements matrix[x][y] that satisfy x1 <= x <= x2 and y1 <= y <= y2.

If the partial coordinates of (x1, y1, x2, y2) and (x1′, y1′, x2′, y2′) submatrices are different (e.g. X1 prime), so these two submatrices are also different.

 

Example 1:

Input: matrix = [[0,1,0],[1,1,1],[0,1,0]], target = 0Copy the code

Example 2:

Input: matrix = [[1,-1],[-1,1]], target = 0 Output: 5 Explanation: Two 1x2 submatrices, plus two 2x1 submatrices, plus one 2x2 submatrix.Copy the code

Example 3:

Input: matrix = [[904]], target = 0 Output: 0Copy the code

Tip:

  • 1 <= matrix.length <= 100
  • 1 <= matrix[0].length <= 100
  • -1000 <= matrix[i] <= 1000
  • –
    1 0 8 10^8     <= target <=
    1 0 8 10^8

Naive two-dimensional prefix sum

304. The sum of two dimensional prefixes is the same as the sum of two dimensional prefixes. Two dimensional region and retrieval – matrix immutable. In this case, the complexity of preprocessing prefixes is O(m∗n)O(m * n)O(m∗n).

Searching for all submatrices requires enumerating “upper left corner of the rectangle” and “lower right corner of the rectangle” with the complexity O(m2∗n2)O(m^2 * n^2)O(m2∗n2).

Therefore, the overall complexity is O(m2∗n2)O(m^2 * n^2)O(m2∗n2) if the problem is used as a two-dimensional prefix and template problem.

The data range is 10210^2102, and the amount of computation is 10810^8108, which is on the timeout edge, but when we enumerate “upper left corner of rectangle” (I,j)(I,j)(I,j), We only need to search the point (p,q)(p,q)(p,q) located at the lower right of (I,j)(I,j)(I,j) as “the lower right corner of the rectangle”, so in fact, we cannot take m2∗n2m^2 * n^2m2∗n2, But there is still a timeout risk (2021/05/29 Java test passed).

Code:

class Solution {
    public int numSubmatrixSumTarget(int[][] mat, int t) {
        int n = mat.length, m = mat[0].length;
        int[][] sum = new int[n + 1][m + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + mat[i - 1][j - 1]; }}int ans = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                for (int p = 1; p <= i; p++) {
                    for (int q = 1; q <= j; q++) {
                        if (sum[i][j] - sum[p - 1][j] - sum[i][q - 1] + sum[p - 1][q - 1] == t) ans++; }}}}returnans; }}Copy the code
  • O(m2∗n2)O(m^2 * n^2)O(m2∗n2)
  • Space complexity: O(m∗n)O(M * n)O(m∗n)

Optimized enumeration + hash table

The above analysis is to determine a submatrix from the “point”. In the case of NNN and MMM of the same order, the complexity is O(n4)O(n^4)O(n4).

In fact, we can determine a submatrix in terms of edges, by enumerating three edges, and then speeding up the process of finding a fourth edge, which reduces the complexity to O(n3)O(n^3)O(n3).

This analytical idea is in363. The rectangular region does not exceed the sum of the largest values of KI told you in detail, if you don’t remember, you can look it up. And this is kind of a simplified version of that problem, where we just have to find the matrix and theta
t a r g e t target , so you only need to use “hash table” to record the occurrence of the value, and in363. The rectangular region does not exceed the maximum sum of values of KIn, we need to find and not exceed
k k The largest submatrix of, therefore also involves “ordered set + dichotomy”.

Specifically, we still need to preprocess a two-dimensional prefix sum. Then, the “upper and lower boundary of the submatrix” is determined by enumeration. In the process of constantly moving the “right boundary of the submatrix” to the right boundary of the original matrix, the matrix sum of the journey from the “right boundary of the submatrix” to the “left boundary of the original matrix” is stored in the hash table (because the quantity needs to be counted, the storage format is {” area “:” number of occurrences “}). Then the left boundary of the submatrix of the target is found by the principle of inclusion and exclusion.

Assuming that the current “upper and lower boundary of the submatrix” is fixed, when enumerating to a “right boundary of the submatrix”, we first calculate the matrix and curcurcur formed by the “right boundary of the submatrix” and the “left boundary of the original matrix” through the two-dimensional prefix sum. Since we want to find the matrix and the submatrix targettargettarget, that is, we want to find a “left boundary of the submatrix” so that the matrix and satisfy the requirements, which is equivalent to finding an XXX from the “hash table”, Make cur−x=targetcur -x =targetcur −x=target, which is an O(1)O(1)O(1) operation.

Code:

class Solution {
    public int numSubmatrixSumTarget(int[][] mat, int t) {
        int n = mat.length, m = mat[0].length;
        int[][] sum = new int[n + 1][m + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + mat[i - 1][j - 1]; }}int ans = 0;
        for (int top = 1; top <= n; top++) {
            for (int bot = top; bot <= n; bot++) {
                int cur = 0;
                Map<Integer, Integer> map = new HashMap<>();
                for (int r = 1; r <= m; r++) {
                    cur = sum[bot][r] - sum[top - 1][r];
                    if (cur == t) ans++;
                    if (map.containsKey(cur - t)) ans += map.get(cur - t);
                    map.put(cur, map.getOrDefault(cur, 0) + 1); }}}returnans; }}Copy the code
  • O(m∗n2)O(m * n^2)O(m∗n2)
  • Space complexity: O(m∗n)O(M * n)O(m∗n)

The advanced

  1. [Time complexity] In the above solution, we adopt the method of fixing the upper and lower boundaries, moving the right boundary, and finding the left boundary through the hash table. The complexity is O(m∗n2)O(M * n^2)O(m∗n2); It is also possible to fix the left and right boundaries, move the lower boundary, and find the upper boundary through the hash table. The complexity is O(m2∗n)O(m^2 * n)O(m2∗n). So how can we tweak the code to maximize the optimization effect of the hash table? And what’s the complexity?

  2. [Spatial complexity] The bottleneck of our spatial complexity lies in “two-dimensional prefix sum”. However, it is noted that no matter we adopt the method of “fixing upper and lower boundaries” or “fixing left and right boundaries”, the direction of scanning the original matrix is still fixed. Therefore, can we not preprocess “two-dimensional prefix sum”? To reduce the space complexity to O (Max ⁡ (n, m)) O (\ Max (n, m)) O (Max (n, m))?

The answer to both questions can be found in the sum of the largest values of the rectangle region not exceeding K.

The last

This is the No.1074 of our “Brush through LeetCode” series, which started on 2021/01/01. There are 1916 topics in LeetCode by the start date, some of which have locks.

In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.

In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour… .

In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.