Return to Revisions

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.