Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 195
Good morning! Here's your coding interview problem for today.

This problem was asked by Google.

Let `A` be an `N by M` matrix in which every row and every column is sorted.

Given `i1, j1, i2, and j2`, compute the number of elements of `M` smaller than `M[i1, j1]` and larger than `M[i2, j2]`.

For example, given the following matrix:
```
[[1, 3, 7, 10, 15, 20],
 [2, 6, 9, 14, 22, 25],
 [3, 8, 10, 15, 25, 30],
 [10, 11, 12, 23, 30, 35],
 [20, 25, 30, 35, 40, 45]]
```
And `i1 = 1, j1 = 1, i2 = 3, j2 = 3`, return `15` as there are 15 numbers in the matrix smaller than 6 or greater than 23.

Pull request:
Day195
Resolves #401.

Patch:
diff --git a/README.md b/README.md
index a2e37e9..02f9827 100644
--- a/README.md
+++ b/README.md
@@ -203,3 +203,4 @@ problems from
 * [Day 190](https://github.com/vaskoz/dailycodingproblem-go/issues/393)
 * [Day 191](https://github.com/vaskoz/dailycodingproblem-go/issues/395)
 * [Day 192](https://github.com/vaskoz/dailycodingproblem-go/issues/397)
+* [Day 195](https://github.com/vaskoz/dailycodingproblem-go/issues/401)
diff --git a/day195/problem.go b/day195/problem.go
new file mode 100644
index 0000000..79773cf
--- /dev/null
+++ b/day195/problem.go
@@ -0,0 +1,61 @@
+package day195
+
+// Matrix is a M by N matrix of integers.
+type Matrix [][]int
+
+// CountLargerAndSmallerBrute computes the number of elements of M smaller
+// than M[i1, j1] and larger than M[i2, j2].
+// Runs in O(M*N) time. Scans the entire matrix.
+func CountLargerAndSmallerBrute(mat Matrix, i1, j1, i2, j2 int) int {
+	count := 0
+	smallerThan := mat[i1][j1]
+	largerThan := mat[i2][j2]
+	for i := range mat {
+		for j := range mat[i] {
+			if mat[i][j] < smallerThan {
+				count++
+			} else if mat[i][j] > largerThan {
+				count++
+			}
+		}
+	}
+	return count
+}
+
+// CountLargerAndSmallerEfficient computes the number of elements of M smaller
+// than M[i1, j1] and larger than M[i2, j2].
+// Runs in O(Answer). Only examines the number of elements in the answer.
+func CountLargerAndSmallerEfficient(mat Matrix, i1, j1, i2, j2 int) int {
+	count := 0
+	smallerThan := mat[i1][j1]
+	for i := range mat {
+		var found bool
+		for _, v := range mat[i] {
+			if v < smallerThan {
+				found = true
+				count++
+			} else {
+				break
+			}
+		}
+		if !found {
+			break
+		}
+	}
+	largerThan := mat[i2][j2]
+	for i := range mat {
+		var found bool
+		for j := range mat[len(mat)-1-i] {
+			if mat[len(mat)-1-i][len(mat[i])-1-j] > largerThan {
+				found = true
+				count++
+			} else {
+				break
+			}
+		}
+		if !found {
+			break
+		}
+	}
+	return count
+}


Test patch:
diff --git a/day195/problem_test.go b/day195/problem_test.go
new file mode 100644
index 0000000..29196f9
--- /dev/null
+++ b/day195/problem_test.go
@@ -0,0 +1,53 @@
+package day195
+
+import "testing"
+
+var testcases = []struct {
+	mat            Matrix
+	i1, j1, i2, j2 int
+	count          int
+}{
+	{Matrix{
+		{1, 3, 7, 10, 15, 20},
+		{2, 6, 9, 14, 22, 25},
+		{3, 8, 10, 15, 25, 30},
+		{10, 11, 12, 23, 30, 35},
+		{20, 25, 30, 35, 40, 45},
+	},
+		1, 1, 3, 3,
+		14},
+}
+
+func TestCountLargerAndSmallerBrute(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if result := CountLargerAndSmallerBrute(tc.mat, tc.i1, tc.j1, tc.i2, tc.j2); result != tc.count {
+			t.Errorf("Expected %v, got %v", tc.count, result)
+		}
+	}
+}
+
+func BenchmarkCountLargerAndSmallerBrute(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			CountLargerAndSmallerBrute(tc.mat, tc.i1, tc.j1, tc.i2, tc.j2)
+		}
+	}
+}
+
+func TestCountLargerAndSmallerEfficient(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if result := CountLargerAndSmallerEfficient(tc.mat, tc.i1, tc.j1, tc.i2, tc.j2); result != tc.count {
+			t.Errorf("Expected %v, got %v", tc.count, result)
+		}
+	}
+}
+
+func BenchmarkCountLargerAndSmallerEfficient(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			CountLargerAndSmallerEfficient(tc.mat, tc.i1, tc.j1, tc.i2, tc.j2)
+		}
+	}
+}