Solving Salesforce SMTS Interview Question: Number of Islands

As a Senior Member of Technical Staff (SMTS) at Salesforce, I've seen my fair share of coding interviews.

One question that often pops up is the classic "Number of Islands" problem.

It tests your problem-solving skills and your ability to think in terms of graphs and connectivity.

This problem is about navigating a 2D grid and identifying connected components.

In this blog post, we'll dive into this problem, break it down, and walk through a solution. Let's get started!

Problem Statement

Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return 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: grid = [

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

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

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

["0","0","0","0","0"]

]

Output: 1

Example 2:

Input: grid = [

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

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

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

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

]

Output: 3

Constraints:

m == grid.length

n == grid[i].length

1 <= m, n <= 300

grid[i][j] is '0' or '1'.

Solution

To solve the problem of counting the number of islands in a 2D grid, we can use a Depth-First Search (DFS) approach.

Here's a step-by-step explanation of how we can implement this:

Step 1: Understand the Grid

➤ The grid is a 2D array where '1' represents land and '0' represents water.

➤ An island is formed by connecting adjacent (horizontally or vertically) lands.

Step 2: Iterate Through the Grid

➤ We iterate through each cell of the grid. If a cell with value '1' is found, it indicates the start of a new island.

Step 3: Apply DFS to Mark Visited Land

➤ When we find a piece of land ('1'), we start a DFS from that cell.

➤ We mark the current land cell as visited by setting it to '0' or another marker to indicate we've already counted this part of an island.

➤ We recursively apply DFS to all adjacent (up, down, left, right) land cells that are part of this island (i.e., cells with value '1').

Step 4: Count the Islands

➤ Each time we start a DFS from a new land cell (that hasn't been visited), we've discovered a new island. We increment our island count.

➤ Continue the process until all cells in the grid have been checked.

Step 5: Return the Count

➤ After we've iterated through the entire grid and applied DFS to all pieces of land, the total count of islands is our answer.

Python Implementation:

def numIslands(grid):
    if not grid:
        return 0

    def dfs(i, j):
        if i < 0 or i >= len(grid) or j < 0 or j >= len(grid[0]) or grid[i][j] == '0':
            return
        grid[i][j] = '0'  # Mark as visited
        dfs(i + 1, j)  # Down
        dfs(i - 1, j)  # Up
        dfs(i, j + 1)  # Right
        dfs(i, j - 1)  # Left

    count = 0
    for i in range(len(grid)):
        for j in range(len(grid[0])):
            if grid[i][j] == '1':  # Found an unvisited land
                dfs(i, j)  # Start DFS to mark all adjacent lands
                count += 1  # Increase the island count
    return count

Explanation:

📌 The numIslands function takes a 2D grid as input.

📌 The nested loop iterates through each cell of the grid.

📌 When it finds an unvisited land ('1'), it calls the dfs function to mark all connected lands as visited.

📌 The dfs function marks the current cell as visited and recursively explores adjacent cells (up, down, left, right) that are part of the same island.

📌 Each time the DFS starts from a new land cell, we increment the count of islands.

📌 Finally, the function returns the total number of islands found.

This approach efficiently counts the number of islands in the grid by marking visited parts of an island and only counting unvisited lands as the start of new islands.

**************

I hope this deep dive into the "Number of Islands" problem has been helpful and maybe even a bit fun! This is just one of many interesting challenges you might encounter in technical interviews, especially at companies like Salesforce.

If you found this useful and want to practice more problems like this, or if you're specifically aiming for a role at Salesforce, connect with me here for a free trial session.

I'm always happy to connect and share insights about the interview process or other common coding challenges.