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.
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.
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.
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.
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 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))
You can also try this code with Online Python Compiler
#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;
}
You can also try this code with Online C++ Compiler
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.
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.
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))
You can also try this code with Online Python Compiler
#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;
}
You can also try this code with Online C++ Compiler
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.
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.
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.
Step 10: Since now we have iterated the entire matrix, we return, ans, which comes out to be 3.
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))
You can also try this code with Online Python Compiler
#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;
}
You can also try this code with Online C++ Compiler
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 i 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.
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 problems, interview experiences, and interview bundles for placement preparations.
However, consider our paid courses to give your career an edge over others!
8+ registered 