Grokking Google Coding Interview

0% completed

​
Hidden Document
Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content

.....

.....

.....

Like the course? Get enrolled and start learning!
M

Mike Xu

· 3 years ago

To clarify the space complexity of BFS traversal of a matrix:

When you start traversing a matrix from the corner, the maximum number of cells/nodes you can have in the queue is k where k is the number of cells on a diagonal line in the matrix, which means k = min(M, N).

When you start traversing a matrix from the centre, the maximum number of cells/nodes you can have in the queue is {1, 4, 8, 12, 16, ..., 4i} where i is the i-th layer. And such cells fit in a matrix of min size {1, 4, 9, 16, 25, ..., i*i} respectively. We know that i is min(M, N), so yet again we have space complexity of O(4 * min(M, N)) which is O(min(M,N)).

https://stackoverflow.com/a/75422161/9406517