Coding

Number of islands

Asked at

Amazon

Goldman Sachs

Oracle

Paytm

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The problem

Given a grid of size N x M (N is the number of rows and M is the number of columns in the grid) consisting of '0's (Water) and ‘1's(Land). Find the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically or diagonally i.e., in all 8 directions.

Input: grid = [ ["1", "1", "1", "0", "1"], ["1", "0", "0", "0", "0"], ["1", "1", "1", "0", "1"], ["0", "0", "0", "1", "1"] ] Output: 2 Explanation: This grid contains 2 islands. Each '1' represents a piece of land, and the islands are formed by connecting adjacent lands horizontally or vertically. Despite some islands having a common edge, they are considered separate islands because there is no land connectivity in any of the eight directions between them. Therefore, the grid contains 2 islands.

Input: grid = [ ["1", "0", "0", "0", "1"], ["0", "1", "0", "1", "0"], ["0", "0", "1", "0", "0"], ["0", "1", "0", "1"," 0"] ] Output: 1 Explanation: In the given grid, there's only one island as all the '1's are connected either horizontally, vertically, or diagonally, forming a single contiguous landmass surrounded by water on all sides.

Input: grid = [ ["1", "1", "1", "1", "0"], ["1", "1", "0", "1", "0"], ["1", "1", "0", "0", "0"], ["0", "0", "0", "0", "0"] ]

· N == grid.length · M == grid[i].length · 1 <= N, M <= 300 · grid[i][j] is '0' or '1'.

cpp

class Solution{
public:
    int numIslands(vector<vector<char>> &grid){
    }
};

java

class Solution {
    public int numIslands(char[][] grid) {
       
    }
}

python

class Solution:
    def numIslands(self, grid):

javascript

class Solution {
    numIslands(grid) {
     
    }
}

csharp

public class Solution {
    public int NumIslands(List<List<string>> grid) {
       
    }
}

func NumIslands(grid [][]byte) int {
	
}

Stuck? Show a way to structure it+

01Scan every grid cell and start a traversal whenever an unvisited land cell is found.
02Mark the entire connected component using the eight direction offsets required by this version.
03Increment the island count once per traversal, not once per land cell.
04Explain how in-place marking or a visited matrix prevents repeated work.

Reference answer

Treat every land cell as a graph node. In this version, two land cells are adjacent horizontally, vertically, or diagonally, so use all eight (dr, dc) direction pairs.

Scan the grid. When a cell contains land and has not been visited, increment the island count and run DFS or BFS from it. During the traversal, mark each reachable land cell before adding or recursing into its neighbors. You can keep a separate boolean matrix or mutate visited land from '1' to '0' if modifying the input is allowed.

Each traversal consumes exactly one connected component, so the number of traversal starts is the number of islands. Boundary checks must happen before reading a neighbor. The eight-direction detail matters: a diagonal chain is one island here, even though the common LeetCode version uses only four directions.

Every cell is examined a constant number of times, giving O(NM) time. The visited structure and traversal frontier use O(NM) worst-case space; in-place marking removes the separate visited matrix but recursion or the BFS queue can still grow to the component size.

Then expect these follow-ups

How would the result differ if only four directions were allowed?
Tests: requirements awareness
How would you process a grid too large to fit in memory?
Tests: scalability reasoning

Hiring now

Linkedin has 196 open roles right now

Also hiring: Paytm

landed applies to roles like these for you, on each company’s own site, with answers written for the role.

Get 5x interviews10 free auto-applies. No card.

Software Engineer - Systems and Infrastructure
Mountain View, CA, United States
Staff Software Engineer
Mountain View, CA, United States
Staff Software Engineer, Systems Infrastructure
Bengaluru, KA, India

Or practice this question first

Next question