Number of Islands
Updated
Problem statement
You are given a map as a grid grid with m rows and n columns. Each cell is 1 for land or 0 for water.
Two land cells are connected when they share a side: one is directly above, below, left or right of the other. Cells that touch only at a corner are not connected. An island is a group of land cells that are connected to each other, directly or through other land cells, and not connected to any other land. Everything outside the grid is water.
Return the number of islands.
Function
countIslands(grid: int[][]) → intExamples
Example 1
grid = [[1,1,0,1],[0,1,0,1],[1,0,0,0],[1,1,0,1]]return = 4Write (r, c) for row r and column c, counting from 0. The islands are:
(0, 0),(0, 1)and(1, 1);(0, 3)and(1, 3);(2, 0),(3, 0)and(3, 1);(3, 3)alone.
Cells (1, 1) and (2, 0) touch only at a corner, so they are in different islands. The answer is 4.
Example 2
grid = [[1,0,1],[1,0,1],[1,1,1]]return = 1The two columns of land are not next to each other at the top, but both reach the bottom row, and the bottom row joins them. So all seven land cells form one island.
Example 3
grid = [[0,0,0],[0,0,0]]return = 0There is no land, so there are no islands.
Constraints
m == grid.lengthn == grid[i].lengthfor every row, so all rows have the same length.1 <= m, n <= 200- Each
grid[i][j]is0or1.
More Expedia Onsite Interview questions
- Scramble StringONSITE INTERVIEW · Seen Sep 2026
- Smallest Sufficient TeamONSITE INTERVIEW · Seen Sep 2026
- Check Anagram Pairs Index by IndexONSITE INTERVIEW · Seen Oct 2025
- Fresh Oranges Left After Rotting StopsONSITE INTERVIEW · Seen Oct 2025
- Longest Increasing SubsequenceONSITE INTERVIEW · Seen Oct 2025
- Lowest Common Ancestor with Repeated and Missing ValuesONSITE INTERVIEW · Seen Oct 2025
- Shortest Substring with Exactly K OnesONSITE INTERVIEW · Seen Oct 2025
- Middle Element of a Linked ListONSITE INTERVIEW · Seen Nov 2024
- Minimum in a Rotated Sorted ArrayONSITE INTERVIEW · Seen Sep 2024
- Mirror Image Binary TreesONSITE INTERVIEW · Seen Sep 2024
Similar questions at other companies
- Count Islands in a Binary GridApple · PHONE SCREENApple interview questions
- Count the IslandsAdobe · PHONE SCREENAdobe interview questions
- Number of Islands with Diagonal ConnectivityGoogle · ONSITE INTERVIEWGoogle interview questions
- Island Count and Maximum AreaOracle · ONSITE INTERVIEWOracle interview questions
- Maximum Number of Fish in a GridGlobalization Partners · ONSITE INTERVIEW
- Max Area of IslandGoldman Sachs · ONSITE INTERVIEWGoldman Sachs interview questions
- Max Area of IslandRoku · ONSITE INTERVIEWRoku interview questions
- Max Area of IslandBloomberg LP · ONSITE INTERVIEWBloomberg LP interview questions
- Maximum Area of IslandSambaNova Systems · ONSITE INTERVIEWSambaNova Systems interview questions
- Count Connected IslandsTwitch · ONSITE INTERVIEWTwitch interview questions