LeetCode Entry
1351. Count Negative Numbers in a Sorted Matrix
Count negatives in a sorted by row and by column matrix.
1351. Count Negative Numbers in a Sorted Matrix easy blog post substack
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/239
Problem TLDR
Count negatives in a sorted by row and by column matrix.
Intuition
Consider example:
4 3 2 -1
3 2 1 -1
1 1 -1 -2
^ we are here
-1 -1 -2 -3
If we set position x at the first negative number, it is guaranteed, that the next row[x] will also be negative. So we can skip already passed columns.
Approach
Let’s use Kotlin’s fold operator.
Complexity
- Time complexity: \(O(n + m)\)
- Space complexity: \(O(1)\)
Code
fun countNegatives(grid: Array<IntArray>): Int =
grid.fold(0 to 0) { (total, prev), row ->
var curr = prev
while (curr < row.size && row[row.lastIndex - curr] < 0) curr++
(total + curr) to curr
}.first
}