Grokking Google Coding Interview
Ask Author
Back to course home

0% completed

Vote For New Content
Space complexity of DFS solution might be incorrectly given

Anand Mohan

Aug 27, 2023

Given :

DFS recursion stack can go  deep when the whole matrix is filled with '1's. Hence, the space complexity will be , where ‘M’ is the number of rows and 'N' is the number of columns of the input matrix.

All the matrix element will not be in one recursion stack. It will part of call back to left and right sub-path. So, the space complexity should be less then (M*N)

I think for DFS as well the Space Complexity would be O(min(M, N))

Please correct me If I am wrong.

0

0

Comments
Comments
C
cookies 2 years ago

Ya I'm confused by this as well because if we look at the section, Solution: 0/1 Knapsack, they say that

"The space complexity is O(n). This space will be used to store the recursion stack. Since the recursive algorithm works in a depth-first fashion, which means th...

Manuel
Manuel9 months ago

Really disappointed they dont fix their stuff over a year

Manuel
Manuel9 months ago

I Just got a good explanation from DeepSeek:

Time Complexity

  1. Outer Loop:
    • The outer loop iterates over each cell in the matrix. If the matrix has rows and cols, the total number of cells is rows * cols.
    • This gives us a time complexity o...

On this page