Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 293
Good morning! Here's your coding interview problem for today.

This problem was asked by Uber.

You have N stones in a row, and would like to create from them a pyramid. This pyramid should be constructed such that the height of each stone increases by one until reaching the tallest stone, after which the heights decrease by one. In addition, the start and end stones of the pyramid should each be one stone high.

You can change the height of any stone by paying a cost of `1` unit to lower its height by `1`, as many times as necessary. Given this information, determine the lowest cost method to produce this pyramid.

For example, given the stones `[1, 1, 3, 3, 2, 1]`, the optimal solution is to pay `2` to create `[0, 1, 2, 3, 2, 1]`.

Pull request:
Day293
Resolves #599.

Patch:
diff --git a/README.md b/README.md
index 0393895..8fe170d 100644
--- a/README.md
+++ b/README.md
@@ -303,6 +303,7 @@ problems from
 * [Day 290](https://github.com/vaskoz/dailycodingproblem-go/issues/594)
 * [Day 291](https://github.com/vaskoz/dailycodingproblem-go/issues/596)
 * [Day 292](https://github.com/vaskoz/dailycodingproblem-go/issues/598)
+* [Day 293](https://github.com/vaskoz/dailycodingproblem-go/issues/599)
 * [Day 294](https://github.com/vaskoz/dailycodingproblem-go/issues/600)
 * [Day 295](https://github.com/vaskoz/dailycodingproblem-go/issues/601)
 * [Day 296](https://github.com/vaskoz/dailycodingproblem-go/issues/605)
diff --git a/day293/problem.go b/day293/problem.go
new file mode 100644
index 0000000..22879c5
--- /dev/null
+++ b/day293/problem.go
@@ -0,0 +1,67 @@
+package day293
+
+// LowestCostPyramid returns the lowest cost option.
+// O(N) time and O(2*N) space.
+func LowestCostPyramid(stones []int) ([]int, int) {
+	left := make([]int, len(stones))
+	right := make([]int, len(stones))
+
+	left[0] = min(stones[0], 1)
+	for i := 1; i < len(stones); i++ {
+		left[i] = min(stones[i],
+			min(left[i-1]+1, i+1))
+	}
+
+	right[len(right)-1] = min(stones[len(stones)-1], 1)
+
+	for i := len(right) - 2; i >= 0; i-- {
+		right[i] = min(stones[i],
+			min(right[i+1]+1, len(right)-i))
+	}
+
+	maxI := 0
+	totalMaxI := min(left[0], right[0])
+
+	for i := range stones {
+		totalI := min(left[i], right[i])
+		if totalI > totalMaxI {
+			maxI = i
+			totalMaxI = totalI
+		}
+	}
+
+	cost := 0
+	height := totalMaxI
+
+	pyramid := make([]int, len(stones))
+
+	for x := maxI; x >= 0; x-- {
+		cost += stones[x] - height
+		pyramid[x] = height
+
+		if height > 0 {
+			height--
+		}
+	}
+
+	height = totalMaxI - 1
+
+	for x := maxI + 1; x < len(stones); x++ {
+		cost += stones[x] - height
+		pyramid[x] = height
+
+		if height > 0 {
+			height--
+		}
+	}
+
+	return pyramid, cost
+}
+
+func min(a, b int) int {
+	if a < b {
+		return a
+	}
+
+	return b
+}


Test patch:
diff --git a/day293/problem_test.go b/day293/problem_test.go
new file mode 100644
index 0000000..18f3779
--- /dev/null
+++ b/day293/problem_test.go
@@ -0,0 +1,57 @@
+package day293
+
+import (
+	"reflect"
+	"testing"
+)
+
+// nolint
+var testcases = []struct {
+	stones, pyramid []int
+	cost            int
+}{
+	{
+		[]int{1, 1, 3, 3, 2, 1},
+		[]int{0, 1, 2, 3, 2, 1},
+		2,
+	},
+	{
+		[]int{0, 0, 0, 9, 9, 0},
+		[]int{0, 0, 0, 1, 0, 0},
+		17,
+	},
+	{
+		[]int{2, 9, 7, 1},
+		[]int{1, 2, 1, 0},
+		15,
+	},
+	{
+		[]int{2, 9, 7, 9, 9},
+		[]int{1, 2, 3, 2, 1},
+		27,
+	},
+	{
+		[]int{9, 9, 9},
+		[]int{1, 2, 1},
+		23,
+	},
+}
+
+func TestLowestCostPyramid(t *testing.T) {
+	t.Parallel()
+
+	for _, tc := range testcases {
+		if pyramid, cost := LowestCostPyramid(tc.stones); cost != tc.cost ||
+			!reflect.DeepEqual(tc.pyramid, pyramid) {
+			t.Errorf("Expected (%v,%v), got (%v,%v)", tc.pyramid, tc.cost, pyramid, cost)
+		}
+	}
+}
+
+func BenchmarkLowestCostPyramid(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			LowestCostPyramid(tc.stones)
+		}
+	}
+}