Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 353
Good morning! Here's your coding interview problem for today.

This problem was asked by Square.

You are given a histogram consisting of rectangles of different heights. These heights are represented in an input list, such that `[1, 3, 2, 5]` corresponds to the following diagram:
```
      x
      x  
  x   x
  x x x
x x x x
```
Determine the area of the largest rectangle that can be formed only from the bars of the histogram. For the diagram above, for example, this would be six, representing the `2 x 3` area at the bottom right.

Pull request description:
Day353
Resolves #701.

Patch:
diff --git a/README.md b/README.md
index df0a55c..321ccea 100644
--- a/README.md
+++ b/README.md
@@ -339,3 +339,4 @@ problems from
 * [Day 347](https://github.com/vaskoz/dailycodingproblem-go/issues/689)
 * [Day 350](https://github.com/vaskoz/dailycodingproblem-go/issues/695)
 * [Day 352](https://github.com/vaskoz/dailycodingproblem-go/issues/699)
+* [Day 353](https://github.com/vaskoz/dailycodingproblem-go/issues/701)
diff --git a/day353/problem.go b/day353/problem.go
new file mode 100644
index 0000000..b38be33
--- /dev/null
+++ b/day353/problem.go
@@ -0,0 +1,31 @@
+package day353
+
+// LargestRectangleHistogram returns the area of the
+// largest possible rectangle given the histogram.
+// Runs in O(N) time with O(N) space for the stack.
+func LargestRectangleHistogram(hist []int) int {
+	stack := make([]int, 1, len(hist))
+	stack[0] = -1
+	var result int
+	for i := range hist {
+		for stack[len(stack)-1] != -1 && hist[stack[len(stack)-1]] >= hist[i] {
+			last := stack[len(stack)-1]
+			stack = stack[:len(stack)-1]
+			result = max(result, hist[last]*(i-stack[len(stack)-1]-1))
+		}
+		stack = append(stack, i)
+	}
+	for stack[len(stack)-1] != -1 {
+		last := stack[len(stack)-1]
+		stack = stack[:len(stack)-1]
+		result = max(result, hist[last]*(len(hist)-stack[len(stack)-1]-1))
+	}
+	return result
+}
+
+func max(a, b int) int {
+	if a > b {
+		return a
+	}
+	return b
+}


Test patch:
diff --git a/day353/problem_test.go b/day353/problem_test.go
new file mode 100644
index 0000000..c0a01b2
--- /dev/null
+++ b/day353/problem_test.go
@@ -0,0 +1,29 @@
+package day353
+
+import "testing"
+
+// nolint
+var testcases = []struct {
+	hist []int
+	area int
+}{
+	{[]int{1, 3, 2, 5}, 6},
+	{[]int{6, 2, 5, 4, 5, 1, 6}, 12},
+}
+
+func TestLargestRectangleHistogram(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if area := LargestRectangleHistogram(tc.hist); area != tc.area {
+			t.Errorf("Expected %v, got %v", tc.area, area)
+		}
+	}
+}
+
+func BenchmarkLargestRectangleHistogram(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			LargestRectangleHistogram(tc.hist)
+		}
+	}
+}