What is the best way to solve Pacific Atlantic Water Flow?

The optimized O(n) approach using Graphs patterns is generally preferred.

상위 150개 인터뷰쉬움

태평양 대서양 물의 흐름

'태평양 대서양 수류' 문제에 대한 자세한 가이드 및 Python 구현입니다.

문제 설명

쉬움

태평양과 대서양을 모두 접하고 있는 m x n 직사각형 섬이 있습니다. 태평양은 섬의 왼쪽과 위쪽 가장자리에 닿고, 대서양은 섬의 오른쪽과 아래쪽 가장자리에 닿습니다.

섬은 정사각형 셀의 격자로 분할되어 있습니다. 높이[r][c]가 좌표(r, c)에서 셀의 해발 높이를 나타내는 m x n 정수 행렬 높이가 제공됩니다.

이웃 셀의 높이가 현재 셀의 높이보다 작거나 같으면 빗물은 바로 북쪽, 남쪽, 동쪽, 서쪽으로 이웃 셀로 흐를 수 있습니다. 물은 바다에 인접한 모든 세포에서 해당 바다로 흐를 수 있습니다.

그리드 좌표 결과의 2D 목록을 반환합니다. 여기서 result[i] = [ri, ci]는 빗물이 셀 (ri, ci)에서 태평양과 대서양 모두로 흐를 수 있음을 나타냅니다.

pacificAtlantic(heights: List[List[int]]) -> List[List[int]] 함수를 작성하세요.

제약

•m == len(heights)
•n == len(heights[0])
•1 <= m, n <= 200
•0 <= heights[i][j] <= 10^5

예

Example 1

Input

heights = [[1,2,2,3,5],[3,2,3,4,4],[2,4,5,3,1],[6,7,1,4,5],[5,1,1,2,4]]

Output

[[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]

Explanation

These coordinates can flow to both Pacific (via top/left) and Atlantic (via bottom/right) oceans.

Example 2

Input

heights = [[1]]

Output

[[0,0]]

Explanation

The single cell borders both oceans directly.

Need a Hint?

세트나 힙과 같은 그래프 관련 데이터 구조를 사용해 보세요.

Edge Cases to Watch

빈 입력 구조
단일 요소 입력
큰 수치 범위

해결할 준비가 되셨나요?

Open the problem in PyRun's browser-based Python editor. Your code runs fully offline — no server required.

편집기에서 열기

인터뷰 통찰력 및 변형

그래프 접근 방식의 논리를 설명하세요.

null 또는 빈 입력과 같은 극단적인 경우에 대해 논의합니다.

복잡성 분석 분석

무차별 대입 복잡성

Time: O(n)•Space: O(1)

왜 시간인가?: Directly evaluates all possibilities.

왜 우주인가?: Uses standard local memory.

최적화된 복잡성

Time: O(n)•Space: O(n)

왜 시간인가?: Optimized paths reduce total operations.

왜 우주인가?: May trade memory for speed.

최적화된 솔루션 Python 코드

컴파일러에서 시도해 보세요

def pacific_atlantic_opt(heights):
    ROWS, COLS = len(heights), len(heights[0])
    pac, atl = set(), set()
    def dfs(r, c, visit, prevHeight):
        if ((r, c) in visit or r < 0 or c < 0 or r == ROWS or c == COLS or heights[r][c] < prevHeight):
            return
        visit.add((r, c))
        dfs(r + 1, c, visit, heights[r][c])
        dfs(r - 1, c, visit, heights[r][c])
        dfs(r, c + 1, visit, heights[r][c])
        dfs(r, c - 1, visit, heights[r][c])
    for c in range(COLS):
        dfs(0, c, pac, heights[0][c])
        dfs(ROWS - 1, c, atl, heights[ROWS - 1][c])
    for r in range(ROWS):
        dfs(r, 0, pac, heights[r][0])
        dfs(r, COLS - 1, atl, heights[r][COLS - 1])
    res = []
    for r in range(ROWS):
        for c in range(COLS):
            if (r, c) in pac and (r, c) in atl:
                res.append([r, c])
    return res

무차별 대입 코드(스포일러 보호)

컴파일러에서 시도해 보세요

def pacific_atlantic_brute(heights):
    res = []
    ROWS, COLS = len(heights), len(heights[0])
    def can_reach(r, c, target_set):
        visited = set()
        q = [(r, c)]
        visited.add((r, c))
        while q:
            curr_r, curr_c = q.pop(0)
            if (curr_r, curr_c) in target_set: return True
            for dr, dc in [[1,0], [-1,0], [0,1], [0,-1]]:
                nr, nc = curr_r + dr, curr_c + dc
                if 0 <= nr < ROWS and 0 <= nc < COLS and (nr, nc) not in visited and heights[nr][nc] <= heights[curr_r][curr_c]:
                    visited.add((nr, nc))
                    q.append((nr, nc))
        return False
    pac_border = set([(0, c) for c in range(COLS)] + [(r, 0) for r in range(ROWS)])
    atl_border = set([(ROWS-1, c) for c in range(COLS)] + [(r, COLS-1) for r in range(ROWS)])
    for r in range(ROWS):
        for c in range(COLS):
            if can_reach(r, c, pac_border) and can_reach(r, c, atl_border):
                res.append([r, c])
    return res