Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
3.
Sample Examples
3.1.
Example 1
3.2.
Example 2
4.
Brute Force Approach
4.1.
Algorithm
4.2.
Dry Run
4.3.
Implementation in Python
4.4.
Implementation in C++
4.5.
Complexity Analysis
4.5.1.
Time Complexity
4.5.2.
Space Complexity
5.
Binary Search Approach
5.1.
Algorithm
5.2.
Dry Run
5.3.
Implementation in Python
5.4.
Implementation in C++
5.5.
Complexity Analysis
5.5.1.
Time Complexity
5.5.2.
Space Complexity
6.
Optimized Traversal Approach
6.1.
Algorithm
6.2.
Dry Run
6.3.
Implementation in Python
6.4.
Implementation in C++
6.5.
Complexity Analysis
6.5.1.
Time Complexity
6.5.2.
Space Complexity
7.
Frequently Asked Questions
7.1.
What are the different approaches to this problem, and which one is optimized?
7.2.
When traversing through the grid, what is the time and space complexity?
7.3.
What are the different types of traversals possible in a grid?
7.4.
What is a two-pointer approach, and how is it working on the above question?
7.5.
How to decompose a 2-D array into a 1-D array?
8.
Conclusion
Last Updated: Mar 27, 2024
Easy

Count Negative Numbers in a Sorted Matrix

Create a resume that lands you SDE interviews at MAANG
Speaker
Anubhav Sinha
SDE-2 @
12 Jun, 2024 @ 01:30 PM

Introduction

Hey Ninjas!! Today we’ll look at a fundamental topic in our DSA curriculum and solve a question. So today’s question is to count the number of negative integers in a sorted grid. We hope you will solve this with us, won’t you? Why the wait? Let’s get going.

og image

Are you ready with your approach? Today we will look into various approaches to solving this question, and then you will decide which one you prefer.

Check out this array problem - Merge 2 Sorted Arrays

Problem Statement

More formally, the problem statement is “You are given a matrix of dimensions M*N, which is sorted in decreasing order both row-wise and column-wise. Find the number of negative integers in a sorted grid.”

Let us look at some sample examples to understand better.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Sample Examples

Here are some examples of the above question.

Example 1

Input:

grid = [ [1,-1] , [-1,-1] ]


Output:

3


Explanation:

As you can see, in the grid above, the total number of negative integers is 3, so we return 3 as the answer.

Example 2

Input:

grid = [ [44,40,13,1],[36,20,10,-1],[7,5,3,-19],[-2,-30,-60,-80] ]


Output:

6


Explanation:

As seen in the grid above, we can count the number of negative integers in the grid. It comes out to be 6, so we return 6.

Brute Force Approach

This is a naive, brute-force approach, where we will traverse every array element and check if it's negative or positive. If a negative number is found, we increment the counter by 1, and on reaching the end of the matrix, we will return the counter as the answer.

Algorithm

Let’s discuss the above algorithm step by step to get a better picture of the approach.

Step 1: First, decompose the 2-D matrix into a 1-D list/array of integers. 

Step 2: To convert a 2-D matrix into a 1-D array, take an empty list, and traverse through the matrix. On traversing, append every element of the matrix to the list. 

Step 3: On reaching the matrix's end, a 1-D array of integers (from the matrix) is obtained.

Step 4: Now, iterate over the elements of the 1-D display and keep a count of negative integers in this 1-D array.

Step 5: Return the count of negative integers as the answer.

Dry Run

Let’s go through the above example with the help of an example.

Example

Input:

grid = [ [1,-1], [-1, -1] ]


Step 1: Decomposition of the 2-D matrix

We have the grid of 2*2 dimensions, where m=2 and n=2. Now we have to convert the following 2-D matrix into a single array.

Let us initialize an empty list ans = [ ] 

Iterate over the elements of the grid, and append the values to a list ans

Step 2: After traversing the entire matrix, we get 

ans = [ 1,-1,-1,-1 ].
step 2

Step 3: Now perform simple linear traversal over ans, and keep a count of negative integers.

Step 4: Return the final answer as the count of negative integers, which turns out to be 3.

Implementation in Python

# Function to count negatives in sorted matrix
def count_negatives(grid: list[list[int]]) -> int:
    
    # Decomposing a 2-d array to 1-d array
    converted_array = []

    for row in grid:
        converted_array.extend(row)

    # Counting the negatives in 1-d array
    ans = 0
    for ele in converted_array:
        if ele < 0:
            ans += 1
    return ans

# Driver code
grid = [[1,-1],[-1,-1]]
print(count_negatives(grid))

  
Output

output py 1

Implementation in C++

#include <bits/stdc++.h>
#define ll long long int
using namespace std;

// Function to count negatives in sorted matrix
int countNegatives(vector<vector<int>> grid){

    // Decomposing a 2-d array to 1-d array
    vector<int> converted_array;
    for (int i = 0; i < grid.size(); i++){
        for (int j = 0; j < grid[0].size(); j++){
            converted_array.push_back(grid[i][j]);
        }
    }

    // Counting the negatives in 1-d array
    int ans = 0;
    for (int i = 0; i < converted_array.size(); i++){
        if (converted_array[i] < 0)
            ans++;
    }
    return ans;
}

int main(){
    // Driver code
    vector<vector<int>> grid = {{1,-1},{-1,-1}};
    cout << countNegatives(grid) << endl;
    
    return 0;
}


Output

output cpp 1

Complexity Analysis

Let’s discuss the complexity analysis of the code above. 

Time Complexity

We are traversing through the entire matrix, which is of M*N dimensions. So our time complexity reaches O(M*N).

Space Complexity

We are appending the values to an empty list whose max value can go, the total number of elements of the matrix. So our space complexity goes, O(M*N), where M*N is the dimensions of the matrix, and so the total count of elements in the matrix is also the same as the dimension.

Binary Search Approach

In this approach, we will solve this problem via Binary Search. This works as the matrix is in sorted order.

Algorithm

Since the matrix(rows and columns) is sorted, we will apply a binary search to find the most negative element in a row. When found that the elements proceeding are also negative, hence we move forward to the next row.

Step 1: Iterate over each row of the matrix.

Step 2: Perform the binary search on each row.

Step 3: Check for the first negative number in the row by comparing it with the mid. If the mid element is negative, then shift left, else, shift right.

Step 4: When the binary search is over, the first negative element in the row is obtained.

Step 5: Count the number of negative elements in each row, and return as the answer.

Dry Run

Let us go through the above approach with a dry run.

Step 1: Iterate over the rows of the matrix, the first row being [1, -1].

Step 2: Set low and high as the starting and ending element’s index of the row. Here low = 0 and high = 1.

Step 3: Take mid and compare the value with negative elements.

Step 4: Here, mid = 0. Take the row value at mid, i.e., the row’s 0th index, which comes out to be positive (1). So we set low = mid + 1, i.e., low = 1.

dry run 1

Step 5: Now, low =1 and high =1, so mid =1, and the row’s 1st index is -1, which is negative. So we stop here.

Step 6: This means all the values starting from index 1 and beyond are negative in the row. So we append ‘len(row) - mid’, i.e., 2 - 1 = 1 to the answer ( number of negative elements after index 1), i.e., ans = 1. 

Step 7: Now we check for another row, and the same procedure is followed. We start with low = 0 and high = 1, so mid = 0.

Step 8: Now the element at the index mid in the grid is -1 (negative), so we change high to high = mid - 1. Now high == low == mid, i.e., mid = 0, so we stop and add ‘len(row) - mid’, i.e., 2 - 0 = 2 to the answer (number of negative elements after index 0), i.e., ans = 1+2 = 3.

dry run 2

Step 9: We have now reached the end of the matrix, and so we return 3 as the answer. 

Implementation in Python

def binarySearch(row,n):
    # Binary search to be performed on a row
    low= 0
    high= n - 1
    count = 0
        
    # Finding the first negative element in the row
    # returning the length of row after that element
    while (low <= high):
        mid = low + (high - low) // 2
        if (row[mid] < 0):
            high = mid - 1
        else:
            low = mid + 1
    count += n - low
    return count
    
# Function to count negative integers in a matrix
def countNegatives(matrix):
         
    r=len(matrix)
    c=len(matrix[0])

    # Count of negatives in every row
    count = 0
    for row in matrix:
        count+=binarySearch(row,c)
        
    return count

# Driver code
grid = [[1,-1],[-1,-1]]
print(countNegatives(grid))


Output

output py

Implementation in C++

#include <bits/stdc++.h>
using namespace std;

int binarySearch(vector<int> &row, int n){
    // Binary search to be performed on a row
    int low = 0; 
    int high = n - 1;
    int count = 0;
        
    /* 
        Finding the first negative element in the row
        returning the length of row after that element 
    */
    while (low <= high){
        int mid = low + (high - low) / 2;
        if (row[mid] < 0)
            high = mid - 1;
        else
            low = mid + 1;
    }
    count += n - low;
    return count;
}

// Function to count negative integers in a matrix
int countNegatives(vector<vector<int>> &matrix){
    int r=matrix.size();
    int c= matrix[0].size();
    
    int count = 0;
    // Count of negatives in every row
    for (int i = 0; i < r; i++){
        count += binarySearch(matrix[i], c);
    }
    return count;
}

int main(){
    // Driver code
    vector<vector<int>> grid = {{1,-1},{-1,-1}};
    cout<<countNegatives(grid)<<endl;
    return 0;
}


Output

output cpp

Complexity Analysis

Let’s analyze the complexity of the above code.

Time Complexity

Since we are performing a binary search on every row of the grid, it takes O(M*log(N)), time complexity, where ‘M’ is the number of rows, and ‘N’ is the number of elements in each row.

Space Complexity

Since we only traverse and not storing anything. So our space complexity reaches O(1).

Optimized Traversal Approach

This is a better approach than the previous one. We will call it an optimized approach. Instead of traversing through the entire elements, we will traverse selectively.

Algorithm

Since this is an optimized approach; we’ll optimize the time and space complexity compared to the previous one. Here we will be taking advantage of the fact that the matrix is sorted, both row and column-wise.

Step 1: Start from the top-right corner of the matrix (as this is the smallest element in the first row). 

Step 2: Now, check it column-wise (here, it is the largest element of the matrix).

Step 3: Check if the element is negative or positive; if this element turns out to be negative, then all the elements belonging to the same column will also be negative.

Step 4: If the element turns out to be positive, then move forward (or, should I say backward) in the array and check for the negative elements.

Step 5: The first negative element found in that row ensures that the column containing this element has only negative integers.

Step 6: Now traverse in a similar manner for other columns. If a positive integer is found, traverse within the column to find the negative integer. When a negative integer is encountered change the column. 

Dry Run

Let’s run the above algorithm over an example.

Example

Input:

grid = [ [1,-1], [-1,-1] ]


Step 1: Start with the top-right corner of the matrix, i.e. -1.

Step 2: Since the element is negative (-1), and since we are on the first row, it is safe to say that the elements belonging to the column of -1 are also negative.

dry run 2

Step 3: Create a variable called ans, which shall append the count of negative integers at every point. 

Step 4: We will move left in the first row until we find a positive integer. Make sure to add the count of negative integers to the variable ans.

Step 5: As we reach the element which has a positive integer. Now we will be incrementing the column number and going down on the column until a negative integer is found.
 

dry run 3

Step 6: As we reach a negative integer, we shall again traverse left until a negative integer is found.

Step 7: Here, as we encounter -1 we move left in the same row. We update the value of ans and add the length of the column to it. So now ans becomes 2.

Step 8: Now we got 1, which is positive, so we have to traverse further in the column containing 1. We will stop just when we get any negative integer, in this column.

Step 9: We iterated in the column, and the very next element got to be -1, which is negative, so now we will move to the next column, and append the remaining length of the column to ans. So now ans becomes 3.

dry run 4

 

Step 10: Since now we have iterated the entire matrix, we return, ans, which comes out to be 3

dry run 2 10

Implementation in Python

# Function to count negatives in sorted matrix
def count_negatives(grid: list[list[int]]) -> int:

    m, n = len(grid), len(grid[0])

    # Two pointer optimized approach
    i, j = 0, n - 1
    ans = 0
    while i < m and j >= 0:
        # Current element
        curr = grid[i][j]

        # If current element is negative, we
        # say the entire column will be negative
        # as the matrix is sorted and move to the
        # left column, else we traverse within the column.

        if curr < 0:
            ans += m - i
            j -= 1
        else:
            i += 1
    return ans

# Driver code
grid = [[1,-1],[-1,-1]]
print(count_negatives(grid))


Output

output 2 py

Implementation in C++

#include <bits/stdc++.h>
#define ll long long int
using namespace std;

// Function to count negatives in sorted matrix
int countNegatives(vector<vector<int>> grid){

    int m = grid.size();
    int n = grid[0].size();

    // Two pointer optimized approach
    int i = 0;
    int j = n - 1;
    int ans = 0;
    while (i < m and j >= 0)
    {
        // Current element
        int curr = grid[i][j];
        
        /* 
            If current element is negative, we
            say the entire column will be negative
            as the matrix is sorted and move to the 
            left column, else traverse within the column.
        */

        if (curr < 0){
            ans += m - i;
            j--;
        }
        else
            i++;
    }
    return ans;
}

int main(){
   vector<vector<int>> grid = {{1,-1},{-1,-1}};
   cout << countNegatives(grid) << endl;
   
   return 0;
}


Output

output c++ 2

Complexity Analysis

Let’s discuss the complexity analysis of the above code. 

Time Complexity

As we merely traverse through the matrix, our time complexity reaches somewhat close to O(M+N), where M*N is the dimension of the matrix.

Space Complexity

As we are not appending anything anywhere, our space complexity stays O(1).

Also see, Euclid GCD Algorithm

Frequently Asked Questions

What are the different approaches to this problem, and which one is optimized?

We can use brute force or a two-pointer approach to solve this problem. There can be many solutions to this, but the two pointers will be the most optimized, as its Time Complexity reaches O(m+n).

When traversing through the grid, what is the time and space complexity?

When we traverse through the grid, it takes O(m*n) time, where m*n is the dimension of the grid. The space complexity for traversing is O(1) until and unless we are not appending the values to any data structure.

What are the different types of traversals possible in a grid?

In a typical grid, we can follow simple traversal using two for loops. Two types of traversals are also present, i.e., Breadth First Search and Depth First Search, which are used to traverse elements of the grid.

What is a two-pointer approach, and how is it working on the above question?

Two pointer approach uses two pointers, namely and j, where we traverse the grid with the help of two pointers. In this question, we are using two pointers to determine the row and column of the element, and then we are traversing according to the algorithm.

How to decompose a 2-D array into a 1-D array?

To convert a 2-D array into a 1-D array, use a for loop, a map, or a spread operator, to spread the array elements. You can also use chain objects in Python. 

Also Read - Strong number in c

Conclusion

So Ninjas!! We saw different approaches how to count negative numbers in a sorted matrix. We hope our approach matches yours on some level or another. 

Check out more of our articles:

If you want to learn more, Refer to our Guided Path to upskill yourself in DSACompetitive ProgrammingJavaScriptSystem Design, and many more! If you want to test your competency in coding, check out the mock test series and participate in the contests hosted on Coding Ninjas Studio!

But you have just started your learning process and are looking for questions from tech giants like Amazon, Microsoft, Uber, etc. In that case, you must look at the problemsinterview experiences, and interview bundles for placement preparations.

However, consider our paid courses to give your career an edge over others!

Happy Coding!

Previous article
Koko Eating Bananas
Next article
Merge two sorted arrays in O(1) extra space using QuickSort partition
Live masterclass