Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 30
Good morning! Here's your coding interview problem for today.

This problem was asked by Facebook.

You are given an array of non-negative integers that represents a two-dimensional elevation map where each element is unit-width wall and the integer is the height. Suppose it will rain and all spots between two walls get filled up.

Compute how many units of water remain trapped on the map in O(N) time and O(1) space.

For example, given the input [2, 1, 2], we can hold 1 unit of water in the middle.

Given the input [3, 0, 1, 3, 0, 5], we can hold 3 units in the first index, 2 in the second, and 3 in the fourth index (we cannot hold 5 since it would run off to the left), so we can trap 8 units of water.

Pull request description:
Day30
Resolves #69 .

Patch:
diff --git a/README.md b/README.md
index b465c34..fb066e2 100644
--- a/README.md
+++ b/README.md
@@ -43,3 +43,4 @@ problems from
 * [Day 27](https://github.com/vaskoz/dailycodingproblem-go/issues/63)
 * [Day 28](https://github.com/vaskoz/dailycodingproblem-go/issues/65)
 * [Day 29](https://github.com/vaskoz/dailycodingproblem-go/issues/67)
+* [Day 30](https://github.com/vaskoz/dailycodingproblem-go/issues/69)
diff --git a/day30/problem.go b/day30/problem.go
new file mode 100644
index 0000000..d7c3d69
--- /dev/null
+++ b/day30/problem.go
@@ -0,0 +1,43 @@
+package day30
+
+// TrappedWater returns the amount of water that can be trapped.
+// Runs in O(N) time and O(1) space.
+func TrappedWater(heights []int) int {
+	if len(heights) < 3 {
+		return 0
+	}
+	total := 0
+	hl := heights[0]
+	hri, hr := highestToRight(heights, 2)
+	for i := 1; i < len(heights)-1; i++ {
+		h := min(hl, hr)
+		if cavity := h - heights[i]; cavity > 0 {
+			total += cavity
+		}
+		if heights[i] > hl {
+			hl = heights[i]
+		}
+		if i+1 == hri {
+			hri, hr = highestToRight(heights, hri)
+		}
+	}
+	return total
+}
+
+func highestToRight(heights []int, start int) (int, int) {
+	var highest, highestI int
+	for i := start; i < len(heights); i++ {
+		if heights[i] > highest {
+			highest = heights[i]
+			highestI = i
+		}
+	}
+	return highestI, highest
+}
+
+func min(a, b int) int {
+	if a < b {
+		return a
+	}
+	return b
+}


Test patch:
diff --git a/day30/problem_test.go b/day30/problem_test.go
new file mode 100644
index 0000000..e28eff1
--- /dev/null
+++ b/day30/problem_test.go
@@ -0,0 +1,30 @@
+package day30
+
+import "testing"
+
+var testcases = []struct {
+	elevations []int
+	expected   int
+}{
+	{[]int{2, 1}, 0},
+	{[]int{2, 1, 2}, 1},
+	{[]int{3, 0, 1, 3, 0, 5}, 8},
+	{[]int{1, 2, 3, 0, 5}, 3},
+}
+
+func TestTrappedWater(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if result := TrappedWater(tc.elevations); result != tc.expected {
+			t.Errorf("Expected %v but got %v", tc.expected, result)
+		}
+	}
+}
+
+func BenchmarkTrappedWater(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			TrappedWater(tc.elevations)
+		}
+	}
+}