Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 84
Good morning! Here's your coding interview problem for today.

This problem was asked by Amazon.

Given a matrix of 1s and 0s, return the number of "islands" in the matrix. A 1 represents land and 0 represents water, so an island is a group of 1s that are neighboring and their perimiter is surrounded by water.

For example, this matrix has 4 islands.
```
1 0 0 0 0
0 0 1 1 0
0 1 1 0 0
0 0 0 0 0
1 1 0 0 1
1 1 0 0 1
```

Pull request:
Day84
Resolves #177.

Patch:
diff --git a/README.md b/README.md
index 31366ee..18ee758 100644
--- a/README.md
+++ b/README.md
@@ -93,3 +93,4 @@ problems from
 * [Day 81](https://github.com/vaskoz/dailycodingproblem-go/issues/171)
 * [Day 82](https://github.com/vaskoz/dailycodingproblem-go/issues/173)
 * [Day 83](https://github.com/vaskoz/dailycodingproblem-go/issues/175)
+* [Day 84](https://github.com/vaskoz/dailycodingproblem-go/issues/177)
diff --git a/day84/problem.go b/day84/problem.go
new file mode 100644
index 0000000..342955b
--- /dev/null
+++ b/day84/problem.go
@@ -0,0 +1,42 @@
+package day84
+
+// CountIslands returns the number of islands.
+// 1 represents land, and 0 represents water.
+// Runs in O(GridSize) and uses O(GridSize) space.
+func CountIslands(grid [][]int) int {
+	visited := make([][]bool, len(grid))
+	for i := range visited {
+		visited[i] = make([]bool, len(grid[i]))
+	}
+	islands := 0
+	for i := range grid {
+		for j := range grid[i] {
+			if grid[i][j] == 1 && !visited[i][j] {
+				islands++
+				exploreIsland(grid, visited, i, j)
+			}
+		}
+	}
+	return islands
+}
+
+// exploreIsland is a DFS of the island
+func exploreIsland(grid [][]int, visited [][]bool, i, j int) {
+	visited[i][j] = true
+	if up := i - 1; up >= 0 && isUnexplored(grid[up][j], visited[up][j]) {
+		exploreIsland(grid, visited, up, j)
+	}
+	if down := i + 1; down < len(grid) && isUnexplored(grid[down][j], visited[down][j]) {
+		exploreIsland(grid, visited, down, j)
+	}
+	if left := j - 1; left >= 0 && isUnexplored(grid[i][left], visited[i][left]) {
+		exploreIsland(grid, visited, i, left)
+	}
+	if right := j + 1; right < len(grid[i]) && isUnexplored(grid[i][right], visited[i][right]) {
+		exploreIsland(grid, visited, i, right)
+	}
+}
+
+func isUnexplored(gridValue int, visitedStatus bool) bool {
+	return gridValue == 1 && !visitedStatus
+}


Test patch:
diff --git a/day84/problem_test.go b/day84/problem_test.go
new file mode 100644
index 0000000..2ab1695
--- /dev/null
+++ b/day84/problem_test.go
@@ -0,0 +1,34 @@
+package day84
+
+import "testing"
+
+var testcases = []struct {
+	grid     [][]int
+	expected int
+}{
+	{[][]int{
+		{1, 0, 0, 0, 0},
+		{0, 0, 1, 1, 0},
+		{0, 1, 1, 0, 0},
+		{0, 0, 0, 0, 0},
+		{1, 1, 0, 0, 1},
+		{1, 1, 0, 0, 1},
+	}, 4},
+}
+
+func TestCountIslands(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if result := CountIslands(tc.grid); result != tc.expected {
+			t.Errorf("Expected %v got %v", tc.expected, result)
+		}
+	}
+}
+
+func BenchmarkCountIslands(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			CountIslands(tc.grid)
+		}
+	}
+}