Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 136
Good morning! Here's your coding interview problem for today.

This question was asked by Google.

Given an N by M matrix consisting only of 1's and 0's, find the largest rectangle containing only 1's and return its area.

For example, given the following matrix:
```
[[1, 0, 0, 0],
 [1, 0, 1, 1],
 [1, 0, 1, 1],
 [0, 1, 0, 0]]
```
Return 4.

Pull request description:
Day136
Resolves #282.

Patch:
diff --git a/README.md b/README.md
index 451ceb1..80f0697 100644
--- a/README.md
+++ b/README.md
@@ -144,3 +144,4 @@ problems from
 * [Day 133](https://github.com/vaskoz/dailycodingproblem-go/issues/275)
 * [Day 134](https://github.com/vaskoz/dailycodingproblem-go/issues/278)
 * [Day 135](https://github.com/vaskoz/dailycodingproblem-go/issues/280)
+* [Day 136](https://github.com/vaskoz/dailycodingproblem-go/issues/282)
diff --git a/day136/problem.go b/day136/problem.go
new file mode 100644
index 0000000..abe65a3
--- /dev/null
+++ b/day136/problem.go
@@ -0,0 +1,46 @@
+package day136
+
+// MaxRectangleOfOnesAreaBrute returns the area of the largest rectangle
+// that contains only 1's.
+// The input is a 2-D matrix of 0's and 1's.
+// Runtime is O(Row*Col*MaxArea) because it checks every possible rectangle of 1's.
+func MaxRectangleOfOnesAreaBrute(matrix [][]int) int {
+	var maxArea int
+	for row := range matrix {
+		for col := 0; col < len(matrix[row]); col++ {
+			if matrix[row][col] == 1 {
+				area := areaOfOnes(matrix, row, col)
+				maxArea = max(area, maxArea)
+			}
+		}
+	}
+	return maxArea
+}
+
+func max(a, b int) int {
+	if a > b {
+		return a
+	}
+	return b
+}
+
+func min(a, b int) int {
+	if a < b {
+		return a
+	}
+	return b
+}
+
+func areaOfOnes(m [][]int, r, c int) int {
+	minWidth := len(m)
+	var colWidth int
+	for i := c; i < len(m[r]) && m[r][i] == 1; i++ {
+		colWidth++
+		var width int
+		for j := r; j < len(m) && m[j][i] == 1; j++ {
+			width++
+		}
+		minWidth = min(width, minWidth)
+	}
+	return colWidth * minWidth
+}


Test patch:
diff --git a/day136/problem_test.go b/day136/problem_test.go
new file mode 100644
index 0000000..c8f1d1f
--- /dev/null
+++ b/day136/problem_test.go
@@ -0,0 +1,50 @@
+package day136
+
+import "testing"
+
+var testcases = []struct {
+	matrix  [][]int
+	maxArea int
+}{
+	{[][]int{
+		{1, 0, 0, 0},
+		{1, 0, 1, 1},
+		{1, 0, 1, 1},
+		{0, 1, 0, 0},
+	}, 4},
+	{[][]int{
+		{1, 1, 1, 1},
+		{0, 0, 0, 0},
+		{0, 0, 0, 0},
+		{0, 0, 0, 0},
+	}, 4},
+	{[][]int{
+		{1, 1, 1, 0},
+		{1, 0, 0, 0},
+		{1, 0, 0, 0},
+		{0, 0, 0, 0},
+	}, 3},
+	{[][]int{
+		{1, 1, 1, 0},
+		{0, 0, 0, 0},
+		{1, 1, 1, 1},
+		{1, 1, 1, 1},
+	}, 8},
+}
+
+func TestMaxRectangleOfOnesAreaBrute(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if result := MaxRectangleOfOnesAreaBrute(tc.matrix); result != tc.maxArea {
+			t.Errorf("Expected %v got %v", tc.maxArea, result)
+		}
+	}
+}
+
+func BenchmarkMaxRectangleOfOnesAreaBrute(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			MaxRectangleOfOnesAreaBrute(tc.matrix)
+		}
+	}
+}