LeetCode Entry

1351. Count Negative Numbers in a Sorted Matrix

28.12.2025 easy 2025 kotlin rust

Count negatives in 2D sorted matrix

1351. Count Negative Numbers in a Sorted Matrix easy blog post substack youtube

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/1218

Problem TLDR

Count negatives in 2D sorted matrix #easy

Intuition

Brute force. Improve with either:

• binary search
• n+m walk on border of negatives

Approach

• use list.binarySearch {..} in Kotlin or partition_point in Rust

Complexity

• Time complexity: \(O(nlogm)\)

• Space complexity: \(O(nm)\)

Code

// 15ms
    fun countNegatives(g: Array<IntArray>) =
        g.sumOf { g[0].size+1+it.asList().binarySearch { if (it < 0) 1 else -1 } }

// 0ms
    pub fn count_negatives(g: Vec<Vec<i32>>) -> i32 {
        g.iter().map(|r| { (r.len() - r.partition_point(|&x| x >= 0)) as i32 }).sum()
    }