Count Negative Numbers in a Sorted Matrix
Easy
Watch on YouTube ↗Solution
class Solution {
public int countNegatives(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
int count = 0;
// O(m)*O(logn)
for(int nums[] : grid) {
if(nums[n-1] >=0 ) {
continue;
}
else {
int index = getIndex(nums);
count += n-index;
}
}
return count;
}
int getIndex(int nums[]) {
int low=0, high = nums.length-1;
while(low < high) {
int mid = low + (high-low)/2;
if(nums[mid] < 0) {
high = mid;
} else low = mid+1;
}
return low;
}
}
/*
[4,3,2,-1]
[3,2,1,-1]
[1,1,-1,-2]
[-1,-1,-2,-3]
*/