## Google Interview Question for Software Developers

Country: United States
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
8
of 8 vote

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:

``````private int countNumZeroes(int[][] matrix) {
int row = matrix.length - 1, col = 0, numZeroes = 0;
while (col < matrix[0].length) {
while (matrix[row][col] != 0) {
if (--row < 0) {
return numZeroes;
}
}
// Add one since matrix index is 0 based
numZeroes += row + 1;
col++;
}
return numZeroes;
}``````

Comment hidden because of low score. Click to expand.
4
of 8 vote

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).

Comment hidden because of low score. Click to expand.
0

What if you have something like this

[1, 1, 1, 1],
[1, 1, 1, 1],
[1, 1, 1, 1],
[1, 1, 1, 1]

Would the above work

Comment hidden because of low score. Click to expand.
0
of 0 vote

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``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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));
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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):

Comment hidden because of low score. Click to expand.
0
of 0 vote

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):

Comment hidden because of low score. Click to expand.
0
of 0 vote

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):

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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");

}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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).

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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++;
}
}
}
}
}

//Worst case: O(N) where N is the number of rows.``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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++;
}
}
}
}
}

Worst case: O(N) where N is the number of rows.``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Any tips for the O(log N) solution? I'm having a hard time visualizing how to find information that to me seems linear in the worst case in logarithmic time without relying on some assumption of fast matrix operations or other things.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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).

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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?) ?

Comment hidden because of low score. Click to expand.
0
of 0 vote

Since N is the length of each side, would your reduction not be

f(n) = 1 + 3 * f(n/2) ?

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Johnie,

You're right, the n in my solution should be number of elements in the matrix and not the number of rows/columns.
And number of elements is in the order of N^2. So we're back to square one.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

test

Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

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]))
else:
pass

print total``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

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]))
else:
pass

print total``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

@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)

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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);
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

log(N):
1) Binary search along the diagonal to find "change" point : log(N)
2) Binary search along the row found in (1) to find "change" point in that row: log(N)
3) Binary search along the column found in (1) to find "change" point in that column: log(N)

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````private static int count(int[][] m) {
int res = 0;
int w = m[0].length, h = m.length;
int i = h - 1, j = 0, count = 0;
while(i >= 0 && j < w) {
if(m[i][j] == 0 && j == w - 1) {
res += w;
i--;
continue;
}
if(m[i][j] == 1) {
res += j;
i--;
}else {
j++;
}
}
return res;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#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();
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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);``````

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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);

}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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);

}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

C- Implementation

``````int main()
{
int matrix[4][4]={ {0, 0, 0, 0},
{0, 0, 0, 0},
{0, 1, 1, 1},
{0, 1, 1, 1},
};
int row = 3 ;
int col = 0;
int zero = 0;

while( col < 4 )
{
if( matrix[col][row] == 0 )
{
zero += ( row + 1 );
col++;
}
else
{
row--;
}
}

printf("Zero:%d\n", zero);

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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;
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public static int count0s(int[][] mat){
int i=0;
int j=mat.length-1;
int count = 0;
while(i < mat.length && j > -1){
if(mat[i][j] == 0){
count = count + j + 1;
i++;
}else{
j--;
}
}
return count;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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)

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.