Matrix Block Sum Solution In C++/Python/java/JS
Matrix Block Sum Problem
Given a m x n matrix mat and an integer k, return a matrix answer where each answer[i][j] is the sum of all elements mat[r][c] for:
i - k <= r <= i + k,
j - k <= c <= j + k, and
(r, c) is a valid position in the matrix.
Explanation
We are given a matrix filled with numbers. Our task is to create a new matrix where each cell contains the sum of all the numbers within a certain distance (k) from that cell in the original matrix. This distance is defined by how many steps you can move up, down, left, or right from the cell.
Example
Input: mat = [[1,2,3], [4,5,6], [7,8,9]], k = 1
Output: [[12,21,16], [27,45,33], [24,39,28]]
Explanation:
For each cell in the matrix, we sum all the elements within a distance of 1 (k=1) from that cell. Let's break down a few cells:
- For the cell at (0,0), we consider the cells (0,0), (0,1), (1,0), and (1,1), which sum up to 1+2+4+5 = 12.
- For the cell at (1,1), we consider the cells (0,0), (0,1), (0,2), (1,0), (1,1), (1,2), (2,0), (2,1), and (2,2), which sum up to 1+2+3+4+5+6+7+8+9 = 45.
We repeat this process for each cell to get the final output matrix.
Input: mat = [[1,2,3], [4,5,6], [7,8,9]], k = 2
Output: [[45,45,45], [45,45,45], [45,45,45]]
Explanation:
For each cell in the matrix, we sum all the elements within a distance of 2 (k=2) from that cell. Let's break down a few cells:
For the cell at (0,0):
- We consider all cells within 2 steps in all directions.
- The cells we consider are: (0,0), (0,1), (0,2), (1,0), (1,1), (1,2), (2,0), (2,1), (2,2).
- These cells are all within the bounds of the matrix.
- The sum of these cells is: 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 = 45.
We repeat this process for each cell to get the final output matrix.
Constraints
- m == mat.length
- n == mat[i].length
- 1 <= m, n, k <= 100
- 1 <= mat[i][j] <= 100
"Matrix Block Sum” problem can be solved using different approaches, such as Brute Force and Optimized iteration. Each approach has its advantages and trade-offs in terms of speed and memory usage. Let's explore both of them!
Brute Force Approach
Intuition
The first thought that comes to our mind is to calculate the sum of all elements within the specified distance (k) for each cell in the matrix. We can do this by iterating over each cell and summing the values of all cells within the k-distance neighborhood. This approach ensures that we consider every possible cell combination within the given range.
Let's Understand with an Example
Example Matrix =
[[1, 2, 3, 4],
[5, 6, 7, 8],
[9, 10, 11, 12],
[13, 14, 15, 16]],
k = 2.
Given k=2, each cell sums all numbers within a 2-step radius in all directions. If a cell's neighborhood extends beyond the matrix boundaries, we only consider valid cells within bounds.
Let's break down a few cells:
- For the cell at (0,0), we consider the cells (0,0), (0,1), (0,2), (1,0), (1,1), (1,2), (2,0), (2,1), and (2,2), which sum up to 1 + 2 + 3 + 5 + 6 + 7 + 9 + 10 + 11 = 54.
- For the cell at (1,2), we consider the cells (0,0), (0,1), (0,2), (0,3), (1,0), (1,1), (1,2), (1,3), (2,0), (2,1), (2,2), (2,3), (3,0), (3,1), (3,2), and (3,3), which sum up to 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10 + 11 + 12 + 13 + 14 + 15 + 16 = 136.
Boundary Check: We only consider cells where both row and column indices are within the valid matrix bounds (0 ≤ i< m,0 ≤ j <n).
We repeat this process for each cell to get the final output matrix and return it.
Matrix Block Sum Algorithm
- Iterate over each cell in the matrix.
- For each cell, calculate the sum of all elements within a distance k.
- Store this sum in the corresponding cell of the new matrix.
- Return the new matrix.
Approach
Initialize Variables
- Create a new matrix answer of the same size as the input matrix mat.
- Get the dimensions of the matrix m (number of rows) and n (number of columns).
Process Each Cell
- Loop through each cell in the matrix using two nested loops (one for rows and one for columns).
- For each cell (i, j), initialize a variable sum to 0. This will store the sum of all valid neighboring cells.
Calculate the Sum
- Loop through the neighboring cells within the distance kk using two more nested loops.
- For each neighboring cell (r, c), check if it is within the bounds of the matrix.
- If the cell (r, c) is within bounds, add its value to sum.
Store the Result
- After calculating the sum for the cell (i, j), store this sum in the answer matrix at the same position (i, j).
Return the Result
- After processing all cells, return the answer matrix.
Dry-Run
General Setup:
Input Matrix: [[2, 3, 4], [5, 6, 7], [8, 9, 10]], k = 1
Output answer = [[16, 27, 20], [33, 54, 39], [30, 48, 34]]
Objective: To Find a new matrix where each cell contains the sum of all elements within a distance k from that cell in the original matrix.
Explanation
For cell (0,0):
• Consider cells within distance 1: (0,0), (0,1), (1,0), (1,1).
• Sum = 2 + 3 + 5 + 6 = 16.
• Store 16 in answer[0][0].
For cell (0,1):
• Consider cells within distance 1: (0,0), (0,1), (0,2), (1,0), (1,1), (1,2).
• Sum = 2 + 3 + 4 + 5 + 6 + 7 = 27.
• Store 27 in answer[0][1].
For cell (0,2):
• Consider cells within distance 1: (0,1), (0,2), (1,1), (1,2).
• Sum = 3 + 4 + 6 + 7 = 20.
• Store 20 in answer[0][2].
For cell (1,0):
• Consider cells within distance 1: (0,0), (0,1), (1,0), (1,1), (2,0), (2,1).
• Sum = 2 + 3 + 5 + 6 + 8 + 9 = 33.
• Store 33 in answer[1][0].
For cell (1,1):
• Consider cells within distance 1: (0,0), (0,1), (0,2), (1,0), (1,1), (1,2), (2,0), (2,1), (2,2).
• Sum = 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10 = 54.
• Store 54 in answer[1][1].
For cell (1,2):
• Consider cells within distance 1: (0,1), (0,2), (1,1), (1,2), (2,1), (2,2).
• Sum = 3 + 4 + 6 + 7 + 9 + 10 = 39.
• Store 39 in answer[1][2].
For cell (2,0):
• Consider cells within distance 1: (1,0), (1,1), (2,0), (2,1).
• Sum = 5 + 6 + 8 + 9 = 30.
• Store 30 in answer[2][0].
For cell (2,1):
• Consider cells within distance 1: (1,0), (1,1), (1,2), (2,0), (2,1), (2,2).
• Sum = 5 + 6 + 7 + 8 + 9 + 10 = 48.
• Store 48 in answer[2][1].
For cell (2,2):
• Consider cells within distance 1: (1,1), (1,2), (2,1), (2,2).
• Sum = 6 + 7 + 9 + 10 = 34.
• Store 34 in answer [2][2].
Final answer matrix:
[[16, 27, 20],
[33, 54, 39],
[30, 48, 34]]
Matrix Block Sum solution
Let now discover the codes for Matrix Block Sum problem in C++, Java, Python, and JavaScript
Brute Force Code in all Languages.
1. Matrix Block Sum solution in C++ Try on Compiler
class Solution {
public:
// Function to compute matrix block sum
vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) {
// Get the number of rows in the matrix
int m = mat.size();
// Get the number of columns in the matrix
int n = mat[0].size();
// Initialize the answer matrix
vector<vector<int>> answer(m, vector<int>(n, 0));
// Compute the block sum for each element in the matrix
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
// Initialize sum for the current block
int sum = 0;
// Iterate over the block of elements
for (int r = max(0, i - k); r <= min(m - 1, i + k); r++) {
for (int c = max(0, j - k); c <= min(n - 1, j + k); c++) {
sum += mat[r][c];
}
}
// Store the computed sum in the answer matrix
answer[i][j] = sum;
}
}
// Return the final answer matrix
return answer;
}
};2. Matrix Block Sum solution in Java Try on Compiler
class Solution {
// Function to compute matrix block sum
public int[][] matrixBlockSum(int[][] mat, int k) {
// Get the number of rows in the matrix
int m = mat.length;
// Get the number of columns in the matrix
int n = mat[0].length;
// Initialize the answer matrix
int[][] answer = new int[m][n];
// Compute the block sum for each element in the matrix
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
// Initialize sum for the current block
int sum = 0;
// Iterate over the block of elements
for (int r = Math.max(0, i - k); r <= Math.min(m - 1, i + k); r++) {
for (int c = Math.max(0, j - k); c <= Math.min(n - 1, j + k); c++) {
sum += mat[r][c];
}
}
// Store the computed sum in the answer matrix
answer[i][j] = sum;
}
}
// Return the final answer matrix
return answer;
}
}3. Matrix Block Sum solution in Python Try on Compiler
class Solution:
# Function to compute matrix block sum
def matrixBlockSum(self, mat: List[List[int]], k: int) -> List[List[int]]:
# Get the number of rows in the matrix
m, n = len(mat), len(mat[0])
# Initialize the answer matrix
answer = [[0] * n for _ in range(m)]
# Compute the block sum for each element in the matrix
for i in range(m):
for j in range(n):
# Initialize sum for the current block
total = 0
# Iterate over the block of elements
for r in range(max(0, i - k), min(m, i + k + 1)):
for c in range(max(0, j - k), min(n, j + k + 1)):
total += mat[r][c]
# Store the computed sum in the answer matrix
answer[i][j] = total
# Return the final answer matrix
return answer4. Matrix Block Sum solution in JavaScript Try on Compiler
/**
* @param {number[][]} mat
* @param {number} k
* @return {number[][]}
*/
var matrixBlockSum = function(mat, k) {
// Get the number of rows in the matrix
const m = mat.length;
// Get the number of columns in the matrix
const n = mat[0].length;
// Initialize the answer matrix
const answer = Array.from({ length: m }, () => Array(n).fill(0));
// Compute the block sum for each element in the matrix
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
let sum = 0;
for (let r = Math.max(0, i - k); r <= Math.min(m - 1, i + k); r++) {
for (let c = Math.max(0, j - k); c <= Math.min(n - 1, j + k); c++) {
sum += mat[r][c];
}
}
answer[i][j] = sum;
}
}
return answer;
};
Complexity Analysis of the problem
Time Complexity: O(m * n * (2k+1) * (2k+1))
The brute force approach utilizes four nested loops, leading to a time complexity of O(m×n×(2k+1)×(2k+1)), where m is the number of rows and n is the number of columns in the matrix. Here’s a detailed breakdown:
- Outer Loop for Rows: The outermost loop iterates over each row of the matrix, contributing O(m).
- Inner Loop for Columns: The second loop iterates over each column of the matrix, contributing O(n).
- Loop for Neighbor Rows: The third loop iterates over the neighboring rows within the distance k, contributing O(2k+1).
- Loop for Neighbor Columns: The fourth loop iterates over the neighboring columns within the distance k, contributing O(2k+1).
Inside these loops, we check if each neighboring cell is within the bounds of the matrix and add its value to the sum if it is. This operation is O(1) for each cell.
Thus, the total time complexity becomes:
O(m×n×(2k+1)×(2k+1))
This is highly inefficient for large matrices, as the execution time increases rapidly with the input size.
Space Complexity: O(m*n)
- Auxiliary space Complexity refers to the extra space required by an algorithm other than the input space. In this case, it is O(m×n) because we create an additional matrix answer of the same size as the input matrix mat. We also use a few integer variables to track indices and sums, but these are negligible compared to the space used by the answer matrix.
- Total space Complexity:
The total space complexity considers the space used by both the input matrix and the output matrix. Since we create an additional matrix answer of the same size as the input matrix mat, the overall space complexity is O(m×n), where mm is the number of rows and n is the number of columns.
Overall space complexity: O(m*n).
Looking at the constraints where the size of the matrix can be up to 100 × 100, the brute force approach results in Time Limit Exceeded since calculating the sum for each cell using nested loops takes O(m×n×(2k+1)×(2k+1)) time in the worst case, which is highly inefficient. This approach is not suitable for large matrices, and an interviewer would likely expect a more optimal solution. Let's explore a more efficient approach.
Optimal Approach
Intuition
The problem requires calculating the sum of elements in a defined submatrix around each position (i, j) within a given k distance.
In the brute force approach, for each cell (i, j), we iterate through all cells within the k range and sum them up. This means we repeatedly sum overlapping areas multiple times, leading to an inefficient solution.
Illustration of Repeated Calculations
Consider a 4x4 matrix with k=1:
For cell (1,2), we again sum an overlapping region, repeating calculations unnecessarily.
If we precompute sum information efficiently, we can avoid redundant calculations, making our approach significantly faster. This leads us to the Prefix Sum Matrix technique.
What is a Prefix Sum Matrix?
A prefix sum matrix is a matrix that helps quickly compute the sum of any submatrix in constant time O(1). It stores cumulative sums such that any element prefixSum[i][j] represents the sum of all elements in the submatrix from (0,0) to (i-1, j-1).
Let's take a 2×2 matrix A:
A=
[[1, 2],
[3, 4]]
We will construct a prefix sum matrix of size (3×3) to handle 1-based indexing properly.
Prefix Sum Matrix (3×3):
P=
[[0, 0, 0],
[0, 1, 3],
[0, 4, 10]]
Understanding the Prefix Sum Matrix:
Each element P[i][j] represents the sum of all elements in A from (0,0) to (i-1, j-1).
- P[1][1] = 1 → It stores the sum of all elements from the top-left (0,0) to (0,0), which is just 1.
- P[1][2] = 3 → Sum of first row (1 + 2).
- P[2][1] = 4 → Sum of first column (1 + 3).
- P[2][2] = 10 → Sum of all elements in A (1 + 2 + 3 + 4).
This prefix sum matrix allows O(1) submatrix sum queries, making computations fast.
How Do We Compute Prefix Sum Matrix?
For any index (i-1, j-1) in the original matrix, where 0 ≤ i-1 < m and 0 ≤ j-1 < n, we calculate the prefix sum at (i, j) in the prefix sum matrix as follows:
For a given matrix mat, the prefix sum prefixSum[i][j] is computed as:
prefixSum[i][j] = mat[i-1][j-1] + prefixSum[i-1][j] + prefixSum[i][j-1] - prefixSum[i-1][j-1]
Explanation of the Formula
- mat[i-1][j-1]: Adds the current cell value from the original matrix.
- prefixSum[i-1][j]: Adds the sum of all elements above the current cell.
- prefixSum[i][j-1]: Adds the sum of all elements to the left of the current cell.
- prefixSum[i-1][j-1]: Subtracts the sum of the top-left overlapping region (since it was added twice in the previous two steps).
This ensures that prefixSum[i][j] correctly represents the sum of all elements from (0,0) to (i-1, j-1).
Using the Prefix Sum Matrix to Compute Answer Matrix
Now, using the precomputed prefix sum matrix, we can calculate the sum for any submatrix (r1, c1) -> (r2, c2) efficiently:
sum = prefixSum[r2+1][c2+1] - prefixSum[r1][c2+1] - prefixSum[r2+1][c1] + prefixSum[r1][c1]
Explanation of the Formula
- prefixSum[r2+1][c2+1]: Sum of all elements from (0,0) to (r2,c2).
- prefixSum[r1][c2+1]: Subtracts the sum of elements above the submatrix.
- prefixSum[r2+1][c1]: Subtracts the sum of elements to the left of the submatrix.
- prefixSum[r1][c1]: Adds back the top-left overlapping region (since it was subtracted twice in previous steps).
This ensures that we get the correct sum for the desired submatrix in constant time O(1).
Matrix Block Sum Algorithm
- We create a prefixSum matrix of size [m+1][n+1] to store cumulative sums.
- We compute the prefixSum matrix using the given formula to store the sum from (0,0) to (i-1,j-1).
- We iterate over each cell (i, j) in the matrix and determine the valid block boundaries using max and min functions.
- We use the prefixSum matrix to compute the sum of elements in the block efficiently.
- We store the computed sum in the answer matrix.
- Finally, return the answer matrix.
Approach
Initialize Variables
- Get the dimensions m (rows) and n (columns) of the matrix.
- Create an empty prefixSum matrix of size [m+1][n+1] to store cumulative sums.
- Create an empty answer matrix of size [m][n] to store results.
Compute the Prefix Sum Matrix: Iterate through the matrix and fill prefixSum[i][j] using:
prefixSum[i][j] = mat[i-1][j-1] + prefixSum[i-1][j] + prefixSum[i][j-1] - prefixSum[i-1][j-1]
This ensures that prefixSum[i][j] stores the sum of elements from (0,0) to (i-1,j-1) in mat.
Compute the Block Sum for Each Cell
- For each cell (i, j), determine the valid submatrix boundaries using k:
r1 = max(0, i-k), c1 = max(0, j-k)
r2 = min(m-1, i+k), c2 = min(n-1, j+k)
Why do we use max(0, i - k) and min(m - 1, i + k) when calculating the block sum boundaries?
We use max(0, i - k) and max(0, j - k) to ensure that the starting indices (r1, c1) do not go out of the matrix bounds (negative indices).
Similarly, we use min(m - 1, i + k) and min(n - 1, j + k) to make sure that the ending indices (r2, c2) do not exceed the matrix size.
This ensures that we always select a valid submatrix within the given range while preventing index errors.
- Use the prefix sum formula to compute the sum in constant time:
answer[i][j] = prefixSum[r2+1][c2+1] - prefixSum[r1][c2+1] - prefixSum[r2+1][c1] + prefixSum[r1][c1]
Return the Final answer Matrix: After computing all values, return the answer matrix.
Dry-Run
Example
Input: mat = [[1, 2], [3, 4]], k = 1
Output answer = [[10, 10], [10, 10]]
Explanation:
Step 1: Compute prefixSum Matrix
We create a prefixSum matrix of size (m+1) x (n+1) = 3 x 3.
Formula to Compute prefixSum[i][j]:
prefixSum[i][j] = mat[i-1][j-1] + prefixSum[i-1][j] + prefixSum[i][j-1] - prefixSum[i-1][j-1]
Calculation of prefixSum:
- prefixSum[1][1] = mat[0][0] + prefixSum[0][1] + prefixSum[1][0] - prefixSum[0][0]
→ 1 + 0 + 0 - 0 = 1 - prefixSum[1][2] = mat[0][1] + prefixSum[0][2] + prefixSum[1][1] - prefixSum[0][1]
→ 2 + 0 + 1 - 0 = 3 - prefixSum[2][1] = mat[1][0] + prefixSum[1][1] + prefixSum[2][0] - prefixSum[1][0]
→ 3 + 1 + 0 - 0 = 4 - prefixSum[2][2] = mat[1][1] + prefixSum[1][2] + prefixSum[2][1] - prefixSum[1][1]
→ 4 + 3 + 4 - 1 = 10
Final prefixSum matrix:
[[0, 0, 0],
[0, 1, 3],
[0, 4, 10]]
Step 2: Compute answer Matrix Using prefixSum
For each answer[i][j], determine the block boundaries:
r1 = max(0, i - k), c1 = max(0, j - k)
r2 = min(m - 1, i + k), c2 = min(n - 1, j + k)
Use the formula to calculate the sum:
answer[i][j] = prefixSum[r2+1][c2+1] - prefixSum[r1][c2+1] - prefixSum[r2+1][c1] + prefixSum[r1][c1]
Calculation of answer:
- answer[0][0]:
r1 = max(0, 0 - 1) = 0
c1 = max(0, 0 - 1) = 0
r2 = min(1, 0 + 1) = 1
c2 = min(1, 0 + 1) = 1
answer[0][0] = prefixSum[2][2] - prefixSum[0][2] - prefixSum[2][0] + prefixSum[0][0]
→ 10 - 0 - 0 + 0 = 10 - answer[0][1]: r1 = 0, c1 = 0, r2 = 1, c2 = 1
answer[0][1] = prefixSum[2][2] - prefixSum[0][2] - prefixSum[2][0] + prefixSum[0][0]
→ 10 - 0 - 0 + 0 = 10 - answer[1][0]: r1 = 0, c1 = 0, r2 = 1, c2 = 1
answer[1][0] = prefixSum[2][2] - prefixSum[0][2] - prefixSum[2][0] + prefixSum[0][0]
→ 10 - 0 - 0 + 0 = 10 - answer[1][1]: r1 = 0, c1 = 0, r2 = 1, c2 = 1
answer[1][1] = prefixSum[2][2] - prefixSum[0][2] - prefixSum[2][0] + prefixSum[0][0]
→ 10 - 0 - 0 + 0 = 10
Final Output (answer Matrix):
[[10, 10],
[10, 10]]
Optimal Code in all Languages
1. Matrix Block Sum solution in C++ Try on Compiler
class Solution {
public:
// Function to compute matrix block sum using prefix sum
vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) {
// Get number of rows in matrix
int numRows = mat.size();
// Get number of columns in matrix
int numCols = mat[0].size();
// Create a prefix sum matrix
vector<vector<int>> prefixSum(numRows + 1, vector<int>(numCols + 1, 0));
// Compute prefix sum for each cell
for (int i = 1; i <= numRows; ++i) {
for (int j = 1; j <= numCols; ++j) {
prefixSum[i][j] = prefixSum[i - 1][j] + prefixSum[i][j - 1]
- prefixSum[i - 1][j - 1] + mat[i - 1][j - 1];
}
}
// Create answer matrix
vector<vector<int>> answer(numRows, vector<int>(numCols, 0));
// Compute block sum using prefix sum
for (int i = 0; i < numRows; ++i) {
for (int j = 0; j < numCols; ++j) {
answer[i][j] = getSum(prefixSum, i + k + 1, j + k + 1)
- getSum(prefixSum, i + k + 1, j - k)
- getSum(prefixSum, i - k, j + k + 1)
+ getSum(prefixSum, i - k, j - k);
}
}
return answer;
}
private:
// Helper function to retrieve prefix sum safely
int getSum(vector<vector<int>>& prefixSum, int r, int c) {
r = max(0, min(r, (int)prefixSum.size() - 1));
c = max(0, min(c, (int)prefixSum[0].size() - 1));
return prefixSum[r][c];
}
};2. Matrix Block Sum solution in Java Try on Compiler
class Solution {
// Function to calculate matrix block sum using prefix sum
public int[][] matrixBlockSum(int[][] mat, int k) {
// Get the number of rows in the input matrix
int numRows = mat.length;
// Get the number of columns in the input matrix
int numCols = mat[0].length;
// Create a prefix sum matrix with one extra row and column
int[][] prefixSum = new int[numRows + 1][numCols + 1];
// Compute prefix sum for each cell in the matrix
for (int i = 1; i <= numRows; ++i) {
for (int j = 1; j <= numCols; ++j) {
// Compute sum using previous values to avoid recomputation
prefixSum[i][j] = prefixSum[i - 1][j] + prefixSum[i][j - 1]
- prefixSum[i - 1][j - 1] + mat[i - 1][j - 1];
}
}
// Create the answer matrix to store block sums
int[][] answer = new int[numRows][numCols];
// Compute block sum for each cell using prefix sum
for (int i = 0; i < numRows; ++i) {
for (int j = 0; j < numCols; ++j) {
// Compute the sum of values inside the given block range
answer[i][j] = getSum(prefixSum, i + k + 1, j + k + 1)
- getSum(prefixSum, i + k + 1, j - k)
- getSum(prefixSum, i - k, j + k + 1)
+ getSum(prefixSum, i - k, j - k);
}
}
return answer;
}
// Helper function to safely get prefix sum values
private int getSum(int[][] prefixSum, int r, int c) {
// Ensure indices are within valid range
if (r < 0) r = 0;
if (c < 0) c = 0;
if (r >= prefixSum.length) r = prefixSum.length - 1;
if (c >= prefixSum[0].length) c = prefixSum[0].length - 1;
return prefixSum[r][c];
}
}3. Matrix Block Sum solution in Python Try on Compiler
class Solution:
# Function to compute matrix block sum using prefix sum
def matrixBlockSum(self, mat: List[List[int]], k: int) -> List[List[int]]:
# Get matrix dimensions
numRows, numCols = len(mat), len(mat[0])
# Create prefix sum matrix
prefixSum = [[0] * (numCols + 1) for _ in range(numRows + 1)]
# Compute prefix sum for each cell
for i in range(1, numRows + 1):
for j in range(1, numCols + 1):
prefixSum[i][j] = prefixSum[i - 1][j] + prefixSum[i][j - 1] \
- prefixSum[i - 1][j - 1] + mat[i - 1][j - 1]
# Create answer matrix
answer = [[0] * numCols for _ in range(numRows)]
# Compute block sum using prefix sum
for i in range(numRows):
for j in range(numCols):
answer[i][j] = self.getSum(prefixSum, i + k + 1, j + k + 1) \
- self.getSum(prefixSum, i + k + 1, j - k) \
- self.getSum(prefixSum, i - k, j + k + 1) \
+ self.getSum(prefixSum, i - k, j - k)
return answer
# Helper function to safely retrieve prefix sum values
def getSum(self, prefixSum, r, c):
r = max(0, min(r, len(prefixSum) - 1))
c = max(0, min(c, len(prefixSum[0]) - 1))
return prefixSum[r][c]
4. Matrix Block Sum solution in JavaScript Try on Compiler
/**
* @param {number[][]} mat
* @param {number} k
* @return {number[][]}
*/
var matrixBlockSum = function (mat, k) {
let numRows = mat.length, numCols = mat[0].length;
// Initialize prefix sum matrix
let prefixSum = Array.from({ length: numRows + 1 }, () => Array(numCols + 1).fill(0));
// Compute prefix sum
for (let i = 1; i <= numRows; i++) {
for (let j = 1; j <= numCols; j++) {
prefixSum[i][j] = prefixSum[i - 1][j] + prefixSum[i][j - 1]
- prefixSum[i - 1][j - 1] + mat[i - 1][j - 1];
}
}
// Function to safely get the sum from prefixSum
function getSum(r, c) {
r = Math.max(0, Math.min(r, numRows));
c = Math.max(0, Math.min(c, numCols));
return prefixSum[r][c];
}
// Compute block sum
let answer = Array.from({ length: numRows }, () => Array(numCols).fill(0));
for (let i = 0; i < numRows; i++) {
for (let j = 0; j < numCols; j++) {
answer[i][j] = getSum(i + k + 1, j + k + 1)
- getSum(i + k + 1, j - k)
- getSum(i - k, j + k + 1)
+ getSum(i - k, j - k);
}
}
return answer;
};
Time Complexity: O(m x n)
This approach efficiently calculates the block sum for each cell using the prefix sum matrix. Below is the detailed breakdown:
Computing the Prefix Sum Matrix
- Outer Loop for Rows: Iterates over each row, contributing O(m).
- Inner Loop for Columns: Iterates over each column, contributing O(n).
Total time complexity for computing the prefix sum matrix: O(m×n).
Calculating the Block Sum Using the Prefix Sum Matrix
- Outer Loop for Rows: Iterates over each row, contributing O(m).
- Inner Loop for Columns: Iterates over each column, contributing O(n).
- Sum Calculation: Each sum calculation using the prefix sum matrix is O(1).
Overall Time Complexity
The overall time complexity is: O(m×n)+O(m×n)=O(m×n)
This is the most optimal approach possible, as it involves only a single scan of the matrix to compute the prefix sum and another scan to calculate the block sums.
Space Complexity: O(m x n)
Auxiliary Space Complexity refers to the extra space required by an algorithm other than the input space.
- We use only a few integer variables (i, j for loops and temporary sum variables).
- We create a prefix sum matrix of size (m+1) × (n+1) to store cumulative sums.
- We create an answer matrix of size (m x n) to store block sums.
- Thus, the auxiliary space complexity is O(m × n).
Total Space Complexity
- The input matrix itself takes O(m × n) space.
- The prefix sum matrix takes O(m × n) space.
- The answer matrix takes O(m × n) space.
Final Space Complexity: O(m x n)
Similar Problems
Now, since we have figured out the Find the Minimum Area to Cover All Ones I solution, let's try out similar problems of "Find the Minimum Area to Cover All Ones I".
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.