Blogs Hub

Count Negative Numbers in a Sorted Matrix - Array - Easy - LeetCode - MiniTV

Count Negative Numbers in a Sorted Matrix - Array - Easy - LeetCode - मिनी टीवी

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;
        }
    }
}