_1351. Count Negative Numbers in a Sorted Matrix.md

1351. Count Negative Numbers in a Sorted Matrix

All prompts are owned by LeetCode. To view the prompt, click the title link above.

Back to top

---

First completed : June 01, 2024

Last updated : July 01, 2024

---

Related Topics : Array, Binary Search, Matrix

Acceptance Rate : 77.54 %

---

Solutions

• e1351 v1 inefficient.java
• e1351 v2 optimized.java
• e1351.py

Java

e1351 v1 inefficient.java

class Solution {
    public int countNegatives(int[][] grid) {
        int counter = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = grid[i].length - 1; j >= 0; j--) {
                if (grid[i][j] >= 0) {
                    break;
                }
                counter++;
            }
        }
        return counter;
    }
}

e1351 v2 optimized.java

// v1 is inefficient since I didn't see that it was sorted both vertically
// and horizontally and that it was a static mxn matrix so I wouldn't
// have to worry about bounds.

class Solution {
    public int countNegatives(int[][] grid) {
        int counter = 0;
        int row = 0;
        int col = grid[0].length - 1;

        while (row < grid.length && col >= 0) {
            if (grid[row][col] < 0) {
                col--;
                counter += grid.length - row;
                continue;
            }
            row++;
        }

        return counter;
    }
}

Python

e1351.py

# This is the efficient version

class Solution:
    def countNegatives(self, grid: List[List[int]]) -> int:
        counter = 0
        row, col = 0, len(grid[0]) - 1

        while row < len(grid) and col >= 0 :
            if grid[row][col] < 0 :
                col -= 1
                counter += len(grid) - row
                continue
            row += 1
        
        return counter