Problems › TypeScript › patterns
How many separate areas on the map
A coverage map marks every square metre as served or not. Planning wants the number of separate served areas, so a served square touching another one edge to edge belongs to the same area.
- A cell holding 1 is served; 0 is not.
- Two served cells belong to the same area when they touch above, below, left or right — not diagonally.
- Return how many separate served areas there are.
- An empty map has no areas.
countRegions(coverage: list<list<int>>) → int
Where you start
function countRegions(coverage: number[][]): number {
}Worked examples
| Call | Result |
|---|---|
countRegions([[1,1,0],[0,1,0],[0,0,1]]) | 2 |
countRegions([[1,0,1],[0,0,0],[1,0,1]]) | 4 |
countRegions([[0,0],[0,0]]) | 0 |
countRegions([[1,1],[1,1]]) | 1 |
Hint
Walk every cell. The first time you meet an unvisited served cell, that is a new area — then flood outwards from it, marking everything it reaches, so you never count it twice.
Reference solution in TypeScript
function countRegions(coverage: number[][]): number {
if (coverage.length === 0) return 0;
const rows = coverage.length;
const cols = coverage[0].length;
const seen: boolean[][] = coverage.map((row) => row.map(() => false));
const flood = (r: number, c: number): void => {
if (r < 0 || r >= rows || c < 0 || c >= cols) return;
if (seen[r][c] || coverage[r][c] !== 1) return;
seen[r][c] = true;
flood(r + 1, c);
flood(r - 1, c);
flood(r, c + 1);
flood(r, c - 1);
};
let areas = 0;
for (let r = 0; r < rows; r += 1) {
for (let c = 0; c < cols; c += 1) {
if (coverage[r][c] === 1 && !seen[r][c]) {
areas += 1;
flood(r, c);
}
}
}
return areas;
}