comments | difficulty | edit_url | rating | source | tags | |||
---|---|---|---|---|---|---|---|---|
true |
Easy |
1139 |
Weekly Contest 176 Q1 |
|
Given a m x n
matrix grid
which is sorted in non-increasing order both row-wise and column-wise, return the number of negative numbers in grid
.
Example 1:
Input: grid = [[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]] Output: 8 Explanation: There are 8 negatives number in the matrix.
Example 2:
Input: grid = [[3,2],[1,0]] Output: 0
Constraints:
m == grid.length
n == grid[i].length
1 <= m, n <= 100
-100 <= grid[i][j] <= 100
Follow up: Could you find an
O(n + m)
solution?
According to the characteristic that both rows and columns are arranged in non-increasing order, we can start traversing from the bottom left corner towards the top right direction.
When encountering a negative number, it indicates that all elements to the right of the current position in this row are negative. We add the number of remaining elements in this row to the answer, that is,
After the traversal is over, return the answer.
The time complexity is
class Solution:
def countNegatives(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
i, j = m - 1, 0
ans = 0
while i >= 0 and j < n:
if grid[i][j] < 0:
ans += n - j
i -= 1
else:
j += 1
return ans
class Solution {
public int countNegatives(int[][] grid) {
int m = grid.length, n = grid[0].length;
int ans = 0;
for (int i = m - 1, j = 0; i >= 0 && j < n;) {
if (grid[i][j] < 0) {
ans += n - j;
--i;
} else {
++j;
}
}
return ans;
}
}
class Solution {
public:
int countNegatives(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
int ans = 0;
for (int i = m - 1, j = 0; i >= 0 && j < n;) {
if (grid[i][j] < 0) {
ans += n - j;
--i;
} else
++j;
}
return ans;
}
};
func countNegatives(grid [][]int) int {
m, n := len(grid), len(grid[0])
ans := 0
for i, j := m-1, 0; i >= 0 && j < n; {
if grid[i][j] < 0 {
ans += n - j
i--
} else {
j++
}
}
return ans
}
function countNegatives(grid: number[][]): number {
const m = grid.length,
n = grid[0].length;
let ans = 0;
for (let i = m - 1, j = 0; i >= 0 && j < n; ) {
if (grid[i][j] < 0) {
ans += n - j;
--i;
} else {
++j;
}
}
return ans;
}
impl Solution {
pub fn count_negatives(grid: Vec<Vec<i32>>) -> i32 {
let n = grid[0].len();
grid.into_iter()
.map(|nums| {
let mut left = 0;
let mut right = n;
while left < right {
let mid = left + (right - left) / 2;
if nums[mid] >= 0 {
left = mid + 1;
} else {
right = mid;
}
}
(n - left) as i32
})
.sum()
}
}
/**
* @param {number[][]} grid
* @return {number}
*/
var countNegatives = function (grid) {
const m = grid.length,
n = grid[0].length;
let ans = 0;
for (let i = m - 1, j = 0; i >= 0 && j < n; ) {
if (grid[i][j] < 0) {
ans += n - j;
--i;
} else {
++j;
}
}
return ans;
};
Traverse each row, use binary search to find the first position less than
After the traversal is over, return the answer.
The time complexity is
class Solution:
def countNegatives(self, grid: List[List[int]]) -> int:
return sum(bisect_left(row[::-1], 0) for row in grid)
class Solution {
public int countNegatives(int[][] grid) {
int ans = 0;
int n = grid[0].length;
for (int[] row : grid) {
int left = 0, right = n;
while (left < right) {
int mid = (left + right) >> 1;
if (row[mid] < 0) {
right = mid;
} else {
left = mid + 1;
}
}
ans += n - left;
}
return ans;
}
}
class Solution {
public:
int countNegatives(vector<vector<int>>& grid) {
int ans = 0;
for (auto& row : grid) {
ans += lower_bound(row.rbegin(), row.rend(), 0) - row.rbegin();
}
return ans;
}
};
func countNegatives(grid [][]int) int {
ans, n := 0, len(grid[0])
for _, row := range grid {
left, right := 0, n
for left < right {
mid := (left + right) >> 1
if row[mid] < 0 {
right = mid
} else {
left = mid + 1
}
}
ans += n - left
}
return ans
}
function countNegatives(grid: number[][]): number {
const n = grid[0].length;
let ans = 0;
for (let row of grid) {
let left = 0,
right = n;
while (left < right) {
const mid = (left + right) >> 1;
if (row[mid] < 0) {
right = mid;
} else {
left = mid + 1;
}
}
ans += n - left;
}
return ans;
}
impl Solution {
pub fn count_negatives(grid: Vec<Vec<i32>>) -> i32 {
let m = grid.len();
let n = grid[0].len();
let mut i = m;
let mut j = 0;
let mut res = 0;
while i > 0 && j < n {
if grid[i - 1][j] >= 0 {
j += 1;
} else {
res += n - j;
i -= 1;
}
}
res as i32
}
}
/**
* @param {number[][]} grid
* @return {number}
*/
var countNegatives = function (grid) {
const n = grid[0].length;
let ans = 0;
for (let row of grid) {
let left = 0,
right = n;
while (left < right) {
const mid = (left + right) >> 1;
if (row[mid] < 0) {
right = mid;
} else {
left = mid + 1;
}
}
ans += n - left;
}
return ans;
};