Pattern: Number of Islands: Count Regions in a Grid
mediumNot solved yet
The problem
A city map is a grid given as a list of equal-length strings. "P" is a park cell and "." is anything else. Park cells that touch up, down, left or right belong to the same park (diagonal doesn't count). Write a function that returns how many separate parks there are.
text
1count_parks(["PP..", "P..P", "..PP"]) -> 2
2count_parks(["P.P", ".P.", "P.P"]) -> 5
3count_parks([]) -> 0
Example 1
111222
Two parks. Cells belong together only when they touch up, down, left or right.
In the second example, the cells only touch diagonally, so each one is its own park.
Write count_parks(city) in Python or countParks(city) in JavaScript.
Runs privately in your browser. Nothing is sent to a server.Ctrl/⌘ + Enter to run · Esc then Tab to leave the editor
Write your function, then run it against 20 tests.
Breakdown
Stuck? Reveal one step at a time, and try again after each one.
See the graph
Each park cell is a node, and it's connected to the park cells next to it. A park is a connected component. So the question is: how many components are there?
Step 2
Start a search from each new park
Scan the grid cell by cell. When you find a park cell you haven't seen yet, you've found a new park: add one to the count.
Step 3
Mark the whole park
From that cell, run a DFS or BFS to every connected park cell and mark them all as seen, so they don't get counted again later.
Step by step1 / 4
PPPPPP
An unseen park cell: count 1 park, then flood it.
Step 4
Neighbours and edges
For a cell (r, c), the neighbours are (r+1, c), (r-1, c), (r, c+1) and (r, c-1). Skip any that fall outside the grid, aren't parks, or were already seen.
Solution
Give it a real try first: you learn far more from a wrong attempt than from reading the answer.
Loop over every cell. When a park cell hasn't been seen, count a new park and flood it: use a stack (or queue) to visit every connected park cell, marking each as seen when you add it. Return the count.
python
1def count_parks(city):
2 rows = len(city)
3 cols = len(city[0]) if rows else 0
4 seen = set()
5 parks = 0
6 for r in range(rows):
7 for c in range(cols):
8 if city[r][c] != "P" or (r, c) in seen:
↑not a park, or already counted
9 continue
10 parks += 1 # a park we haven't seen: flood all of it
↑a new park!
11 seen.add((r, c))
12 stack = [(r, c)]
13 while stack:
14 cr, cc = stack.pop()
15 for nr, nc in ((cr + 1, cc), (cr - 1, cc), (cr, cc + 1), (cr, cc - 1)):
16 if 0 <= nr < rows and 0 <= nc < cols and city[nr][nc] == "P" and (nr, nc) not in seen:
17 seen.add((nr, nc))
↑mark when ADDING to the stack
18 stack.append((nr, nc))
19 return parks
↑one count per flood
javascript
1function countParks(city) {
2 const rows = city.length
3 const cols = rows ? city[0].length : 0
4 const seen = new Set()
5 const key = (r, c) => r * cols + c
6 let parks = 0
7 for (let r = 0; r < rows; r++) {
8 for (let c = 0; c < cols; c++) {
9 if (city[r][c] !== "P" || seen.has(key(r, c))) continue
↑not a park, or already counted
10 parks++ // a park we haven't seen: flood all of it
↑a new park!
11 seen.add(key(r, c))
12 const stack = [[r, c]]
13 while (stack.length) {
14 const [cr, cc] = stack.pop()
15 for (const [nr, nc] of [[cr + 1, cc], [cr - 1, cc], [cr, cc + 1], [cr, cc - 1]]) {