Medium Facebook Graph Interview Question - Max Area of Island - Leetcode 695

FAANG Coding Interviews / Data Structures and Algorithms / Leetcode

[GregHogg]

Master Data Structures & Algorithms For FREE at AlgoMap.io!

[chixenlegjo]

I think I have an O(mn) time and space solution that doesn’t require DFS or a hashset. It involves storing the size of each island in a list (beginning with just [0]), and as you march through the list (left-to-right and up-to-down), you check the value of the cell, the of the above cell, and the value of the cell to the left. If the current cell is 0, nothing happens and it stays 0. If both above and left of the current cell is 0, set the cell to the length of the sizes list, and then append a 1 to it. If exactly one of the cells is a 0, add 1 to the element in the list with the index of the nonzero value, then set the cell’s value to the same as the nonzero cell. If both are nonzero, add the list’s element indexed above to the value indexed to the left plus one, then set the value indexed above to 0. Set the current cell’s value to that of what’s to the left. By the end this process, you get a list of the sizes of the islands, some of which are 0 because they are duplicates. The maximum size of this list is mn/2 if the grid has a checkerboard pattern. I’ll write some pseudocode in a reply.

[TFShows]

You can optimize it: instead of using "visited" set, you can modify in-place the matrix. Set visited cells to '' (empty string) instead of 1.

[Nysvarth]

If there are 2 with the largest size how does this return both of them?

[unstopper]

Is it possible to do it by using Union-find for less space complexity? (not sure about comparing time complexity)

[rashmiranjanjena]

What application you used to run python

[Alex.Juarezc]

Hello, at my university to work with graphs and their algorithms we use the networkX Python library. Do you recommend it to work with these data structures? Which one do you recommend for this type of problem to solve? Greetings and thanks for the video.

[anmolsinha]

Is this code logic also used by Minesweeper ? 😅

[insertnamehere]

could you make it so you let us try to solve the question on our own before you give the answer

[ULTIMARAGNARK]

Mate I’m sick of seeing your videos. These sorts of videos only appear after Meta, Google, etc do massive layoffs.

[Btstaz]

yeah unsubbed, as your answers are only mostly correct.