Skip to content

Instantly share code, notes, and snippets.

@djassie
Created March 30, 2024 00:33
Show Gist options
  • Save djassie/cdb291fda1210e0c56f87b711f381bcc to your computer and use it in GitHub Desktop.
Save djassie/cdb291fda1210e0c56f87b711f381bcc to your computer and use it in GitHub Desktop.
Binary Search : number of negatives in sorted matrix in C
int rowNegatives(int *arr, int size){
int li = 0, ri = size - 1, negative=0;
//corner cases
if(*(arr+size-1) >=0){return 0;}
if(*arr<0){return size;}
while(li<=ri){
int mid = li + (ri - li)/2;
if(*(arr+mid)<0 && *(arr+mid-1)>=0){
return size - mid;
}else if(*(arr+mid)<0){
ri = mid - 1;
}else{
li = mid + 1;
}
}
return 0;
}
int countNegatives(int **grid, int gridSize, int *gridColSize) {
int negatives = 0;
for(int i=0; i<gridSize; i++){
negatives += rowNegatives(grid[i], *gridColSize);
}
return negatives;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment