# Count Rectangular Submatrices - Google Top Interview Questions

### Problem Statement :

```Given a two-dimensional list of integers matrix containing 1s and 0s, return the total number of submatrices with all 1 s.

Constraints

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

Example 1

Input

matrix = [

[1, 1, 0],

[1, 1, 0],

[0, 0, 0]

]

Output
9

Explanation

There's four 1 x 1 matrices. Theres two 2 x 1 matrices. There's two 1 x 2 matrices. And there's one 2 x 2
matrix.```

### Solution :

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

int solve(vector<vector<int>>& matrix) {
int n = matrix.size(), m = matrix.size();
vector<vector<int>> dp(n + 1, vector<int>(m));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (!matrix[i][j]) continue;
dp[i][j] = j == 0 ? 1 : dp[i][j - 1] + 1;
}
}
int ans = 0;
for (int j = 0; j < m; ++j) {
stack<pair<int, int>> st;
for (int i = 0; i <= n; ++i) {
int v = dp[i][j], len = 1;
while (!st.empty() && st.top().first > v) {
auto [h, w] = st.top();
st.pop();
int lo = v;
if (!st.empty() && st.top().first >= v) {
lo = st.top().first;
st.top().second += w;
} else
len += w;
ans += (h - lo) * w * (w + 1) / 2;
}
if (!st.empty() && st.top().first == v)
st.top().second++;
else
st.emplace(v, len);
cout << ans << " ";
}
}
return ans;
}```
```

```                        ```Solution in Java :

import java.util.*;

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

int n = a.length;
int m = a.length;

int ans = 0;

int[] row = new int[m];

for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (a[i][j] == 0) {
row[j] = 0;
} else {
row[j]++;
}
}
int[] dp = new int[m];
//  [1, 2, 3, 7, 4*]

Stack<Integer> stack = new Stack<>();

for (int j = 0; j < m; j++) {
while (stack.size() > 0 && row[stack.peek()] >= row[j]) {
stack.pop();
}
dp[j] = (stack.size() > 0 ? (j - stack.peek()) * row[j] + dp[stack.peek()]
: row[j] * (j + 1));
ans += dp[j];
stack.push(j);
}
}
return ans;
}
}```
```

## 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