Making A Large Island | Leetcode 827 | Matrix Graph DFS Hard | Facebook Apple

[@AP-eh6gr]

thank you for explaining!

[@NareshGupta]

You're welcome!

[@praveenj3112]

Thanks Naresh for the outstanding explanation. it really helped a lot .

[@NareshGupta]

Most welcome!

[@mrprime557]

Why is the dimension on A array- n* n+2 ?? I didnt understand the n+2 part

[@rahulmodi926]

Can you tell how time complexity in 1st approach is O(n4). And if it is O(n4) in 1st approach, how it is O(n2) in 2nd approach as DFS is used within matrix traversal in both approaches.

[@NareshGupta]

In first approach we are running two nested for loop and then applying dfs for each zero cells --> n^2 * n^2 = n^4 While in second approach we are first running simple dfs --> n^2 and storing and marking area colors of each island. Hope it clear ur doubt.

[@Jay-lj2bv]

@@NareshGupta so the worst case is when all the cells of matrix are zero. so for each cell in dfs function it will look for one in adjacent cell (left,right,top,bottom)but since all the adjacent will be having zeroes it will retun 0; so don't you think time complexity should be n^2! Actually i know i am wrong but i just find it difficult to know time complexity can u correct me?

[@rsroyalrahul5]

please dont use red color on black!!!

[@NareshGupta]

Thanks, noted.