Google Interview Question
Software DevelopersCountry: United States
Interview Type: In-Person
I have an O(log n) solution.
Binary search the middle row. Now you know the x and y of the middle 1. We break the matrix into four rectangular sections. Everything on the upper left of the middle 1 must be a 0. Everything on the bottom right of the middle 1 must be a 1. This leaves the bottom left and the upper right. Those two sections are smaller versions of the original problem so we recurse on those sections. Performing the binary search takes (log n), and since we are breaking the problem in half each time, there will be (log n) recursions. The next recursions perform a binary search taking time (log n/2), (log n/4), etc. This results in O( log n + log n/2 + log n/4 + ...) which amortizes to O(log n).
Simple python solution based on binary search
def count_zeros(m):
high = len(m[0]) - 1
count = 0
for i in range(len(m)):
low = 0
if m[i][high] == 0:
# All zeros in this row
count += high + 1
continue
if m[i][low] == 1:
# No more zeros around
break
while low <= high:
# Binary search for the
# first one of the row
mid = (low + high)/2
if m[i][mid] == 1:
high = mid - 1
if m[i][mid - 1] == 0:
break
else:
low = mid + 1
count += high + 1
return count
assert count_zeros([[0, 0, 1],
[0, 1, 1],
[1, 1, 1]]) == 3
assert count_zeros([[0, 0],
[0, 0]]) == 4
assert count_zeros([[1, 1, 1, 1],
[1, 1, 1, 1],
[1, 1, 1, 1],
[1, 1, 1, 1]]) == 0
assert count_zeros([[0, 0, 0, 0],
[0, 0, 0, 1],
[1, 1, 1, 1],
[1, 1, 1, 1]]) == 7
assert count_zeros([[0]]) == 1
assert count_zeros([[1]]) == 0
static int getNumOfZeroes(int a[][]) {
int count=0;
for(int i=0; i < a.length; ++i) {
int index=binarySearchUpper(a[i]);
if(index > -1) {
count += index;
}
}
return count;
}
static int binarySearchUpper(int[] a) {
int low=0;
int high=a.length;
int lower=-1;
for(int i =0; i < a.length; ++i) {
int m = (low + high) / 2;
if(a[m] == 0) {
low = m + 1;
lower = m;
} else {
high = m - 1;
}
}
return lower+1;
}
public static void main(String... args) {
int[][] a = { {0,0,1}, {0,1,1}, {0,1,1}};
System.out.println(getNumOfZeroes(a));
}
static int getNumOfZeroes(int a[][]) {
int count=0;
for(int i=0; i < a.length; ++i) {
int index=binarySearchUpper(a[i]);
if(index > -1) {
count += index;
}
}
return count;
}
static int binarySearchUpper(int[] a) {
int low=0;
int high=a.length;
int lower=-1;
for(int i =0; i < a.length; ++i) {
int m = (low + high) / 2;
if(a[m] == 0) {
low = m + 1;
lower = m;
} else {
high = m - 1;
}
}
return lower+1;
}
My initial solution was just to do a binary search in each row, and add the index of the first 1 to a count of zeros - O(n * log n).
My second solution was to preform two binary searches. First a horizontal one, then a vertical one on the column returned by the horizontal one. This yields a section of the matrix that is all zeros, which we can add to the count by multiplying the horizontal and vertical indices. We then decrement the column, increment the row, and recurse. This solution performs better in the case of many zeros (for example, a matrix of all 0s takes log(n) instead of n*log(n)), but I believe this remains O(n * log n) in the worst case.
If we had a matrix with a diagonal separating the 0s and 1s, then we do log(n) + log (n-1) + ... + log(1) = log (n * (n - 1) * ... * 1) = log(n!) = n * log (n) work.
int getZeroCount(int (*arr)[MAX_SIZE], int size)
{
int ret = 0;
int x=0;
int y=0;
//find last 0 of 1st row.
for(int i=0;i<size;i++)
{
if(arr[x][i] > 0 || i == size-1)
{
y = i;
ret = i;
if(i == size-1) ret++;
x++;
break;
}
}
//move backward until find 0 of next row.
while(x > -1 && y > -1 && x < size && y < size)
{
if(arr[x][y] > 0)
{
y--;
}
else if(arr[x][y] == 0)
{
ret += y + 1;
x++;
}
}
return ret;
}
What if you just sum each of the arrays that form the matrix and substract "n"?
import operator
def main():
matrix = [[0, 0, 1, 0], [1, 1, 0, 1], [0, 0, 0, 0], [0, 0, 1, 0]]
matrixLength = len(matrix)
result = sum([getZeros(matrix[i], matrixLength) for i in range(matrixLength)])
print result
def getZeros(array, length):
return length - reduce(operator.add, array)
What if you just sum each of the arrays that form the matrix and substract "n"?
import operator
def main():
matrix = [[0, 0, 1, 0], [1, 1, 0, 1], [0, 0, 0, 0], [0, 0, 1, 0]]
matrixLength = len(matrix)
result = sum([getZeros(matrix[i], matrixLength) for i in range(matrixLength)])
print result
def getZeros(array, length):
return length - reduce(operator.add, array)
What if you just sum each of the arrays that form the matrix and substract "n"?
import operator
def main():
matrix = [[0, 0, 1, 0], [1, 1, 0, 1], [0, 0, 0, 0], [0, 0, 1, 0]]
matrixLength = len(matrix)
result = sum([getZeros(matrix[i], matrixLength) for i in range(matrixLength)])
print result
def getZeros(array, length):
return length - reduce(operator.add, array)
import java.util.Scanner;
public class ArraryMatrix {
static int count;
/**
* @param args
*/
public static int Mat(int arr[][],int size){
for(int i=0;i<size;i++){
for(int j=0;j<size;j++){
if(arr[i][j]==0){
count+=1;
}
}
}
return count;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc=new Scanner(System.in);
System.out.println("Enter the dimension of the Array:-");
int len=sc.nextInt();
int [][]A=new int[len][len];
for(int i=0;i<len;i++){
for(int j=0;j<len;j++){
System.out.println("Enter the element:["+i+"]"+"["+j+"]");
A[i][j]=sc.nextInt();
}
}
int score=Mat(A,len);
System.out.println("There are --"+score+"---No of zros are present in the given Matrics");
}
}
We can start off with the top row, counting from the right end until we hit a 0. Let's say we hit k1 number of 1's before hitting a 0. Total number of 1's in row1 = k1.
Now for the next row, we know that every column is also sorted, so no column from the end can have a 0 if it has a 1 in this row. So, we can safely skip k1 number of 1's and start from there until we hit a 0. Let the new number of 1's hit be k2. Total number of 1's in row1+row2 = sum so far + (previous k + new k) = (k1) + (k1+k2) = 2k1+k2
Continuing, we can go down, and we'll be amassing the number of 1's. Next row, we get total 1's = 3k1+2k2+k3, and so on. The total 1's in the end would be n*k1+(n-1)*k2+...+2*k{n-1}+kn.
Time wise, the total counting is k1+k2+...+kn = actually the whole length of one row = n, since if we completely cover a lot of elements in one row, the elements to cover for the next row become lesser and lesser, and the maximum we can cover is only n elements horizontally. Thus, time is O(n).
This can be optimized by binary search. Applying that on first row to find k1 yields us log(n) steps for row1, log(n-k1) steps for row2 and so on. Total = log(n)+log(n-k1)+log(n-k1-k2)+...+log(n-k1-k2...-kn).
public int numZeros(int[][] m)
{
if(m==null||m.length==0||m[0].length==0)
{
return 0;
}
int r=0;
int c=m[0].length-1;
int total=0;
while(r<m.length)
{
if(c<0)
{
r++;
c=m[0].length-1;
}else
{
if(m[r][c]==1)
{
c--;
}else{
if(c==m[0].length-1||m[r][c+1]==1)
{
total+=c+1;
r++;
}else{
c++;
}
}
}
}
return total;
}
//Worst case: O(N) where N is the number of rows.
public int numZeros(int[][] m)
{
if(m==null||m.length==0||m[0].length==0)
{
return 0;
}
int r=0;
int c=m[0].length-1;
int total=0;
while(r<m.length)
{
if(c<0)
{
r++;
c=m[0].length-1;
}else
{
if(m[r][c]==1)
{
c--;
}else{
if(c==m[0].length-1||m[r][c+1]==1)
{
total+=c+1;
r++;
}else{
c++;
}
}
}
}
return total;
}
Worst case: O(N) where N is the number of rows.
1. Divide the matrix into 4 quadrants.
2. Check the element at origin.
3. If it is 1, then we can eliminate the right bottom quadrant, as it will have only 1s.
4. If it is 0, then we can eliminate the left top quadrant, as it will have only 0s.
5. Now we are left with 3 quadrants each of size 1/4 of original matrix.
6. Repeat the process for these.
7. The base case can be a 2 x 2 matrix, or a single row of column.
This is f(n) = 1 + 3 * f(n/4), by Master's theorem, this is O(n ^ log(3 to base 4). Which is better than O(n).
int getZeroCountDivide(int x1, int y1, int x2, int y2, int (*arr)[MAX_SIZE])
{
if(arr[x1][y1] == 0 && arr[x2][y2] == 0) return (x2-x1+1) * (y2-y1+1);
if(arr[x1][y1] == 1 && arr[x2][y2] == 1) return 0;
int result = 0;
int row = x2-x1;
int column = y2-y1;
if(row == 0)
{
//just a few. count!
for(int i=y1;i<=y2;i++)
{
if(arr[x1][i] == 0) result ++;
}
return result;
}
if(column == 0)
{
//just a few. count!
for(int i=x1;i<=x2;i++)
{
if(arr[i][y2] == 0) result ++;
}
return result;
}
return getZeroCountDivide(x1, y1, x1 + (row / 2), y1 + (column / 2), arr)
+ getZeroCountDivide(x1 + (row / 2) + 1, y1 + (column / 2) + 1, x2, y2, arr)
+ getZeroCountDivide(x1, y1 + (column / 2) + 1, x1 + (row / 2), y2, arr)
+ getZeroCountDivide(x1 + (row / 2) + 1, y1, x2, y1 + (column / 2), arr);
}
O(logN?) ?
binary search from top-left to bottom-right to find 1, it will be located at X, where 0<=X<N. At this point you have X+X zeros, plus you need to recursively check right-top and top-bottom sections from X for extra zeros using similar technique. For right-top do binary search along top row to find 1, it will be located at Y, where X<=Y<N. So far with log n you will know how many 1s there in the right-top section: X*(N-Y). Then, recursively check rectangle bounded by X,0 and Y,X where left-bottom and right-top corners have zeros. Not sure though if the extra recursion increases log n complexity though.
Here is what I think, you can do it with recursion as below with O(logN):
1. First check position (0,0) == 1, if true, then quit with Number of Zeros = 0; else step 2.
2.
FindZeros(N,N){
if position (N,N) == 0, then quit with
Number of Zeros = N*N;
else,
if(N-1,N)==0 then
{
NumberOfZeros = N*(N-1) + Number of zeros from (N,0) to (N,N-1) ;
}
else if(N,N-1) == 0 then
{
NumberOfZeros = N*(N-1) + Number of zeros from (0,N) to (N-1,N) ;
}
else{
FindZeros(N-1,N-1);
}
}
You can do this with recursion with O(logN):
1. First check if (0,0) == 1, if true then exit with NumberOfZeros = 0 else step 2.
2.
FindNumberOfZeros(N)
{
if(N,N)==0, then
return Number of Zeros = N*N;
else if (N-1,N) == 0 then,
return Number of Zeros = N*(N-1) + Number of zeros from (N,0) to (N,N-1);
else if (N,N-1 )
return Number of Zeros = N*(N-1) + Number of zeros from (0,N) to (N-1,N);
else
return FindNumberOfZeros(N-1);
}
You can do this with recursion with O(logN):
1. First check if (0,0) == 1, if true then exit with NumberOfZeros = 0 else step 2.
2.
FindNumberOfZeros(N)
{
if(N,N)==0, then
return Number of Zeros = N*N;
else if (N-1,N) == 0 then,
return Number of Zeros = N*(N-1) + Number of zeros from (N,0) to (N,N-1);
else if (N,N-1 )
return Number of Zeros = N*(N-1) + Number of zeros from (0,N) to (N-1,N);
else
return FindNumberOfZeros(N-1);
}
You can do this with recursion with O(logN):
1. First check if (0,0) == 1, if true then exit with NumberOfZeros = 0 else step 2.
2.
FindNumberOfZeros(N)
{
if(N,N)==0, then
return Number of Zeros = N*N;
else if (N-1,N) == 0 then,
return Number of Zeros = N*(N-1) + Number of zeros from (N,0) to (N,N-1);
else if (N,N-1 )
return Number of Zeros = N*(N-1) + Number of zeros from (0,N) to (N-1,N);
else
return FindNumberOfZeros(N-1);
}
#include <iostream>
#include <vector>
using namespace std;
int main()
{
enum values{
zero =0,
one = 1,
};
vector<vector<values>> matrix = {{zero,zero,zero,one,one},{zero,zero,one,one,one},{zero,zero,one,one,one},{one,one,one,one,one}};
for (short int i = 0;i<matrix.size();i++){
cout<<"["<<i<<"]=> ";
for (short int j = 0;j<matrix[i].size();j++){
cout<<"["<<matrix[i][j]<<"]";
}
cout<<endl;
}
int posFirstOne = matrix[0].size();
int cont = 0;
for (short int i = 0;i<matrix.size();i++){
for (short int j = 0;j<posFirstOne;j++){
if (matrix[i][j]==one){
posFirstOne = j;
break;
}else{
cont+=1;
}
}
}
cout<<"Zeros:"<<cont<<endl;
return 0;
}
Here are 2 methods in Python:
matrix = [[0, 0, 0, 1 ], [0, 1, 1, 1], [0, 0, 0, 0], [0, 0, 1, 1]]
#method 1
print sum([len(eachArr)-sum(eachArr) for eachArr in matrix])
#method 2
from operator import add
length = len(matrix)
if matrix[length-1][length-1]==0:
print length**2
elif matrix[0][0]==1:
print 0
else:
total=0
for i in range(length-1,-1,-1):
if matrix[i][0]==0:
#total+=(length - sum(matrix[i]))
total+=(length - reduce(add, matrix[i]))
else:
pass
print total
implementation in Python
matrix = [[0, 0, 0, 1 ], [0, 1, 1, 1], [0, 0, 0, 0], [0, 0, 1, 1]]
#method 1
print sum([len(eachArr)-sum(eachArr) for eachArr in matrix])
#method 2
from operator import add
length = len(matrix)
if matrix[length-1][length-1]==0:
print length**2
elif matrix[0][0]==1:
print 0
else:
total=0
for i in range(length-1,-1,-1):
if matrix[i][0]==0:
#total+=(length - sum(matrix[i]))
total+=(length - reduce(add, matrix[i]))
else:
pass
print total
Go diagonally from bottom right until it hits '0' (i,j). This eliminates the (I,j) block and adds this dimension to count. Then, increment i for as long as it is '0', add this to count. Then, increment j for as long as it is '0', add this to count.
long MatrixPatternCount(vector<vector<long>>& data)
{
long i = data.size() - 1, j = data[0].size() -1;
long count = 0;
for (; i >= 0 && j >= 0; i--, j--)
if (!data[i][j]) {
count = (i + 1) * (j + 1);
break;
}
long ii = i, jj = j;
if (ii < data.size() - 1)
for (; j >= 0; j--)
for (i = ii + 1; !data[i][j]; i++)
count++;
i = ii;
if (jj < data[ii].size() - 1)
for (; i >= 0; i--)
for (j = jj + 1; !data[i][j]; j++)
count++;
return count;
}
@zd Your total complexity is O(nlogn), not O(logn). The complexity of the binary search doesn't change when the search space gets smaller since O(log(n/2)) = O(log(1/2 * n)) = O(log(1/2) + log(n)) = O(constant + log(n)) + O(log(n)). Also, you end up doing the binary search O(n) times, so your total complexity is O(nlogn)
void calculateElemNum(int **mat, int n, int m, int el)
{
printf("Number of '%ds' in matrix:\t", el);
int cnt = 0;
int start = n - 1;
for (int i = 0; i < m; i++) {
for (int j = start; j >= 0; j--) {
if (mat[i][j] == el) {
cnt += j + 1;
start = j;
if (j == 0)
goto END;
else
break;
}
}
}
END:
printf("%d\n", cnt);
}
I think I can solve this in O(logn*logn).
1. binary search on the diagonal finding the last cell containing 0. -->O(logn)
2. then we can divide the matrix into 4- one contain only 0, one contain only 1 and in the other 2 we need to count the zeroes. we can run the first step on the 2 matrix and sum all together. each time narrow the matrix size in at least 2.
The optimal solution is O(n).
This cannot be done in O(log n), and it's not difficult to prove this.
One proof is to note that the contour separating the 0 and 1 regions could have up to n segments. To determine the size of each area we need to know the location of the segments, which cannot be done in O(log n) since there are O(n) segments.
#include<stdio.h>
#include<conio.h>
void main()
{
int i, j, row, col = 0;
int arr[50][50];
clrscr();
printf("Enter no of rows:");
scanf("%d",&row);
printf("Enter no of columns:");
scanf("%d",&col);
for(i = 0; i < row; i++)
{
for(j = 0; j < col; j++)
{
printf("Enter value for row %d and column %d",i,j);
scanf("%d", &arr[i][j]);
}
}
for(i = 0; i < row; i++)
{
printf("\n");
for(j = 0; j < col; j++)
{
printf("%d ",arr[i][j]);
}
}
getch();
}
The best runtime complexity we can achieve is n*lg(n), the following code is written in java, using a binary search to find the biggest 0 index in a row.
public int findZeroCount(int[][] matrix) {
if (matrix == null || matrix.length < 1) {
return 0;
}
int sumZeros = 0;
int indexOfLastZero = matrix[0].length;
for (int i = 0; i < matrix.length; i++) {
indexOfLastZero = findIndexOfLastZero(matrix[i], 0, indexOfLastZero);
if (indexOfLastZero >= 0) {
sumZeros += (indexOfLastZero + 1);
}
}
return sumZeros;
}
private int findIndexOfLastZero(int[] array, int left, int right) {
int mid = 0;
while (right - left > 1) {
mid = (left + right) / 2;
if (array[mid] == 0) {
left = mid;
} else {
right = mid;
}
}
if (array[right] == 0) {
return right;
} else if (array[left] == 0) {
return left;
} else {
return -1;
}
}
@Test
public void testCountZeros() {
int[][] data = new int[][]{
{0, 0, 1},
{0, 1, 1},
{1, 1, 1}
};
int zeroCount = findZeroCount(data);
assertTrue(zeroCount == 3);
}
import java.util.*;
public class matrix {
public static void main(String args[]){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(); int count =0;
int [][] array = new int[n][n];
for(int i=0;i<n;i++){
for(int j=0;j<n;j++)
{
array[i][j] = sc.nextInt();
if (array[i][j] == 1)
break;
else count = count + 1;
}
sc.nextLine();
}
System.out.print(count);
}
}
import java.util.*;
public class matrix {
public static void main(String args[]){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(); int count =0;
int [][] array = new int[n][n];
for(int i=0;i<n;i++){
for(int j=0;j<n;j++)
{
array[i][j] = sc.nextInt();
if (array[i][j] == 1)
break;
else count = count + 1;
}
sc.nextLine();
}
System.out.print(count);
}
}
int countZero(vector<vector<int>> table){
//Find the most right 0 of the first row
int col = 0;
int res = 0;
while (col < table.size() && table[1][col] == 0) col++;
if (col == 0) return 0; res += col; col--;
for (int i = 1; i < table.size(); i++){
while(col > -1 && table[i][col] == 1) col--;
res += col + 1;
if (col == -1) return res;
}
}
This is my first version, and the complexity is O(n * log(n)):
// array contains n elements
int CountZeroCountInArray(const int *array, int n) {
// Range is [begin, end)
int begin = 0;
int end = n;
while (begin < end) {
int middle = (begin + end) / 2;
if (array[middle] != 0) {
end = middle;
} else {
begin = middle + 1;
}
}
// Should begin == end, and is the index of first non-zero element
return begin;
}
// matrix contains n * n elements
int CountZeroCountInMatrix(const int *matrix, int n) {
int zeroCount = 0;
int lineEnd = n;
for (const int *line = matrix; line < matrix + n * n; line += n) {
lineEnd = CountZeroCountInArray(line, lineEnd);
zeroCount += lineEnd;
}
return zeroCount;
}
This is my second version. It doesn't use a binary search, but the complexity is O(n). Interesting!
// matrix contains n * n elements
int CountZeroCountInMatrix(const int *matrix, int n) {
int zeroCount = 0;
int lineEnd = n;
for (const int *line = matrix; line < matrix + n * n; line += n) {
while (line[lineEnd - 1] != 0) {
lineEnd--;
if (lineEnd == 0) {
return zeroCount;
}
}
zeroCount += lineEnd;
}
return zeroCount;
}
Here is my test code:
int main() {
const int matrix1[] = {
0, 0, 1,
0, 1, 1,
1, 1, 1
};
// 3
std::cout << CountZeroCountInMatrix(matrix1, 3) << std::endl;
const int matrix2[] = {
0, 0,
0, 0
};
// 4
std::cout << CountZeroCountInMatrix(matrix2, 2) << std::endl;
const int matrix3[] = {
0, 0, 0,
0, 1, 1,
0, 1, 1
};
// 5
std::cout << CountZeroCountInMatrix(matrix3, 3) << std::endl;
return 0;
}
Your solution is correct with tiny correction.
" Everything on the upper left of the middle 1 : not exactly." not exactly.
O(N,N) = 3* O(N/2,N/2);
O(N^2) = 3 *O(N/4) + 1;
O(2logN/log(4/3)) --> O(logN).
int count(const vec2dint &A, int x, int y, int x1, int y1)
{
if (x > x1 || y > y1) return 0;
if (A[x][y] == 1) return 0;
if (A[x1][y1] == 0) return (x1-x+1) * (y1-y+1);
int xm = (x + x1)/2;
int ym = (y + y1)/2;
int t = count (A, x,y,xm,ym) + count (A, xm+1,ym+1, x1, y1) + count(A, x, ym+1, xm, y1) + count(A, xm+1, y, x1, ym);
int nc = 0;
for (int i = x; i <= x1; ++i)
for (int j = y; j <= y1; ++j)
if (A[i][j] == 0) nc ++;
if (nc != t)
{
std::cout << "error " << nc << " " << t << "\n";
exit(1);
}
}
Another Solution that depends on bit manipulation could be as follows:
i)Invert bits in every single row -> O(n) with the assumption that the bit mask operation takes constant time with fast processor.
ii)Return the least significant one in every row -> Should be another O(n)
iii) Number of zeros in every row = N - output of step # ii -> O(n)
iv) Add numbers
iv)
Here is an approach walking along the diagonal. General approach:
1. Start in the bottom left corner.
2. Subtract row index until you find a 0.
3. Add the row index + 1 to you total and move one column right.
4. Repeat from step 2 until you find the top or right edge of the matrix.
This is worst case O(N) since the length of the diagonal is proportional to N.
Code:
- Johnie June 26, 2016