Count negative elements present in the sorted matrix in linear time
Given an M × N matrix, which is row-wise and column-wise sorted, count the total number of negative elements present in it in linear time.
For example,
[ -7 -3 -1 3 5 ]
[ -3 -2 2 4 6 ]
[ -1 1 3 5 8 ]
[ 3 4 7 8 9 ]
Output:
The total number of negative elements present is 6.
We can do a binary search to find the last occurrence of a negative number or the first occurrence of a positive number for each row. The complexity of this solution will be O(M × log(N)), which is not linear as per problem time constraints.
The idea is to take advantage of the fact that the matrix is row-wise and column-wise sorted. Start from the matrix’s top-rightmost cell and do the following until the matrix boundary is reached:
- If the current element is negative, increment the negative count and move to the next row.
- If the current element is positive, move to the left cell.
The algorithm can be implemented as follows in C++, Java, and Python:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 |
#include <iostream> #include <vector> using namespace std; int count(vector<vector<int>> const &mat) { // base case if (mat.size() == 0) { return 0; } int M = mat.size(); int N = mat[0].size(); // variable to store negative number count int negative = 0; // start from `(0, N-1)` cell, i.e., top-rightmost cell of the matrix int i = 0, j = N - 1; // run till matrix boundary is reached while (i <= M - 1 && j >= 0) { // if the current element is negative if (mat[i][j] < 0) { negative += j + 1; // increment the negative count i++; // move to the next row } else { j--; // move to the cell to the left } } // return negative number count return negative; } int main() { vector<vector<int>> mat = { { -7, -3, -1, 3, 5 }, { -3, -2, 2, 4, 6 }, { -1, 1, 3, 5, 8 }, { 3, 4, 7, 8, 9 } }; cout << "The total number of negative elements present is " << count(mat); return 0; } |
Output:
The total number of negative elements present is 6
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 |
class Main { public static int count(int[][] mat) { // base case if (mat == null || mat.length == 0) { return 0; } // `M × N` matrix int M = mat.length; int N = mat[0].length; // variable to store negative number count int negative = 0; // start from `(0, N-1)` cell, i.e., top-rightmost cell of the matrix int i = 0, j = N - 1; // run till matrix boundary is reached while (i <= M - 1 && j >= 0) { // if the current element is negative if (mat[i][j] < 0) { negative += j + 1; // increment the negative count i++; // move to the next row } else { j--; // move to the cell to the left } } // return negative number count return negative; } public static void main(String[] args) { int[][] mat = { { -7, -3, -1, 3, 5 }, { -3, -2, 2, 4, 6 }, { -1, 1, 3, 5, 8 }, { 3, 4, 7, 8, 9 } }; System.out.print("The total number of negative elements present is " + count(mat)); } } |
Output:
The total number of negative elements present is 6
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
def count(mat): # base case if not mat or not len(mat): return 0 # `M × N` matrix (M, N) = (len(mat), len(mat[0])) # variable to store negative number count negative = 0 # start from `(0, N-1)` cell, i.e., top-rightmost cell of the matrix (i, j) = (0, N - 1) # run till matrix boundary is reached while i <= M - 1 and j >= 0: # if the current element is negative if mat[i][j] < 0: negative += j + 1 # increment the negative count i = i + 1 # move to the next row else: j = j - 1 # move to the cell to the left # return negative number count return negative if __name__ == '__main__': mat = [ [-7, -3, -1, 3, 5], [-3, -2, 2, 4, 6], [-1, 1, 3, 5, 8], [3, 4, 7, 8, 9] ] print("The total number of negative elements present is", count(mat)) |
Output:
The total number of negative elements present is 6
The time complexity of the proposed solution is O(M + N) for an M × N matrix and doesn’t require any extra space.
Exercise: Count zeros in a row-wise and column-wise sorted matrix.
Report all occurrences of an element in a row-wise and column-wise sorted matrix in linear time
Find the index of a row containing the maximum number of 1’s in a binary matrix
Find minimum passes required to convert all negative values in a matrix
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)