leetcode

commit 889cdb1bd06de38f9bf8fe0c24154665b044ba69
parent 2d4d6db5843b264b91ceec6dbb179e6050fd1e74
Author: Jack Sangdahl <jack@pngu.org>
Date:   Sat, 27 Dec 2025 19:37:31 -0700

1351. count negative numbers in a sorted maxtrix

Diffstat:
M
count_negative_num_matrix.c
 | 
59
+++++++++++++++++++++--------------------------------------
A
count_negative_num_matrix.py
 | 
33
+++++++++++++++++++++++++++++++++

2 files changed, 54 insertions(+), 38 deletions(-)
diff --git a/count_negative_num_matrix.c b/count_negative_num_matrix.c
@@ -1,49 +1,32 @@
 // 1351. Count Negative Numbers in a Sorted Matrix
-#include <stdio.h>
+#include "leetcode.h"
 
 // given an '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'
 
-void search(int **grid, int grid_size, int row, int start, int end, int *ans) {
-  while (start < end) {
-    int mid = start + (end - start) / 2;
-    if (grid[row][mid] >= 0) {
-      start = mid + 1;
-      if (grid[row][start] < 0) {
-        (*ans) += grid_size - start;
-        return;
-      }
-    } else {
-      end = mid;
-    }
+int countNegatives(int **grid, int gridSize, int *gridColSize) {
+  int r = gridSize - 1, c = 0, cnt = 0, n = gridColSize[0];
+  while (r >= 0 && c < n) {
+    if (grid[r][c] < 0)
+      --r, cnt += n - c;
+    else
+      ++c;
   }
-}
-
-int countNegatives(int **grid, int grid_size, int *grid_col_size) {
-  if (grid_size == 1 && grid_col_size[0] == 1)
-    return grid[0][0] < 0 ? 1 : 0;
-  int r_size = grid_size, c_size = grid_col_size[0], r_idx = 0, ans = 0;
-  for (int r = r_size - 1; r >= 0; r--) {
-    if (grid[r][0] >= 0) {
-      r_idx = r;
-      ans = (r_size - r_idx - 1) * c_size;
-      break;
-    }
-  }
-  for (int r = 0; r <= r_idx; r++) {
-    if (grid[r][c_size - 1] >= 0)
-      continue;
-    search(grid, c_size, r, 0, c_size - 1, &ans);
-  }
-  return ans;
+  return cnt;
 }
 
 int main() {
-  int g1[4][4] = {
+  int g1i[4][4] = {
       {4, 3, 2, -1}, {3, 2, 1, -1}, {1, 1, -1, -2}, {-1, -1, -2, -3}};
-  int g2[2][2] = {{3, 2}, {1, 0}};
-  int gs1 = 4, gs2 = 2;
-  int *gcs1, *gcs2;
-  printf("%d\n", countNegatives(g1, gs1, gcs1)); // expect: 8
-  printf("%d\n", countNegatives(g2, gs2, gcs2)); // expect: 0
+  int g2i[2][2] = {{3, 2}, {1, 0}};
+  struct two_d_arr *g1 =
+      two_d_arr_init(ARRAY_SIZE(g1i), ARRAY_SIZE(g1i[0]), g1i);
+  struct two_d_arr *g2 =
+      two_d_arr_init(ARRAY_SIZE(g2i), ARRAY_SIZE(g2i[0]), g2i);
+  printf("%d\n",
+         countNegatives(g1->arr, g1->row_size, g1->col_size)); // expect: 8
+  printf("%d\n",
+         countNegatives(g2->arr, g2->row_size, g2->col_size)); // expect: 0
+  two_d_arr_free(g1);
+  two_d_arr_free(g2);
 }
diff --git a/count_negative_num_matrix.py b/count_negative_num_matrix.py
@@ -0,0 +1,33 @@
+# 1351. Count Negative Numbers in a Sorted Matrix
+
+"""
+given an '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'
+"""
+
+
+class Solution(object):
+    def countNegatives(self, grid):
+        """
+        :type grid: List[List[int]]
+        :rtype: int
+        """
+        m, n = len(grid), len(grid[0])
+        r, c, cnt = n - 1, 0, 0
+        while r >= 0 and c < m:
+            if grid[r][c] < 0:
+                cnt += m - c
+                r -= 1
+            else:
+                c += 1
+        return cnt
+
+
+if __name__ == "__main__":
+    obj = Solution()
+    print(
+        obj.countNegatives(
+            grid=[[4, 3, 2, -1], [3, 2, 1, -1], [1, 1, -1, -2], [-1, -1, -2, -3]]
+        )
+    )
+    print(obj.countNegatives(grid=[[3, 2], [1, 0]]))