417. Pacific Atlantic Water Flow
Tags:
Medium
Skills:
Matrix
June 24, 2025
04:32 AM
No headings found
Loading content...
Related Posts
Leetcode
No headings found
Related Posts
Leetcode
Problem
Cho một matrix heights kích thước m x n, mỗi ô là độ cao. Nước mưa có thể chảy từ ô này sang ô kề (trên, dưới, trái, phải) nếu ô kề có độ cao nhỏ hơn hoặc bằng ô hiện tại
→ Cần tìm tất cả các ô mà nước có thể chảy từ đó đến cả hai biển
Time and space complexity
Solution
1function pacificAtlantic(heights: number[][]): number[][] {
2 const m = heights.length;
3 const n = heights[0].length;
4
5 const pacific = Array.from({
6 length: m
7 }, () => Array(n).fill(false));
8
9 const atlantic = Array.from({
10 length: m
11 }, () => Array(n).fill(false));
12
13 const directions = [
14 [-1, 0], [1, 0], [0, 1], [0, -1]
15 ]
16
17 function dfs(x: number, y: number, visisted: boolean[][]) {
18 visisted[x][y] = true;
19 for (const [dx, dy] of directions) {
20 const nx = dx + x;
21 const ny = dy + y;
22
23 if (nx >= 0 && nx < m && ny >= 0 && ny < n &&
24 !visisted[nx][ny] && heights[nx][ny] >= heights[x][y]) {
25 dfs(nx, ny, visisted)
26 }
27 }
28 }
29
30 // Pacifics: top row and left column
31 for (let i = 0; i < m; i++) dfs(i, 0, pacific);
32 for (let j = 0; j < n; j++) dfs(0, j, pacific);
33
34 // Atlantic: Bottom row and right column
35 for (let i = 0; i < m; i++) dfs(i, n - 1, atlantic)
36 for (let j = 0; j < n; j++) dfs(m - 1, j, atlantic)
37
38 const res: number[][] = [];
39 for (let i = 0; i < m; i++) {
40 for (let j = 0; j < n; j++) {
41 if (pacific[i][j] && atlantic[i][j]) {
42 res.push([i, j]);
43 }
44 }
45 }
46
47 return res;
48};