Find Lakes
Updated
Problem statement
You are given an m x n map grid where grid[i][j] == 1 is land and grid[i][j] == 0 is water. Everything outside the grid is open sea.
Water moves only between cells that share a side (up, down, left or right). Two water cells that touch only at a corner are not joined.
A water cell on the outer edge of the grid is part of the sea, and so is every water cell joined to it through other water cells. Every other group of joined water cells is a lake: it is closed in by land on all sides.
Return the number of lakes in grid.
Function
countLakes(grid: int[][]) → intExamples
Example 1
grid = [[0,0,0,0,0],[0,1,1,1,0],[0,1,0,1,0],[0,1,1,1,0],[0,0,0,0,0]]return = 1Rows and columns are numbered from 0. The water cell at row 2, column 2 has land on all four sides, so it is one lake. Every other water cell is on the outer edge of the grid, so it is sea.
Example 2
grid = [[1,1,1,1,1,1],[1,0,1,1,0,0],[1,1,0,1,1,1],[1,1,1,1,0,1],[1,1,1,1,1,1]]return = 3The water cells at (row 1, column 1) and (row 2, column 2) touch only at a corner, so water cannot flow between them: they are two separate lakes. The water cell at (row 3, column 4) is a third lake. The water cell at (row 1, column 4) shares a side with (row 1, column 5), which is on the right edge, so both are sea.
Example 3
grid = [[1,1,1,1],[1,0,0,1],[1,1,0,1],[1,1,0,1]]return = 0The four water cells form one group: (row 1, column 1), (row 1, column 2), (row 2, column 2) and (row 3, column 2). The last one is on the bottom edge, so the whole group is sea and there is no lake.
Constraints
m == grid.lengthn == grid[i].length1 <= m, n <= 200grid[i][j]is0or1.
More Airbnb Phone Screen questions
- Read Across Sound TracksPHONE SCREEN · Seen Nov 2026
- Text JustificationPHONE SCREEN · Seen Nov 2026
- Decode and Store StringsPHONE SCREEN · Seen Oct 2026
- Print Sentences as TablePHONE SCREEN · ONSITE INTERVIEW · Seen Sep 2026
- Detonate Bombs with Chain ReactionsPHONE SCREEN · Seen Aug 2026
- Smallest Common RegionPHONE SCREEN · Seen Aug 2026
- Longest Chain BookingPHONE SCREEN · Seen Aug 2026
- Nested List Iterator with RemovePHONE SCREEN · Seen Jul 2026
- Parse Query StringPHONE SCREEN · Seen May 2026
- Pacific Atlantic Water FlowPHONE SCREEN · Seen May 2023
Similar questions at other companies
- Max Area of Island Without Changing the GridFlexport · PHONE SCREENFlexport interview questions
- Count Islands with Eight-Direction AdjacencyAmazon · PHONE SCREEN
- Count Islands in a Binary GridApple · PHONE SCREENApple interview questions
- Pacific Atlantic Water FlowAnduril · PHONE SCREENAnduril interview questions
- House Bounds in a Ragged GridRippling · OA · PHONE SCREENRippling interview questions
- Maximum Damage PatchGecko Robotics · OA · PHONE SCREEN
- Count the IslandsAdobe · PHONE SCREENAdobe interview questions
- Maximum Area of IslandSkydio · PHONE SCREENSkydio interview questions
- Number of IslandsIntuit · ONSITE INTERVIEWIntuit interview questions
- Number of Islands with Diagonal ConnectivityGoogle · ONSITE INTERVIEWGoogle interview questions
Interview reports that mention this question
Airbnb interview experiences
- Airbnb SWE OA: Four-Level Banking System: 1 Experience
- Airbnb Campus and Full-Time SWE OA / Interviews: 9 Experiences
- Airbnb Intern OA and Phone Screens: 17 Experiences (Part 6 of 7)
- Airbnb Intern OA and Onsite Rounds: 16 Experiences (Part 5 of 7)
- Airbnb Intern OA, Diplomacy Game: 19 Experiences (Part 4 of 7)