-
Notifications
You must be signed in to change notification settings - Fork 1
/
200-numberOfIslands.js
158 lines (139 loc) · 3.69 KB
/
200-numberOfIslands.js
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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
//URL--
// https://leetcode.com/problems/number-of-islands/
//INSTRUCTIONS--
/* 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--
/*
This solution is O(n) space complexity and O(n) where n is the number of tiles in the grid
*/
/**
* @param {character[][]} grid
* @return {number}
*/
const numIslands = function (grid) {
let count = 0
//if there is no grid or no tiles in the grid
if (!grid) {
return count
}
const visited = {}
const rowCount = grid.length
const colCount = grid[0].length
//starting at the top left of the grid
for (let row = 0; row < rowCount; row++) {
for (let col = 0; col < colCount; col++) {
//if it's a one and non traversed
if (grid?.[row]?.[col] === "1" && visited[`${row}-${col}`] === undefined) {
// increment the island count by one
count++
searchNeighbors(row, col)
}
}
}
function searchNeighbors(row, col) {
//if the tile is in bounds and non traversed
if (grid?.[row]?.[col] === "1" && visited[`${row}-${col}`] === undefined) {
//mark the tile as visited
visited[`${row}-${col}`] = "visited"
//search the vertically and horizontally adjacent tiles
searchNeighbors(row + 1, col)
searchNeighbors(row - 1, col)
searchNeighbors(row, col + 1)
searchNeighbors(row, col - 1)
}
}
//return the island count
return count
}
//TESTCASES--
console.log(numIslands([
["1", "1", "1", "1", "0"],
["1", "1", "0", "1", "0"],
["1", "1", "0", "0", "0"],
["0", "0", "0", "0", "0"]
]), 1);
console.log(numIslands([
["1", "1", "0", "0", "0"],
["1", "1", "0", "0", "0"],
["0", "0", "1", "0", "0"],
["0", "0", "0", "1", "1"]
]), 3);
console.log(numIslands([
["1", "0", "1", "1", "0", "1", "1"]
]), 3);
//optimizations--
/*
In this solution, I changed each traversed land tile to an arbitrary value that is not "1" so that no extra space was required
This solution is O(n) for time complexity where n is the number of tiles in the grid and O(1) for space complexity
*/
/**
* @param {character[][]} grid
* @return {number}
*/
const numIslands2 = function (grid) {
let numOfIslands = 0
//iterate through each island from the top left corner
for (let row = 0; row < grid.length; row++) {
for (let col = 0; col < grid[0].length; col++) {
//if the tile is equal to 1
if (grid[row][col] === "1") {
dfs(row, col)
//add one to the island count
numOfIslands++
}
}
}
function dfs(row, col) {
//if the tile is in bounds and land
if (grid?.[row]?.[col] === "1") {
//set the tile to an arbitrary value that isn't "1" or undefined
grid[row][col] = "2"
//check each horizonantal and vertical neighbor
dfs(row + 1, col)
dfs(row - 1, col)
dfs(row, col + 1)
dfs(row, col - 1)
}
}
//return numOfIslands
return numOfIslands
}
//TESTCASES--
console.log(numIslands2([
["1", "1", "1", "1", "0"],
["1", "1", "0", "1", "0"],
["1", "1", "0", "0", "0"],
["0", "0", "0", "0", "0"]
]), 1);
console.log(numIslands2([
["1", "1", "0", "0", "0"],
["1", "1", "0", "0", "0"],
["0", "0", "1", "0", "0"],
["0", "0", "0", "1", "1"]
]), 3);
console.log(numIslands2([
["1", "0", "1", "1", "0", "1", "1"]
]), 3);