-
-
Notifications
You must be signed in to change notification settings - Fork 10
/
417 Pacific Atlantic Water Flow.swift
74 lines (63 loc) 路 2.42 KB
/
417 Pacific Atlantic Water Flow.swift
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
//
// 417 Pacific Atlantic Water Flow.swift
// LeetCode-Solutions
//
// Created by Aleksandar Dinic on 25/03/2021.
// Copyright 漏 2021 Aleksandar Dinic. All rights reserved.
//
import Foundation
/// Source: https://leetcode.com/problems/pacific-atlantic-water-flow/
class Solution {
private let directions: [(row: Int, col: Int)] = [(0, 1), (1, 0), (-1, 0), (0, -1)]
private var rows = 0
private var cols = 0
private var landHeights = [[Int]]()
/// Finds the list of grid coordinates where water can flow to both the
/// Pacific and Atlantic oceans.
///
/// - Parameter matrix: Matrix of non-negative integers.
/// - Returns: The list of grid coordinates.
///
/// - Complexity:
/// - time: O(n * m), where n is the number of rows, and m is the number
/// of columns.
/// - space: O(n * m), where n is the number of rows, and m is the number
/// of columns.
func pacificAtlantic(_ matrix: [[Int]]) -> [[Int]] {
guard !matrix.isEmpty, !matrix[0].isEmpty else { return [] }
rows = matrix.count
cols = matrix[0].count
landHeights = matrix
var pacificReachable = [[Bool]](repeating: [Bool](repeating: false, count: cols), count: rows)
var atlanticReachable = [[Bool]](repeating: [Bool](repeating: false, count: cols), count: rows)
for i in 0..<rows {
dfs(i, 0, &pacificReachable)
dfs(i, cols - 1, &atlanticReachable)
}
for i in 0..<cols {
dfs(0, i, &pacificReachable)
dfs(rows - 1, i, &atlanticReachable)
}
var ans = [[Int]]()
for i in 0..<rows {
for j in 0..<cols {
guard pacificReachable[i][j], atlanticReachable[i][j] else { continue }
ans.append([i, j])
}
}
return ans
}
private func dfs(_ row: Int, _ col: Int, _ reachable: inout [[Bool]]) {
reachable[row][col] = true
for direction in directions {
let newRow = row + direction.row
let newCol = col + direction.col
guard newRow >= 0, newRow < rows,
newCol >= 0, newCol < cols,
!reachable[newRow][newCol],
landHeights[newRow][newCol] >= landHeights[row][col]
else { continue }
dfs(newRow, newCol, &reachable)
}
}
}