LeetCode #200 Number of Islands

Medium

Problem

Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example 1:

Input:
11110
11010
11000
00000
Output: 1

Example 2:

Input:
11000
11000
00100
00011
Output: 3

Solution

It’s a recursion problem because we should test neighbors once we found a point is equal to 1. Remember to change value of point after testing or it will be tested again.

Complexity

For each point, it will be visited up to 5 times which comes from four direction and loop visiting. Because there are m * n points which m and n denote to counts of row and column of grid, it takes O(5mn) = O(mn) time for this approach.

For space complexity, because we don’t allocate new param in both loop and recursion, it uses O(1) extra space.