Biggest Island

In this short story, I would like to talk about a fun puzzle involving a recursion technique.

At first this problem might seem a little more complicated than it really is, if you are the kind of person who always worry about complexity (like me…), but it turns out everything works together nicely :)

To briefly describe the problem, you are given a representation of a piece of water and islands in it:

[[0,0,1,1,0,0],
 [0,0,1,1,0,0],
 [0,0,0,1,0,0],
 [0,0,0,0,0,1]]

Where 0’s are water and 1’s are islands. the problem is to find the biggest island and its size in the water.

In this case you can just tell it’s 5:

[[0,0,1,1,0,0],
 [0,0,1,1,0,0],
 [0,0,0,1,0,0],
 [0,0,0,0,0,1]]

Because the 1’s are connected 4-directionally.

One more rule to specify to avoid ambiguity:

diagonal connection is not considered connected.

[[0,0,1,1,0,0],
 [0,0,1,1,0,0],
 [0,0,0,0,1,0],
 [0,0,0,0,0,1]]

In this case the biggest island is size 4.

How would one approach this problem, I think for anyone with some experience in recursion, he/she would attempt to go through each position in the water, and if that position happens to be a rock(1), recursively search its 4 neighbors to determine its size and figure out if this island is the biggest encountered so far.

Two potential obstacles immediately come to mind:

1. If you recursively search its neighbors, how do you make sure you don’t search the positions you have already searched?
2. If you search past the boundary of the map, how do you handle that?

Let’s start with a first attempt and see how we can resolve these issues:

def find_biggest_island(islands):

    cur_max = 0
    for row in range(len(islands)):
        for col in range(len(islands[row])):
            cur_max = max(cur_max, get_size(islands, row, col))

    return cur_max

In this function, find_biggest_island, I loop through each position in the island map:

(row, col) in {(0, 0), (0, 1), (0, 2), …, (1, 0), (1, 1), … (n, m)}

and find the size of the island at each position, replacing the current maximum size with the bigger of the previous maximum size and the new found size of the island at the current position.

Next step is to implement get_size, here is a first attempt:

def get_size(islands, row, col):
    if islands[row][col] != 1:
        return 0

    size = 1
    directions = [(-1, 0), (1, 0), (0, 1), (0, -1)]
    for direction in directions:
        size = size + get_size(islands,
                               row + direction[0],
                               col + direction[1])

    return size

in this function, I first check if the current position is 1, if so then there is an island at this position so I need to find its size.

I first initialize the size to 1, since that’s the minimum possible if there is island at all at the current position, then I recursively search in the four directions (left, right, up, down), and find the size of islands connection to the current position, and add them up to get the total size of the island.

So here we will encounter the two problems, for example:

position (0, 2)!
      |
      v
[[0,0,1,1,0,0],
 [0,0,1,1,0,0],
 [0,0,0,1,0,0],
 [0,0,0,0,0,1]]

if I am at position (0, 2), it’s a 1, so I search its four neighbors:

left: 0

right: 1

up: out of boundary

down: 1

We first attempt to get_size(left), which is a zero, so returns a 0. All is well.

Then we try to get_size(right), it’s a 1, so we have to recursively get its four neighbors again. But! position (0, 2) is its neighbor and it’s also where we started, if we just let the program run, it’ll go back and forth forever between the two positions… (and you’ll get a stack depth exceeded error)

In this case we’ll need to figure out a way to make sure we don’t do recursion again at position (0, 2), one of the simplest ways to do this is to mark it as visited:

def get_size(islands, row, col):
    if islands[row][col] != 1:
        return 0

    size = 1
    islands[row][col] = -1 # change the value of the position to -1
    directions = [(-1, 0), (1, 0), (0, 1), (0, -1)]
    for direction in directions:
        size = size + get_size(islands,
                               row + direction[0],
                               col + direction[1])

    return size

Now that you marked it, since the value is not 1 anymore after you visited it, the condition

if islands[row][col] != 1:
        return 0

will prevent you from searching this position again.

Now that we have resolved the recursion problem, we can attempt the remaining neighbors:

up: out of boundary

To prevent the program from searching beyond the boundary we need a few additional boundary checks:

if row < 0 or row >= len(islands):
    return 0

if col < 0 or col >= len(islands[row]):
    return 0

if the row or column number is less than 0 or greater than the islands map, then return immediately.

With these enhancements, we find the size of the island by adding up the current position and the size of its neighbors:

1 + 0 + (1 + (1 + 1 + 1)) = 5

(Try figure out why I arranged the equation this way :P)

the final program looks like this:

def get_size(islands, row, col):

    #3
    if row < 0 or row >= len(islands):
        return 0

    if col < 0 or col >= len(islands[row]):
        return 0

    #2
    if islands[row][col] != 1:
        return 0

    size = 1
    islands[row][col] = -1
    directions = [(-1, 0), (1, 0), (0, 1), (0, -1)]
    for direction in directions:
        size = size + get_size(islands,
                               row + direction[0],
                               col + direction[1])

    return size


#1
def find_biggest_island(islands):

    cur_max = 0
    for row in range(len(islands)):
        for col in range(len(islands[row])):
            cur_max = max(cur_max, get_size(islands, row, col))

    return cur_max

islands001 = \
[[0,0,1,1,0,0],
 [0,0,1,1,0,0],
 [0,0,0,1,0,0],
 [0,0,0,0,0,1]]

islands002 = \
[[0,0,1,1,0,0],
 [0,0,1,1,0,0],
 [0,0,0,0,1,0],
 [0,0,0,0,0,1]]

print(find_biggest_island(islands001))
print(find_biggest_island(islands002))