# Matrix Prefix Sum - Amazon Top Interview Questions

### Problem Statement :

```Given a two-dimensional integer matrix, return a new matrix A of the same dimensions where each element is set to A[i][j] = sum(matrix[r][c]) for all r ≤ i, c ≤ j.

Constraints

n, m ≤ 250 where n and m are the number of rows and columns in matrix
matrix[i][j] ≤ 2**12

Example 1

Input
matrix = [
[2, 3],
[5, 7]
]

Output
[
[2, 5],
[7, 17]
]```

### Solution :

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

vector<vector<int>> solve(vector<vector<int>>& matrix) {
for (int i = 0; i < matrix.size(); ++i) {
for (int j = 0; j < matrix.size(); ++j) {
if (i - 1 >= 0) matrix[i][j] += matrix[i - 1][j];

if (j - 1 >= 0) matrix[i][j] += matrix[i][j - 1];

if (i - 1 >= 0 && j - 1 >= 0) matrix[i][j] -= matrix[i - 1][j - 1];
}
}

return matrix;
}```
```

```                        ```Solution in Java :

import java.util.*;

class Solution {
public int[][] solve(int[][] matrix) {
if (matrix.length == 0 || matrix.length == 0) {
return matrix;
}

int[][] output = new int[matrix.length][matrix.length];
output = matrix;
for (int x = 0; x < matrix.length; x += 1) {
for (int y = 0; y < matrix[x].length; y += 1) {
int sum = 0;
for (int a = 0; a <= x; a += 1) {
for (int b = 0; b <= y; b += 1) {
sum += matrix[a][b];
}
}
output[x][y] = sum;
}
}
return output;
}
}```
```

```                        ```Solution in Python :

class Solution:
def solve(self, matrix):

if not matrix:
return []

r = len(matrix)
c = len(matrix)

for i in range(r):
for j in range(1, c):
matrix[i][j] += matrix[i][j - 1]

for j in range(c):
for i in range(1, r):
matrix[i][j] += matrix[i - 1][j]

return matrix```
```

## Array Pairs

Consider an array of n integers, A = [ a1, a2, . . . . an] . Find and print the total number of (i , j) pairs such that ai * aj <= max(ai, ai+1, . . . aj) where i < j. Input Format The first line contains an integer, n , denoting the number of elements in the array. The second line consists of n space-separated integers describing the respective values of a1, a2 , . . . an .

## Self Balancing Tree

An AVL tree (Georgy Adelson-Velsky and Landis' tree, named after the inventors) is a self-balancing binary search tree. In an AVL tree, the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property. We define balance factor for each node as : balanceFactor = height(left subtree) - height(righ

## Array and simple queries

Given two numbers N and M. N indicates the number of elements in the array A[](1-indexed) and M indicates number of queries. You need to perform two types of queries on the array A[] . You are given queries. Queries can be of two types, type 1 and type 2. Type 1 queries are represented as 1 i j : Modify the given array by removing elements from i to j and adding them to the front. Ty