# 08.06.2023 [1351. Count Negative Numbers in a Sorted Matrix]

08.06.2023

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
}