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

Question

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

• David Harkness: 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.
• JS1: sum[i]==count;? This is not a working program, and that isn't the only mistake.
• Winston Ewert: I think you are missing a word in the third sentence of the problem description.

Answer 1

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

• Jason Blake: But this raises the complexity to O(n^2) in the worst case and wont be valid answer to the problem right?
• Jason Blake: I will think along your lines and come up with a suggestion maybe :)
• Hellion: 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: In fact I believe it'll take n operations in the best case, and 2n operations in the worst case.
• Jason Blake: 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 -

Answer 2

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.

• Erick Wong: This is in fact not best possible. Binary search is actually wasteful here because it spends time on each row seeking to the left when the actual sequence of indices is increasing.