Count the Lakes Inside an Island
Updated
Problem statement
An island sits in an endless sea made of square cells. You are given island, the list of the island's cells as [row, column] pairs, in any order. Every other cell is water.
Water moves only between two cells that share a side. It cannot pass between two cells that touch only at a corner.
A lake is a group of water cells, connected through shared sides, that the island closes in completely: no path of water cells leads from the group to the open sea far away from the island. A pocket of water that does reach the open sea is a bay, not a lake.
Return the number of lakes. Each connected group of lake cells counts once, however many cells it has.
Function
countLakes(island: int[][]) → intExamples
Example 1
island = [[0,0],[0,1],[0,2],[1,0],[1,2],[2,0],[2,1],[2,2]]return = 1The 8 cells form a ring around the cell [1, 1]. That cell is water, and all four of its sides touch the island, so water there cannot reach the sea. It is the only lake.
Example 2
island = [[0,0],[0,1],[0,2],[0,3],[0,4],[0,6],[1,0],[1,2],[1,6],[2,0],[2,1],[2,2],[2,3],[2,4],[2,5],[2,6]]return = 1The water cell [1, 1] is closed in on all four sides, so it is a lake. The water cells [1, 3], [1, 4] and [1, 5] connect to [0, 5], which opens to the sea above the island. That pocket is a bay, not a lake. The answer is 1.
Example 3
island = [[2,2],[0,1],[1,0],[0,0],[2,1],[1,2],[0,2]]return = 1The cells can come in any order. They form a ring around [1, 1] with the corner [2, 0] missing. Water at [1, 1] touches [2, 0] only at a corner, and water cannot pass through a corner, so [1, 1] is still a lake. The answer is 1.
Constraints
1 <= island.length <= 1000island[i].length == 20 <= island[i][0], island[i][1] <= 10^9- All cells are different, and the island is connected: from any island cell you can reach every other island cell by moving between island cells that share a side.
More Google Onsite Interview questions
- Delete Nodes and Return Forest RootsONSITE INTERVIEW · Seen Nov 2026
- Dice-Walk Winning ProbabilityPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- First and Last Target Position in a Mountain ArrayONSITE INTERVIEW · Seen Nov 2026
- Lowest Common Ancestor in an N-ary TreePHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- 0/1 Knapsack with Weight and Volume LimitsONSITE INTERVIEW · Seen Nov 2026
- Batched Subsequence Word MatchesONSITE INTERVIEW · Seen Nov 2026
- Course Schedule Cycle DetectionPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Filesystem Entity Total SizeONSITE INTERVIEW · Seen Nov 2026
- Longest Subarray Within an Absolute-Difference LimitONSITE INTERVIEW · Seen Nov 2026
- Reach a Destination Through Scheduled FlightsPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
Similar questions at other companies
- Number of IslandsAmazon · PHONE SCREEN · ONSITE INTERVIEW
- Island Count and Maximum AreaOracle · ONSITE INTERVIEWOracle interview questions
- Mouse and Cheese ReachabilityMeta · ONSITE INTERVIEWMeta interview questions
- Number of IslandsTripjack · ONSITE INTERVIEWTripjack interview questions
- Number of IslandsTekion · ONSITE INTERVIEWTekion interview questions
- Grid Pathfinding with Obstacles (DFS)Roblox · PHONE SCREEN · ONSITE INTERVIEWRoblox interview questions
- Number of IslandsGoldman Sachs · OA · PHONE SCREEN · ONSITE INTERVIEWGoldman Sachs interview questions
- Number of IslandsBloomberg LP · PHONE SCREEN · ONSITE INTERVIEWBloomberg LP interview questions
- Number of IslandsCrowdstrike · ONSITE INTERVIEWCrowdstrike interview questions
- Max Area of IslandRoku · ONSITE INTERVIEWRoku interview questions