aboutsummaryrefslogtreecommitdiff
path: root/count_negative_num_matrix.c
blob: e91de57dae08989481e19b32abba4f38a4dba5b1 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
// 1351. Count Negative Numbers in a Sorted Matrix
#include <stdio.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 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;
}

int main() {
  int g1[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
}