Number of Islands


Can you explain in your approach #2, why is space complexity O(1)? The size of queue (neighbors) will grow as more of the "newfoundland" is discovered. I have tried to run your program with a 100x100 grid of only 1 giant 100x100 island, and the size of neighbors hit 100 sometime during execution. At its peak, neighbors will contain the diagonal of the matrix, so the worst case space complexity should be min{O(M), O(N)}, which is O(M + N). (O(M) or O(N) also work, isn't it?) It's alright because we are using big O notation, I don't know how would min{O(M), O(N)} looks like in Θ, any thoughts?.

@williamfu4leetcode, yes you are right. I didn't think through about the space complexity of BFS approach. Thanks for making it correct! I've just updated the article to reflect this.

@ jocelynayoga Thanks for the comments! Think about the worse case: the grid if filled with '1'. During the first iteration, it takes MN to do BFS to identify the giant island. After that, it takes another MN to scan the grid, even though all the cells become '0' by then. So the total is 2MN which is still O(M*N).

@jocelynayoga Thanks for the comments! Think about the worse case: the grid if filled with '1'. During the first iteration, it takes MN to do BFS to identify the giant island. After that, it takes another MN to scan the grid, even though all the cells become '0' by then. So the total is 2MN which is still O(M*N).