# Matrix Rectangular Sums - Facebook Top Interview Questions

### Problem Statement :

```Given a two-dimensional list of integers matrix and an integer k, return a new matrix M of the same dimensions where M[i][j] is the sum of all numbers

sum(matrix[r][c]) for all (i - k ≤ r ≤ i + k, j - k ≤ c ≤ j + k)

Constraints

n, m ≤ 250 where n and m is the number of rows and columns in matrix

Example 1

Input

matrix = [

[1, 2, 3],

[4, 5, 6],

[7, 8, 9]

]

k = 1

Output

[

[12, 21, 16],

[27, 45, 33],

[24, 39, 28]

]```

### Solution :

```                        ```Solution in C++ :

int rectangle(vector<vector<int>>& dp, int r1, int c1, int r2, int c2) {
int res = dp[r2 + 1][c2 + 1];
res -= dp[r2 + 1][c1];
res -= dp[r1][c2 + 1];
res += dp[r1][c1];
return res;
}

vector<vector<int>> solve(vector<vector<int>>& matrix, int k) {
int m = matrix.size(), n = matrix[0].size();
vector<vector<int>> res(m, vector<int>(n));
vector<vector<int>> dp(m + 1, vector<int>(n + 1));

for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
dp[i + 1][j + 1] = matrix[i][j] + dp[i][j + 1] + dp[i + 1][j] - dp[i][j];
}
}

for (int r = 0; r < m; r++) {
for (int c = 0; c < n; c++) {
int r1 = max(0, r - k);
int c1 = max(0, c - k);
int r2 = min(m - 1, r + k);
int c2 = min(n - 1, c + k);

res[r][c] = rectangle(dp, r1, c1, r2, c2);
}
}
return res;
}```
```

```                        ```Solution in Java :

import java.util.*;

class Solution {
public int[][] solve(int[][] matrix, int k) {
RangeSumMatrix rsm = new RangeSumMatrix(matrix);
int[][] ret = new int[matrix.length][matrix[0].length];
for (int i = 0; i < ret.length; i++) {
for (int j = 0; j < ret[0].length; j++) {
ret[i][j] = rsm.total(i - k, j - k, i + k, j + k);
}
}
return ret;
}
}
class RangeSumMatrix {
int[][] matrix;
public RangeSumMatrix(int[][] matrix) {
this.matrix = matrix;
for (int i = 0; i < matrix.length; i++) {
for (int j = 1; j < matrix[0].length; j++) {
matrix[i][j] += matrix[i][j - 1];
}
}
}

public int total(int row0, int col0, int row1, int col1) {
row0 = Math.max(0, row0);
row1 = Math.min(matrix.length - 1, row1);
col0 = Math.max(0, col0);
col1 = Math.min(matrix[0].length - 1, col1);

int ret = 0;
for (int i = row0; i <= row1; i++) {
ret += matrix[i][col1];
if (col0 != 0) {
ret -= matrix[i][col0 - 1];
}
}
return ret;
}
}```
```

```                        ```Solution in Python :

class Solution:
def solve(self, A, k):
R, C = len(A), len(A[0])
for r in range(R):
for c in range(C):
if r:
A[r][c] += A[r - 1][c]
if c:
A[r][c] += A[r][c - 1]
if r and c:
A[r][c] -= A[r - 1][c - 1]

def get_sum(top, left, bottom, right):
top = max(top, 0)
left = max(left, 0)
bottom = min(bottom, R - 1)
right = min(right, C - 1)

return (
A[bottom][right]
- (A[top - 1][right] if top else 0)
- (A[bottom][left - 1] if left else 0)
+ (A[top - 1][left - 1] if top and left else 0)
)

return [[get_sum(r - k, c - k, r + k, c + k) for c in range(C)] for r in range(R)]```
```

## Insert a node at a specific position in a linked list

Given the pointer to the head node of a linked list and an integer to insert at a certain position, create a new node with the given integer as its data attribute, insert this node at the desired position and return the head node. A position of 0 indicates head, a position of 1 indicates one node away from the head and so on. The head pointer given may be null meaning that the initial list is e

## Delete a Node

Delete the node at a given position in a linked list and return a reference to the head node. The head is at position 0. The list may be empty after you delete the node. In that case, return a null value. Example: list=0->1->2->3 position=2 After removing the node at position 2, list'= 0->1->-3. Function Description: Complete the deleteNode function in the editor below. deleteNo

## Print in Reverse

Given a pointer to the head of a singly-linked list, print each data value from the reversed list. If the given list is empty, do not print anything. Example head* refers to the linked list with data values 1->2->3->Null Print the following: 3 2 1 Function Description: Complete the reversePrint function in the editor below. reversePrint has the following parameters: Sing