1074. Number of Submatrices That Sum to Target

leetcode hard

#array#csharp#hard#hash-table#leetcode#matrix#prefix-sum#string

Task

Дана матрица и целевое значение. Верните количество непустых подматриц, сумма элементов которых равна целевому значению.

Подматрица x1, y1, x2, y2 — это набор всех ячеек matrix[x][y] с x1 <= x <= x2 и y1 <= y <= y2.

Две подматрицы (x1, y1, x2, y2) и (x1', y1', x2', y2') различны, если у них есть какая-то различающаяся координата: например, если x1 != x1'.

Пример:

Input: matrix = [[0,1,0],[1,1,1],[0,1,0]], target = 0

Output: 4

Explanation: The four 1x1 submatrices that only contain 0.

C# solution

matched/original

public class Solution {
    public int NumSubmatrixSumTarget(int[][] matrix, int target) {
        int r = matrix.Length, c = matrix[0].Length;
        int[,] ps = new int[r + 1, c + 1];
        
        for (int i = 1; i <= r; ++i) {
            for (int j = 1; j <= c; ++j) {
                ps[i, j] = ps[i - 1, j] + ps[i, j - 1] - ps[i - 1, j - 1] + matrix[i - 1][j - 1];
            }
        }
        
        int count = 0;
        
        for (int r1 = 1; r1 <= r; ++r1) {
            for (int r2 = r1; r2 <= r; ++r2) {
                Dictionary<int, int> h = new Dictionary<int, int>();
                h[0] = 1;
                for (int col = 1; col <= c; ++col) {
                    int currSum = ps[r2, col] - ps[r1 - 1, col];
                    if (h.ContainsKey(currSum - target)) {
                        count += h[currSum - target];
                    }
                    if (h.ContainsKey(currSum)) {
                        h[currSum]++;
                    } else {
                        h[currSum] = 1;
                    }
                }
            }
        }
        
        return count;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int NumSubmatrixSumTarget(int[][] matrix, int target) {
        int r = matrix.size(), c = matrix[0].size();
        int[,] ps = new int[r + 1, c + 1];
        
        for (int i = 1; i <= r; ++i) {
            for (int j = 1; j <= c; ++j) {
                ps[i, j] = ps[i - 1, j] + ps[i, j - 1] - ps[i - 1, j - 1] + matrix[i - 1][j - 1];
            }
        }
        
        int count = 0;
        
        for (int r1 = 1; r1 <= r; ++r1) {
            for (int r2 = r1; r2 <= r; ++r2) {
                unordered_map<int, int> h = new unordered_map<int, int>();
                h[0] = 1;
                for (int col = 1; col <= c; ++col) {
                    int currSum = ps[r2, col] - ps[r1 - 1, col];
                    if (h.count(currSum - target)) {
                        count += h[currSum - target];
                    }
                    if (h.count(currSum)) {
                        h[currSum]++;
                    } else {
                        h[currSum] = 1;
                    }
                }
            }
        }
        
        return count;
    }
}

Java solution

matched/original

class Solution {
  public int numSubmatrixSumTarget(int[][] matrix, int target) {
    int r = matrix.length, c = matrix[0].length;

    int[][] ps = new int[r + 1][c + 1];
    for (int i = 1; i < r + 1; ++i) {
      for (int j = 1; j < c + 1; ++j) {
        ps[i][j] = ps[i - 1][j] + ps[i][j - 1] - ps[i - 1][j - 1] + matrix[i - 1][j - 1];
      }
    }

    int count = 0, currSum;
    Map<Integer, Integer> h = new HashMap();
    for (int r1 = 1; r1 < r + 1; ++r1) {
      for (int r2 = r1; r2 < r + 1; ++r2) {
        h.clear();
        h.put(0, 1);
        for (int col = 1; col < c + 1; ++col) {
          currSum = ps[r2][col] - ps[r1 - 1][col];
          count += h.getOrDefault(currSum - target, 0);
          h.put(currSum, h.getOrDefault(currSum, 0) + 1);
        }
      }
    }

    return count;
  }
}

JavaScript solution

matched/original

var numSubmatrixSumTarget = function(matrix, target) {
    const r = matrix.length, c = matrix[0].length;
    const ps = Array.from({ length: r + 1 }, () => Array(c + 1).fill(0));
    
    for (let i = 1; i <= r; i++) {
        for (let j = 1; j <= c; j++) {
            ps[i][j] = ps[i - 1][j] + ps[i][j - 1] - ps[i - 1][j - 1] + matrix[i - 1][j];
        }
    }
    
    let count = 0;
    
    for (let r1 = 1; r1 <= r; r1++) {
        for (let r2 = r1; r2 <= r; r2++) {
            const h = {0: 1};
            for (let col = 1; col <= c; col++) {
                const currSum = ps[r2][col] - ps[r1 - 1][col];
                if (h[currSum - target]) {
                    count += h[currSum - target];
                }
                h[currSum] = (h[currSum] || 0) + 1;
            }
        }
    }
    
    return count;
};

Go solution

matched/original

func numSubmatrixSumTarget(matrix [][]int, target int) int {
    r, c := len(matrix), len(matrix[0])
    ps := make([][]int, r+1)
    for i := range ps {
        ps[i] = make([]int, c+1)
    }
    
    for i := 1; i <= r; i++ {
        for j := 1; j <= c; j++ {
            ps[i][j] = ps[i-1][j] + ps[i][j-1] - ps[i-1][j-1] + matrix[i-1][j]
        }
    }
    
    count := 0
    
    for r1 := 1; r1 <= r; r2++ {
        for r2 := r1; r2 <= r; r2++ {
            h := map[int]int{0: 1}
            for col := 1; col <= c; col++ {
                currSum := ps[r2][col] - ps[r1-1][col]
                if count, ok := h[currSum-target]; ok {
                    count += count
                }
                h[currSum]++
            }
        }
    }
    
    return count
}

Explanation

Algorithm

Инициализируйте результат: count = 0. Вычислите количество строк: r = len(matrix) и количество столбцов: c = len(matrix[0]). Вычислите двумерную префиксную сумму ps, выделив еще одну строку и еще один столбец для нулевых значений.

Итерируйте по строкам: r1 от 1 до r и r2 от r1 до r. Внутри этого двойного цикла фиксируйте левые и правые границы строк и инициализируйте хэш-таблицу для хранения префиксных сумм. Итерируйте по столбцам от 1 до c + 1, вычислите текущую префиксную сумму 1D curr_sum и увеличьте count на количество матриц, сумма которых равна target.

Добавьте текущую префиксную сумму 1D в хэш-таблицу. Когда все итерации завершены, верните count.

😎