Given a m * 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
Example 3:
Input: grid = [[1,-1],[-1,-1]]
Output: 3
Example 4:
Input: grid = [[-1]]
Output: 1
Constraints:
m == grid.length
n == grid[i].length
1 <= m, n <= 100
-100 <= grid[i][j] <= 100
Solution:
using System;
using System.Collections.Generic;
using System.Text;
namespace LeetCode.AskGif.Easy.Array
{
public class CountNegativesSoln
{
public int CountNegatives(int[][] grid)
{
int count = 0;
for (int i = 0; i < grid.Length; i++)
{
for (int j = 0; j < grid[i].Length; j++)
{
if (grid[i][j] < 0)
{
count += grid[i].Length - j;
break;
}
}
}
return count;
}
}
}
Time Complexity: O(n^2)
Space Complexity: O(1)
Unit Tests:
using LeetCode.AskGif.Easy.Array;
using Microsoft.VisualStudio.TestTools.UnitTesting;
using System;
using System.Collections.Generic;
using System.Text;
namespace CodingUnitTest.Easy.Array
{
[TestClass]
public class CountNegativesSolnTests
{
[TestMethod]
public void CountNegativesSoln_First()
{
var grid = new int[,]{
{ 4, 3, 2, -1 },
{ 3, 2, 1, -1 },
{ 1, 1, -1, -2 },
{ -1, -1, -2, -3 }
};
var output = 8;
var res = new CountNegativesSoln().CountNegatives(ArrayMapper(grid));
Assert.AreEqual(res, output);
}
[TestMethod]
public void CountNegativesSoln_Second()
{
var grid = new int[,]{
{ 3, 2 },
{ 1, 0 }
};
var output = 0;
var res = new CountNegativesSoln().CountNegatives(ArrayMapper(grid));
Assert.AreEqual(res, output);
}
[TestMethod]
public void CountNegativesSoln_Third()
{
var grid = new int[,]{
{ 1, -1 },
{ -1, -1 }
};
var output = 3;
var res = new CountNegativesSoln().CountNegatives(ArrayMapper(grid));
Assert.AreEqual(res, output);
}
[TestMethod]
public void CountNegativesSoln_Fourth()
{
var grid = new int[,]{
{ -1 }
};
var output = 1;
var res = new CountNegativesSoln().CountNegatives(ArrayMapper(grid));
Assert.AreEqual(res, output);
}
private int[][] ArrayMapper(int[,] matrix)
{
var arr = new int[matrix.GetLength(0)][];
for (int i = 0; i < matrix.GetLength(0); i++)
{
arr[i] = new int[matrix.GetLength(1)];
for (int j = 0; j < matrix.GetLength(1); j++)
{
arr[i][j] = matrix[i, j];
}
}
return arr;
}
}
}
