## Amazon Interview Question

Computer Scientists**Country:**India

**Interview Type:**In-Person

Assumption M<=N

For no of squares in MxN

```
Size of square: 1 2 3 4..... k... M-1 M
No of squares in row: N N-1 N-2 N-3 N-k+1 N-M+2 N-M+1
No of squares in col: M M-1 M-1 M-1 M-k+1 2 1
Total no of squares = no of squares in row * no of squares in col
sigma [(N-k+1)*(M-k+1)] for k from 1 to M
```

For rectangles

```
Length of rectange 1 2 ... k ... N-1 N
No of rectange N N-1 N-k+1 2 1
Total rectangles = N*(N+1)/2
Height of rectange 1 2 ... k ... M-1 M
No of rectange M M-1 M-k+1 2 1
Total rectangles = M*(M+1)/2
Total no of rectanges = M*N*(M+1)*(N+1)/4
```

your approach is good but in rectangle case we can solve it more easily

m* n matrix has (m+1) vertical lines and (n+1) horizontal lines and a rectangle will form if we chose any 2 vertical lines from m+1 lines (i.e (m+1 C 2)) and any 2 horizontal lines from n+1 horizontal lines (i.e. n+1 C 2),

hence

Ans - m+1C 2 * n+1 C 2 = m*n*(m+1)*(n+1)/4

This solution uses DP, however, it's not as good as those that provide a cool formula, plus its demonstration, for calculating the value :(

Number of squares:

The idea is that for getting the number of possible squares at cell (i, j), we want to add the existing ones at (i-1,j) + (i, j-1) while ignoring duplications, i.e., (i-1,j-1). Then, we want to add all new squares that have cell (i, j) as part of them, which in this case is the value of min(i, j) for the squares of size 1, 2, 3 ... min (i, j) that have cell (i, j) at its bottom-right corner.

Hence,

F(i, j) = F(i - 1, j) + F(i, j - 1) - F(i - 1, j - 1) + min(i, j)

You can fill the matrix top-down while reading left to right.

Number of rectangles:

Same idea as previous one, except that the number of new rectangles added at cell (i, j) that include such cell is given by i * j.

F(i, j) = F(i - 1, j) + F(i, j - 1) - F(i - 1, j - 1) + i * j

Time complexity: O(n^2), sadly...

Space complexity: O(n^2), ouch...

Solve reccurance equation:

C(1)=n; C(n)=C(n-1)*2 - n + N + 1

The solution:

C(n) = 2^(n-1) (n+N-2)+n-N+1

Notice, with adding row we only doubling previous squares (each has shifted copy) plus aad all covering new width

1. squares in NxN grid

2.squares in MxN grid

3.rectangles in MxN grid

- neerajlakhotia08 March 27, 2014