content: package by.andd3dfx.search;
  
  /**
   * <pre>
   * <a href="https://leetcode.com/problems/count-negative-numbers-in-a-sorted-matrix/description/">Task description</a>
   *
   * Given a 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.
   *
   * Example 1:
   * Input: grid = [
   *      [4,3,2,-1],
   *      [3,2,1,-1],
   *      [1,1,-1,-2],
   *      [-1,-1,-2,-3]
   *  ]
   * Output: 8
   * Explanation: There are 8 negatives number in the matrix.
   *
   * Example 2:
   * Input: grid = [[3,2],[1,0]]
   * Output: 0
   *
   * Follow up: Could you find an O(n + m) solution?
   * </pre>
   *
   * @see <a href="https://youtu.be/N3RrlPQn9CY">Video solution</a>
   */
  public class CountNegativesInSortedMatrix {
  
      public static int count_MN(int[][] grid) {
          var m = grid.length;
          if (m == 0) {
              return 0;
          }
          var n = grid[0].length;
          var result = 0;
  
          for (int[] gridItem : grid) {
              for (int j = 0; j < n; j++) {
                  if (gridItem[j] < 0) {
                      result += n - j;    // add count of numbers from current to the end of row (because of sorted row)
                      break;
                  }
              }
          }
          return result;
      }
  
      public static int count_NPlusM(int[][] grid) {
          var m = grid.length;
          if (m == 0) {
              return 0;
          }
          var n = grid[0].length;
          var result = 0;
  
          // start position in the left bottom grid corner
          var i = m - 1;
          var j = 0;
  
          while (i >= 0 && j < n) {
              if (grid[i][j] < 0) {
                  i--;                // switch to the upper row
                  result += n - j;    // add count of numbers from current to the end of row (because of sorted row)
              } else {
                  j++;                // switch to the right column
              }
          }
          return result;
      }
  }
  