Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 76
Good morning! Here's your coding interview problem for today.

This problem was asked by Google.

You are given an N by M 2D matrix of lowercase letters. Determine the minimum number of columns that can be removed to ensure that each row is ordered from top to bottom lexicographically. That is, the letter at each column is lexicographically later as you go down each row. It does not matter whether each row itself is ordered lexicographically.

For example, given the following table:
```
cba
daf
ghi
```
This is not ordered because of the a in the center. We can remove the second column to make it ordered:
```
ca
df
gi
```
So your function should return 1, since we only needed to remove 1 column.

As another example, given the following table:

```abcdef```
Your function should return 0, since the rows are already ordered (there's only one row).

As another example, given the following table:
```
zyx
wvu
tsr
```
Your function should return 3, since we would need to remove all the columns to order it.

Pull request:
Day76
Resolves #161 .

Patch:
diff --git a/README.md b/README.md
index fa8dc51..f422f86 100644
--- a/README.md
+++ b/README.md
@@ -85,3 +85,4 @@ problems from
 * [Day 73](https://github.com/vaskoz/dailycodingproblem-go/issues/155)
 * [Day 74](https://github.com/vaskoz/dailycodingproblem-go/issues/157)
 * [Day 75](https://github.com/vaskoz/dailycodingproblem-go/issues/159)
+* [Day 76](https://github.com/vaskoz/dailycodingproblem-go/issues/161)
diff --git a/day76/problem.go b/day76/problem.go
new file mode 100644
index 0000000..4789c58
--- /dev/null
+++ b/day76/problem.go
@@ -0,0 +1,21 @@
+package day76
+
+// MinRemoveColumns determines the minimum number of columns
+// that can be removed to ensure that each row is ordered
+// from top to bottom lexicographically.
+// Runs in O(M*N) checking all input values.
+func MinRemoveColumns(matrix [][]rune) int {
+	if len(matrix) < 2 {
+		return 0
+	}
+	removals := 0
+	for col := 0; col < len(matrix[0]); col++ {
+		for row := 1; row < len(matrix); row++ {
+			if matrix[row][col] < matrix[row-1][col] {
+				removals++
+				break
+			}
+		}
+	}
+	return removals
+}


Test patch:
diff --git a/day76/problem_test.go b/day76/problem_test.go
new file mode 100644
index 0000000..817e6e5
--- /dev/null
+++ b/day76/problem_test.go
@@ -0,0 +1,39 @@
+package day76
+
+import "testing"
+
+var testcases = []struct {
+	input    [][]rune
+	expected int
+}{
+	{[][]rune{
+		[]rune("cba"),
+		[]rune("daf"),
+		[]rune("ghi"),
+	}, 1},
+	{[][]rune{
+		[]rune("abcdef"),
+	}, 0},
+	{[][]rune{
+		[]rune("zyx"),
+		[]rune("wvu"),
+		[]rune("tsr"),
+	}, 3},
+}
+
+func TestMinRemoveColumns(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if result := MinRemoveColumns(tc.input); result != tc.expected {
+			t.Errorf("Expected %v got %v", tc.expected, result)
+		}
+	}
+}
+
+func BenchmarkMinRemoveColumns(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			MinRemoveColumns(tc.input)
+		}
+	}
+}