# 2022-06-02

## 200. Number of Islands

### Description

Given an `m x n` 2D binary grid `grid` which represents a map of `'1'`s (land) and `'0'`s (water), return the number of islands.

An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example 1:

``````Input: grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]
Output: 1``````

Example 2:

``````Input: grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
Output: 3``````

Constraints:

• `m == grid.length`

• `n == grid[i].length`

• `1 <= m, n <= 300`

• `grid[i][j]` is `'0'` or `'1'`.

### Solution

#### Approach #0: BFS

``````var (
dx = []int{0, 1, 0, -1}
dy = []int{1, 0, -1, 0}
)

func numIslands(grid [][]byte) (ans int) {
if len(grid) == 0 {
return 0
}
m, n := len(grid), len(grid[0])
var queue [][]int
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
if grid[i][j] == '0' {
continue
}
ans++
queue = append(queue, []int{i, j})
for len(queue) > 0 {
x, y := queue[0][0], queue[0][1]
queue = queue[1:]
if grid[x][y] == '0' {
continue
}
grid[x][y] = '0'
for k := 0; k < 4; k++ {
xx, yy := x+dx[k], y+dy[k]
if xx >= 0 && xx < m && yy >= 0 && yy < n && grid[xx][yy] > '0' {
queue = append(queue, []int{xx, yy})
}
}
}
}
}
return ans
}``````

#### Approach #1: DFS

``````var (
dx = []int{0, 1, 0, -1}
dy = []int{1, 0, -1, 0}
)

func numIslands(grid [][]byte) (ans int) {
if len(grid) == 0 {
return 0
}
m, n := len(grid), len(grid[0])
var dfs func(x, y int)
dfs = func(x, y int) {
if grid[x][y] == '0' {
return
}
grid[x][y] = '0'
for i := 0; i < 4; i++ {
xx, yy := x+dx[i], y+dy[i]
if xx >= 0 && xx < m && yy >= 0 && yy < n && grid[xx][yy] > '0' {
dfs(xx, yy)
}
}
}
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
if grid[i][j] == '0' {
continue
}
ans++
dfs(i, j)
}
}
return ans
}``````

## 547. Number of Provinces

### Description

There are `n` cities. Some of them are connected, while some are not. If city `a` is connected directly with city `b`, and city `b` is connected directly with city `c`, then city `a` is connected indirectly with city `c`.

A province is a group of directly or indirectly connected cities and no other cities outside of the group.

You are given an `n x n` matrix `isConnected` where `isConnected[i][j] = 1` if the `ith` city and the `jth` city are directly connected, and `isConnected[i][j] = 0` otherwise.

Return the total number of provinces.

Example 1:

``````Input: isConnected = [[1,1,0],[1,1,0],[0,0,1]]
Output: 2``````

Example 2:

``````Input: isConnected = [[1,0,0],[0,1,0],[0,0,1]]
Output: 3 ``````

Constraints:

• `1 <= n <= 200`

• `n == isConnected.length`

• `n == isConnected[i].length`

• `isConnected[i][j]` is `1` or `0`.

• `isConnected[i][i] == 1`

• `isConnected[i][j] == isConnected[j][i]`

### Solution

#### Approach #0

``````func findCircleNum(isConnected [][]int) (ans int) {
if len(isConnected) == 0 {
return 0
}
m := len(isConnected)
var dfs func(x, y int)
dfs = func(x, y int) {
for i := 0; i < m; i++ {
if isConnected[y][i] == 0 {
continue
}
isConnected[y][i] = 0
if isConnected[i][y] > 0 {
dfs(y, i)
}
}
}
for i := 0; i < m; i++ {
for j := 0; j < m; j++ {
if isConnected[i][j] == 0 {
continue
}
ans++
if isConnected[j][i] > 0 {
dfs(i, j)
}
}
}
return ans
}``````

#### Approach #1

``````func findCircleNum(isConnected [][]int) (ans int) {
if len(isConnected) == 0 {
return 0
}
m := len(isConnected)
vis := make([]bool, m)
var queue []int
for i, ok := range vis {
if !ok {
ans++
queue = append(queue, i)
for len(queue) > 0 {
j := queue[0]
vis[j] = true
queue = queue[1:]
for k := 0; k < m; k++ {
if isConnected[j][k] == 1 && !vis[k] {
queue = append(queue, k)
}
}
}
}
}
return ans
}``````

## 450. Delete Node in a BST

### Description

Given a root node reference of a BST and a key, delete the node with the given key in the BST. Return the root node reference (possibly updated) of the BST.

Basically, the deletion can be divided into two stages:

1. Search for a node to remove.

2. If the node is found, delete the node.

Example 1:

``````Input: root = [5,3,6,2,4,null,7], key = 3
Output: [5,4,6,2,null,null,7]
Explanation: Given key to delete is 3. So we find the node with value 3 and delete it.
One valid answer is [5,4,6,2,null,null,7], shown in the above BST.
Please notice that another valid answer is [5,2,6,null,4,null,7] and it's also accepted.``````

Example 2:

``````Input: root = [5,3,6,2,4,null,7], key = 0
Output: [5,3,6,2,4,null,7]
Explanation: The tree does not contain a node with value = 0.``````

Example 3:

``````Input: root = [], key = 0
Output: []``````

Constraints:

• The number of nodes in the tree is in the range `[0, 10^4]`.

• `-10^5 <= Node.val <= 10^5`

• Each node has a unique value.

• `root` is a valid binary search tree.

• `-10^5 <= key <= 10^5`

Follow up: Could you solve it with time complexity `O(height of tree)`?

### Solution

#### Approach #0

``````/**
* Definition for a binary tree node.
* type TreeNode struct {
*     Val int
*     Left *TreeNode
*     Right *TreeNode
* }
*/
func deleteNode(root *TreeNode, key int) *TreeNode {
var pre *TreeNode
cur := root
for cur != nil {
if cur.Val == key {
if cur.Left == nil {
if cur == root {
return root.Right
}
if pre.Val > cur.Val {
pre.Left = cur.Right
} else {
pre.Right = cur.Right
}
return root
}
if cur.Right == nil {
if cur == root {
return root.Left
}
if pre.Val > cur.Val {
pre.Left = cur.Left
} else {
pre.Right = cur.Left
}
return root
}
target := cur
pre = cur
cur = cur.Right
for cur.Left != nil {
pre = cur
cur = cur.Left
}
if pre.Val > cur.Val {
pre.Left = cur.Right
} else {
pre.Right = cur.Right
}
target.Val = cur.Val
return root
}
pre = cur
if cur.Val > key {
cur = cur.Left
} else {
cur = cur.Right
}
}
return root
}``````

#### Approach #1: Recursive

``````/**
* Definition for a binary tree node.
* type TreeNode struct {
*     Val int
*     Left *TreeNode
*     Right *TreeNode
* }
*/
func deleteNode(root *TreeNode, key int) *TreeNode {
switch {
case root == nil:
return nil
case root.Val > key:
root.Left = deleteNode(root.Left, key)
case root.Val < key:
root.Right = deleteNode(root.Right, key)
case root.Left == nil:
return root.Right
case root.Right == nil:
return root.Left
default:
cur := root.Right
for cur.Left != nil {
cur = cur.Left
}
cur.Right = deleteNode(root.Right, cur.Val)
cur.Left = root.Left
return cur
}
return root
}``````

Last updated