# Devise an algorithm of complexity O(N) finding No of 1's from a 2 dimensional matrix[N][N] containing 1's and 0's

Assume a 2D [n][n] matrix of 1's and 0's. All the 1's in any row should come before 0's. The number of 1's in any row I should be at least the number of 1's row (i+1). Find a method and write a C program to count the number of 1's in a 2D matrix. The complexity of the algorithm should be order n.

The question is from Cormen's Algorithm Book. Kindly point out the mistakes in my algorithm and hopefully suggest a better way.

 #include<stdio.h>
#include<stdlib.h>

int **map;
int getMatrix();

main()
{
int n,i,j,t;
j=0;
n=getMatrix();
i=n-1;
int sum[n];
for(t=0;t<n;t++)
sum[t]=0;
int count=0;
while ( (i>=0) && (j<n) )
{
if ( map[i][j] == 1 )
{
j++;
count=count+1;
}
else
{
if (i==(n-1))
{
sum[i]==count;
count=0;
}
else
{
sum[i]=sum[i+1]+count;
count=0;
i--;
}
}
}
for (t=0;t<n;t++)
{
if ((t==(n-1)) && (sum[t]==0))
sum[t]=0;
else if ((sum[t]==0) && (sum[t+1]>0))
sum[t]=sum[t+1];
}
int s=0;
for (t=0;t<n;t++)
s=s+sum[t];
printf("\nThe No of 1's in the given matrix is %d \n" ,s);
}

int getMatrix()
{
FILE *input=fopen("matrix.txt","r");
char c;
int nVer=0,i,j;
while((c=getc(input))!='\n')
if(c>='0' && c<='9')
nVer++;
map=malloc(nVer*sizeof(int*));
rewind(input);
for(i=0;i<nVer;i++)
{
map[i]=malloc(nVer*sizeof(int));
for(j=0;j<nVer;j++)
{
do
{
c=getc(input);
}while(!(c>='0' && c<='9'));
map[i][j]=c-'0';
}
}
fclose(input);
return nVer;
}

-
Please format your code nicely to make it easier for everyone else to read. You only need to format it once, but you'll save a lot of people time and increase your chances of getting feedback. Also, you typically post here when the code is already working to get a review. SO is where you take it when it doesn't work yet. –  David Harkness Aug 26 '12 at 8:47
sum[i]==count;? This is not a working program, and that isn't the only mistake. –  JS1 Jan 26 at 1:18
I think you are missing a word in the third sentence of the problem description. –  Winston Ewert Jan 26 at 1:46

## 2 Answers

I think your main loop should be something more along the lines of

row = n-1;      // start at bottom row
for (col=0; col<n; col++) {   // read columns from left to right
while ((row >= 0) && (map[row,col] == 0)) {   // while not out of rows, and on a 0
sum += col;  //add count of 1s to total
row--;       //move to next row up
}
// do nothing if we're on a 1, just move to next column.
}
if (row >= 0) sum += (row+1)*col; // add in any leftover rows of all 1s
printf("sum is %d\n",sum);

-
But this raises the complexity to O(n^2) in the worst case and wont be valid answer to the problem right? –  Jason Blake Aug 25 '12 at 3:27
I will think along your lines and come up with a suggestion maybe :) –  Jason Blake Aug 25 '12 at 3:28
No, it's O(n); it's got a single loop, col = 0 to n-1. (while the column value goes from 0 to n, the row value goes from n-1 to 0 at the same time; it's not a nested loop but a linked value.) –  Hellion Aug 25 '12 at 4:04
In fact I believe it'll take n operations in the best case, and 2n operations in the worst case. –  Hellion Aug 25 '12 at 4:07
But The code gives the wrong result, so maybe the algorithm needs some tuning - I implemented for this matrix 1111 1111 1100 1000 here is the code I used - –  Jason Blake Aug 25 '12 at 9:41

Sorry, but your solution is still O(N^2). Say the number of 1s is its minimum. Consider the minimum number of 1s, i.e. each row i has i+1 ones. You will have to scan N-i positions in each row, for a total of N^2/2 actions, i.e. O(N^2). visually:

1* 0* 0* 0* 0*
1  1* 0* 0* 0*
1  1  1* 0* 0*
1  1  1  1* 0*
1  1  1  1  1*


Where the *s indicate you looked at that position. With smart enough code, you could actually infer the 1s, but that's still O(N^2) and probably more overhead than it's worth.

A faster solution is to find the border between 0 and 1 by binary search.

int findFirstZero(int *row, int left, int right)
{
if(row[right]) return right;
int lastOne = left;
int firstZero = right;
int pos;
while(firstZero - lastOne > 1) {
pos = (lastOne + firstZero) / 2;
if(pos) {
lastOne = pos;
} else {
firstZero = pos;
}
}
return firstZero;
}

int sumOnes(int **map) {
int sum = 0;
for(int i = 0; i < N; i++) {
sum += findFirstZero(map[i], i, N-i-1);
}
return sum;
}


Now, this is actually O(NlogN), but given the constraints of the problem as I understand them, I'm quite certain that's the best possible; either you or Cormen left something out of the problem or Cormen made a mistake in his big-O analysis. I'd love to see a proof to the contrary, though.

-