How does The Interns Company match students with internships?

We use a combination of AI-powered matching algorithms and human expertise to connect students with internship opportunities that align with their skills, interests, and career goals.

Are the internship opportunities exclusive?

Yes, many of our partner companies offer positions exclusively through our platform that you won't find on public job boards or career sites.

Is there a cost to use The Interns Company?

Our basic matching service is free for students. Premium services like one-on-one interview coaching and resume reviews may have associated fees.

Number of Islands

MediumAcceptance: 51.3%

Array Depth-First Search Breadth-First Search Union Find Matrix

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.

Constraints:

m == grid.length
n == grid[i].length
1 <= m, n <= 300
grid[i][j] is '0' or '1'

Input Format:

A 2D grid map where '1' represents land and '0' represents water

Output Format:

Return the number of islands in the grid.

Examples:

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:

Explanation:

There is only one island in the grid above.

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:

Explanation:

There are three islands in the grid above.

Solutions

Depth-First Search Approach

Time: O(m × n) where m is the number of rows and n is the number of columns

Space: O(m × n) in the worst case for the recursion stack

Use DFS to traverse and mark visited lands. Each time we encounter a new unvisited land, we increment our count and use DFS to mark all connected lands as visited.

Breadth-First Search Approach

Time: O(m × n) where m is the number of rows and n is the number of columns

Space: O(min(m, n)) for the queue

Use BFS to traverse and mark islands. For each unvisited land cell, increment the island count and use BFS to visit all connected land cells.

Algorithm Walkthrough

Example input: nums = []

Step-by-step execution:

Starting BFS from grid[0][0] = '1':
Mark (0,0) as visited and add to queue
Explore neighbors of (0,0): mark (0,1) and (1,0) as visited
Continue BFS until all connected land cells are visited
This forms island #1
Starting BFS from grid[2][2] = '1':
Mark (2,2) as visited, no adjacent land cells
This forms island #2
Starting BFS from grid[3][3] = '1':
Mark (3,3) as visited and add to queue
Explore neighbors: mark (3,4) as visited
This forms island #3
No more unvisited land cells, return count = 3

Hints

Hint 1

Think about using a graph traversal algorithm like DFS or BFS to explore each island.

Hint 2

When you encounter land ('1'), perform a full exploration of the connected island and mark visited cells.

Hint 3

How can you mark visited cells without using extra space? Consider modifying the input grid.

Video Tutorial