leetCodeGrid.swift

// https://leetcode.com/problems/number-of-islands/
// Time: n*m, Space 1
func numIslands(_ grid: [[Character]]) -> Int {
    var gridCopy = grid
    var islandCount = 0

    for i in 0..<gridCopy.count {
        for j in 0..<gridCopy[0].count {
            if gridCopy[i][j] != "0" {
                markAdjacentLands(i, j, inGrid: &gridCopy)
                islandCount += 1
            } 
        }
    }

    return islandCount
}

func markAdjacentLands(_ i: Int, _ j: Int, inGrid grid: inout [[Character]]) {
    let maxI = grid.count - 1
    let maxJ = grid[0].count - 1

    if i < 0 || i > maxI || j < 0 || j > maxJ || grid[i][j] == "0" { return }
    grid[i][j] = "0"
    markAdjacentLands(i - 1, j, inGrid: &grid)
    markAdjacentLands(i + 1, j, inGrid: &grid)
    markAdjacentLands(i, j - 1, inGrid: &grid)
    markAdjacentLands(i, j + 1, inGrid: &grid)
}


// Time: m*n, Space: m*n
func pacificAtlantic(_ matrix: [[Int]]) -> [[Int]] {
    if matrix.isEmpty { return [] }

    var pacific = Array(repeating: Array(repeating: false, count: matrix[0].count), 
                        count: matrix.count)
    var atlantic = Array(repeating: Array(repeating: false, count: matrix[0].count), 
                         count: matrix.count)

    // traverse left & right borders of the grid
    for i in 0..<matrix.count {
        dfs(matrix, i, 0, Int.min, &pacific)
        dfs(matrix, i, matrix[0].count - 1, Int.min, &atlantic)
    }

    // traverse top & bottom borders of the grid
    for i in 0..<matrix[0].count {
        dfs(matrix, 0, i, Int.min, &pacific)
        dfs(matrix, matrix.count - 1, i, Int.min, &atlantic)
    }

    var result = [[Int]]()
    // compare pacific and atlantic, return the matchings
    for i in 0..<matrix.count {
        for j in 0..<matrix[0].count {
            if pacific[i][j] && atlantic[i][j] {
                result.append([i, j])
            }
        }
    }

    return result
}

func dfs(_ matrix: [[Int]], _ row: Int, _ col: Int, _ prevVal: Int, _ ocean: inout [[Bool]]) {
    // check conditions
    if row < 0 || row > matrix.count - 1 || col < 0 || col > matrix[0].count - 1 { return }
    if matrix[row][col] < prevVal { return }
    if ocean[row][col] { return }

    ocean[row][col] = true

    dfs(matrix, row - 1, col, matrix[row][col], &ocean)
    dfs(matrix, row + 1, col, matrix[row][col], &ocean)
    dfs(matrix, row, col - 1, matrix[row][col], &ocean)
    dfs(matrix, row, col + 1, matrix[row][col], &ocean)
}