Find number of islands - 1d grid, no modification, and no linear extra space


  • 0
    B

    Write a function: int numIslands(boolean[] grid, int w, int h)
    that returns the number of islands in grid. grid is 1-dimensional, but represents a 2-dimensional boolean[h][w] array. Example: if h = 12 and w = 5, then grid[7] represents [1][2].

    Now, there is an additional constraint: can you solve this problem without modifying grid, and without using O(w*h) extra space?

    I was asked this in a interview, and haven't figured out the solution for the constraint.


  • 0
    S

    This sounds similar to https://leetcode.com/problems/battleships-in-a-board/description/
    All the additional space you need is O(1) for a counter for the distinct islands encountered so far.
    You can then traverse the array and increase the counter every time you find an island that has not been counted. For that, if the current square is land, check if any of the adjacent squares you've visited before is land, too (as opposed to water) else increase the counter. Keep in mind that if the width is w, you get the array position of the square immediately above by subtracting w from the current array position (if the current position is greater than w). Be sure to ask if they want you to consider diagonally adjacent squares as one connected island and if the map is meant to be flat or round (i.e. is it possible to cross the edges and turn out at the other end). Depending on that, the number of squares to check for each land square can rise to up to 4, but the overall runtime complexity will still remain O(h*w).


  • 0
    B
    This post is deleted!

  • 0
    B

    @sapere-aude
    I looked at the battleships problem. Its solution would not work for the number of islands, for example:

    X . X
    X X X

    It would return 2, even though it's 1.

    I thought my interview question was identical to the number of islands problem. I must have glossed over some of the details, since the interviewer asked for no modification and better than O(w*h) space. For a problem like number of islands, it's not possible right?


  • 0
    S

    @bluecloud Do diagonal connections count? In other words, would

    X .
    . X
    

    be considered one or two islands?

    The boolean[] declaration makes me guess you'd prefer java code?


  • 0
    B

    @sapere-aude

    Diagonal connections do not count. That would be two islands.

    I'd prefer Java or Python.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.