Parking Lot Puddles
After a storm, a drone photographs a parking lot from above and splits the picture into a grid of squares. Each square is marked 1 if it is under water and 0 if it is dry. The maintenance crew sends one person with a squeegee to each puddle, so they need to know how many separate puddles there are.
Water squares that share an edge belong to the same puddle. Water squares that only touch at a corner do not: the crew has found that water does not flow across those diagonal cracks.
Your task
Write countPuddles(lot). lot is a grid of 0s and 1s. Return the number of puddles: groups of 1s joined up, down, left or right.
A grid with no rows, or with no 1s, has 0 puddles.
countPuddles(lot: int[][]) → int
Examples
lot = [[1, 1, 0, 0], [0, 1, 0, 1], [0, 0, 0, 1], [1, 0, 0, 0]]
3
The three 1s in the top-left are one puddle. The two 1s on the right edge are a second. The lone 1 in the bottom-left corner is a third. Total 3.
lot = [[1, 0, 1], [0, 1, 0], [1, 0, 1]]
5
Every wet square touches the others only at corners, so each is its own puddle: 5.
Constraints
- 0 ≤ rows ≤ 20
- 1 ≤ cols ≤ 20 when rows ≥ 1
- lot[r][c] is 0 or 1
Start with brute force
A tempting shortcut is to count a wet square as "the start of a new puddle" when the square above it and the square to its left are both dry. It looks right on blobs, but a U-shaped puddle has two tops, so it gets counted twice. The rule only sees two neighbors, while a puddle can wind around in any direction.
The safe slow version labels every wet square with its own puddle number, then repeatedly sweeps the grid, giving neighbors the smaller of their two labels until nothing changes, then counts distinct labels. That can take many full sweeps. A search from each new puddle finishes in one pass over the grid.
Hints
0 of 4 shown- Hint 1
Picture yourself standing on the top-left wet square of the first example. If you mop up that whole puddle right now, what would the grid look like afterwards?
- Hint 2
Counting puddles is the same as counting how many times you find a wet square that is not part of a puddle you have already handled.
- Hint 3
When you find such a square, you need to visit every square of its puddle so you do not count it again later. Which kind of search visits everything connected to a starting point?
- Hint 4
Scan the grid row by row. Each time you meet a 1, add one to the count and run a depth-first or breadth-first search from it that turns every connected 1 into 0 (or marks it as seen). The scan then skips those squares, so each puddle is counted exactly once.
Walkthrough and solution
Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.
How to solve it
Each puddle is a connected group in a graph where wet squares are nodes and edges join wet squares that share a side. You need the number of groups. The trick is to count a group the first time you touch it, then visit all of it at once so you never count it again.
Trace the first example, scanning row by row:
- (0,0) is wet and unseen. Count = 1. The search from it reaches (0,1), then (1,1). All three are marked seen.
- (0,1) and (1,1) come up later in the scan, but they are already seen, so they are skipped.
- (1,3) is wet and unseen. Count = 2. The search reaches (2,3) below it.
- (3,0) is wet and unseen. Count = 3. It has no wet neighbors, so the search stops at once.
The scan ends with 3. Notice that the U-shaped trap from the brute force section cannot fool this: the search from the first top walks down, along the bottom and up the other arm, so the second top is already seen when the scan reaches it.
function countPuddles(lot) {
const rows = lot.length;
if (rows === 0) return 0;
const cols = lot[0].length;
const seen = lot.map(row => row.map(() => false));
let count = 0;
for (let r = 0; r < rows; r++) {
for (let c = 0; c < cols; c++) {
if (lot[r][c] !== 1 || seen[r][c]) continue;
count++; // a puddle we have not met before
seen[r][c] = true;
const stack = [[r, c]];
while (stack.length > 0) {
const [cr, cc] = stack.pop();
for (const [nr, nc] of [[cr + 1, cc], [cr - 1, cc], [cr, cc + 1], [cr, cc - 1]]) {
if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
if (lot[nr][nc] !== 1 || seen[nr][nc]) continue;
seen[nr][nc] = true;
stack.push([nr, nc]);
}
}
}
}
return count;
}def count_puddles(lot):
rows = len(lot)
if rows == 0:
return 0
cols = len(lot[0])
seen = [[False] * cols for _ in range(rows)]
count = 0
for r in range(rows):
for c in range(cols):
if lot[r][c] != 1 or seen[r][c]:
continue
count += 1 # a puddle we have not met before
seen[r][c] = True
stack = [(r, c)]
while stack:
cr, cc = stack.pop()
for nr, nc in ((cr + 1, cc), (cr - 1, cc), (cr, cc + 1), (cr, cc - 1)):
if 0 <= nr < rows and 0 <= nc < cols and lot[nr][nc] == 1 and not seen[nr][nc]:
seen[nr][nc] = True
stack.append((nr, nc))
return countRun your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.