Count Negative Numbers in Sorted Matrix

🎯

Count Negative Numbers in Sorted Matrix

easyMATRIXAmazonGoogle

Imagine you are analyzing temperature data from a grid of sensors, and you want to quickly count how many sensors recorded below-freezing temperatures.

💡 This problem involves searching and counting in a 2D matrix where each row and column is sorted. Beginners often struggle because they try to scan every element, missing the opportunity to leverage the sorted property for faster counting.

📋

Problem Statement

Given an m x n matrix sorted in non-increasing order both row-wise and column-wise (each row and column is sorted in decreasing order), count the number of negative numbers in the matrix. Input: a 2D integer matrix. Output: an integer representing the count of negative numbers.

1 ≤ m, n ≤ 1000-10^5 ≤ matrix[i][j] ≤ 10^5Rows and columns are sorted in non-increasing order

💡

Example

Input"[[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]]"

Output8

There are 8 negative numbers in the matrix: -1, -1, -1, -2, -1, -1, -2, -3.

• Matrix with all positive numbers → output 0
• Matrix with all negative numbers → output m*n
• Matrix with a single element negative → output 1
• Matrix with a single element non-negative → output 0

⚠️

Common Mistakes

Not leveraging the sorted property and scanning all elements

Solution is too slow and may time out on large inputs

✅ Use binary search or staircase search to reduce time complexity

Incorrect binary search boundaries or conditions

Binary search returns wrong index, leading to incorrect counts

✅ Carefully implement binary search to find first negative element

In staircase search, moving in wrong direction on condition

Infinite loop or incorrect count results

✅ Remember to move left when negative found, down otherwise

Not handling empty matrix or single-element matrix

Runtime errors or wrong output

✅ Add checks for empty input and handle small cases explicitly

🧠

Brute Force (Nested Loops)

💡 This approach exists to establish a baseline understanding by checking every element. It is simple but inefficient, helping beginners grasp the problem structure before optimizing.

Intuition

Check every element in the matrix and count if it is negative. Since the matrix is sorted, this approach ignores that property and treats the matrix as an unsorted grid.

Algorithm

1. Initialize count to 0.
2. Iterate over each row.
3. Within each row, iterate over each element.
4. If the element is negative, increment count.
5. Return the count after all elements are checked.

💡 The nested loops are easy to understand but can be inefficient for large matrices because they do not leverage the sorted property.

</>

Code

def countNegatives(grid):
    count = 0
    for row in grid:
        for num in row:
            if num < 0:
                count += 1
    return count

# Driver code
if __name__ == '__main__':
    matrix = [[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]]
    print(countNegatives(matrix))  # Output: 8

Line Notes

count = 0Initialize counter to track negative numbers

for row in grid:Iterate over each row in the matrix

for num in row:Iterate over each element in the current row

if num < 0:Check if the current element is negative

count += 1Increment count when a negative number is found

return countReturn the total count after scanning all elements

public class Solution {
    public static int countNegatives(int[][] grid) {
        int count = 0;
        for (int[] row : grid) {
            for (int num : row) {
                if (num < 0) {
                    count++;
                }
            }
        }
        return count;
    }

    public static void main(String[] args) {
        int[][] matrix = {{4,3,2,-1},{3,2,1,-1},{1,1,-1,-2},{-1,-1,-2,-3}};
        System.out.println(countNegatives(matrix)); // Output: 8
    }
}

Line Notes

int count = 0;Initialize counter for negative numbers

for (int[] row : grid)Loop through each row in the matrix

for (int num : row)Loop through each element in the current row

if (num < 0)Check if the element is negative

count++;Increment count when negative found

return count;Return total negative count after full scan

#include <iostream>
#include <vector>
using namespace std;

int countNegatives(vector<vector<int>>& grid) {
    int count = 0;
    for (auto& row : grid) {
        for (int num : row) {
            if (num < 0) {
                count++;
            }
        }
    }
    return count;
}

int main() {
    vector<vector<int>> matrix = {{4,3,2,-1},{3,2,1,-1},{1,1,-1,-2},{-1,-1,-2,-3}};
    cout << countNegatives(matrix) << endl; // Output: 8
    return 0;
}

Line Notes

int count = 0;Initialize count variable to zero

for (auto& row : grid)Range-based loop over each row

for (int num : row)Range-based loop over each element in row

if (num < 0)Check if current element is negative

count++;Increment count for each negative element

return count;Return total count after scanning all elements

function countNegatives(grid) {
    let count = 0;
    for (const row of grid) {
        for (const num of row) {
            if (num < 0) {
                count++;
            }
        }
    }
    return count;
}

// Driver code
const matrix = [[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]];
console.log(countNegatives(matrix)); // Output: 8

Line Notes

let count = 0;Initialize counter for negative numbers

for (const row of grid)Iterate over each row in the matrix

for (const num of row)Iterate over each element in the current row

if (num < 0)Check if the element is negative

count++;Increment count when negative found

return count;Return total count after full iteration

⏱

Complexity

TimeO(m*n)

SpaceO(1)

We visit every element once, so time is proportional to total elements. No extra space besides counters is used.

💡 For a 1000x1000 matrix, this means 1,000,000 operations, which can be slow in interviews.

Interview Verdict: Accepted but inefficient for large inputs

This approach works but is too slow for large matrices; it helps confirm correctness before optimizing.

🧠

Optimized Row-wise Binary Search

💡 This approach leverages the sorted property of each row to quickly find the first negative number using binary search, reducing the number of elements checked.

Intuition

Since each row is sorted in decreasing order, negatives appear consecutively at the end. Use binary search on each row to find the first negative element's index, then count all elements after it.

Algorithm

1. Initialize count to 0.
2. For each row, perform binary search to find the first negative number's index.
3. Add the count of negative numbers in that row (length - index) to total count.
4. Return the total count after processing all rows.

💡 Binary search reduces scanning each row from O(n) to O(log n), improving overall efficiency.

</>

Code

def countNegatives(grid):
    def binary_search(row):
        left, right = 0, len(row) - 1
        while left <= right:
            mid = (left + right) // 2
            if row[mid] < 0:
                right = mid - 1
            else:
                left = mid + 1
        return left

    count = 0
    for row in grid:
        idx = binary_search(row)
        count += len(row) - idx
    return count

# Driver code
if __name__ == '__main__':
    matrix = [[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]]
    print(countNegatives(matrix))  # Output: 8

Line Notes

def binary_search(row):Define helper to find first negative index in a row

left, right = 0, len(row) - 1Initialize binary search boundaries

if row[mid] < 0:If mid element is negative, search left half

else: left = mid + 1If mid element non-negative, search right half

return leftLeft points to first negative index after loop ends

for row in grid:Process each row independently

idx = binary_search(row)Find first negative index in current row

count += len(row) - idxAdd count of negatives in this row

public class Solution {
    public static int countNegatives(int[][] grid) {
        int count = 0;
        for (int[] row : grid) {
            int left = 0, right = row.length - 1;
            while (left <= right) {
                int mid = left + (right - left) / 2;
                if (row[mid] < 0) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
            count += row.length - left;
        }
        return count;
    }

    public static void main(String[] args) {
        int[][] matrix = {{4,3,2,-1},{3,2,1,-1},{1,1,-1,-2},{-1,-1,-2,-3}};
        System.out.println(countNegatives(matrix)); // Output: 8
    }
}

Line Notes

int left = 0, right = row.length - 1;Initialize binary search boundaries for each row

if (row[mid] < 0)Check if mid element is negative to adjust search

right = mid - 1;Move right pointer left to find first negative

left = mid + 1;Move left pointer right if mid is non-negative

count += row.length - left;Add count of negatives after first negative index

for (int[] row : grid)Iterate over each row

#include <iostream>
#include <vector>
using namespace std;

int countNegatives(vector<vector<int>>& grid) {
    int count = 0;
    for (auto& row : grid) {
        int left = 0, right = (int)row.size() - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (row[mid] < 0) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        count += (int)row.size() - left;
    }
    return count;
}

int main() {
    vector<vector<int>> matrix = {{4,3,2,-1},{3,2,1,-1},{1,1,-1,-2},{-1,-1,-2,-3}};
    cout << countNegatives(matrix) << endl; // Output: 8
    return 0;
}

Line Notes

int left = 0, right = (int)row.size() - 1;Set binary search boundaries for current row

if (row[mid] < 0)Check if mid element is negative

right = mid - 1;Search left half to find first negative

left = mid + 1;Search right half if mid is non-negative

count += (int)row.size() - left;Count negatives from first negative index to end

for (auto& row : grid)Loop over each row in matrix

function countNegatives(grid) {
    function binarySearch(row) {
        let left = 0, right = row.length - 1;
        while (left <= right) {
            let mid = Math.floor((left + right) / 2);
            if (row[mid] < 0) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }

    let count = 0;
    for (const row of grid) {
        const idx = binarySearch(row);
        count += row.length - idx;
    }
    return count;
}

// Driver code
const matrix = [[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]];
console.log(countNegatives(matrix)); // Output: 8

Line Notes

function binarySearch(row)Helper function to find first negative index in a row

let left = 0, right = row.length - 1;Initialize binary search pointers

if (row[mid] < 0)Check if mid element is negative

right = mid - 1;Move right pointer left to find first negative

left = mid + 1;Move left pointer right if mid is non-negative

for (const row of grid)Iterate over each row

count += row.length - idx;Add count of negatives in current row

⏱

Complexity

TimeO(m * log n)

SpaceO(1)

Binary search on each of the m rows takes O(log n), so total time is O(m log n). Space remains constant.

💡 For a 1000x1000 matrix, this reduces operations from 1,000,000 to about 10,000, a significant speedup.

Interview Verdict: Accepted and efficient for medium-sized inputs

This approach is a good improvement and often acceptable in interviews, showing understanding of binary search.

🧠

Optimal Staircase Search from Top-Right

💡 This approach exploits the matrix's sorted property fully by starting from the top-right corner and moving left/down to count negatives in O(m+n) time.

Intuition

Start at the top-right element. If it's negative, all elements below in that column are negative, so add them to count and move left. If not negative, move down to find negatives in lower rows.

Algorithm

1. Initialize count to 0, row to 0, and col to last column index.
2. While row < m and col >= 0:
3. If element at (row, col) is negative, add (m - row) to count and move left (col--).
4. Else, move down (row++).
5. Return count after loop ends.

💡 This method skips entire rows or columns at once, leveraging sorted order to avoid unnecessary checks.

</>

Code

def countNegatives(grid):
    m, n = len(grid), len(grid[0])
    count = 0
    row, col = 0, n - 1
    while row < m and col >= 0:
        if grid[row][col] < 0:
            count += m - row
            col -= 1
        else:
            row += 1
    return count

# Driver code
if __name__ == '__main__':
    matrix = [[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]]
    print(countNegatives(matrix))  # Output: 8

Line Notes

m, n = len(grid), len(grid[0])Get matrix dimensions

row, col = 0, n - 1Start from top-right corner

while row < m and col >= 0:Traverse until out of bounds

if grid[row][col] < 0:If current element negative, all below are negative

count += m - rowAdd count of all negatives in current column below

col -= 1Move left to next column

else: row += 1If not negative, move down to next row

return countReturn total count after traversal

public class Solution {
    public static int countNegatives(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int count = 0;
        int row = 0, col = n - 1;
        while (row < m && col >= 0) {
            if (grid[row][col] < 0) {
                count += m - row;
                col--;
            } else {
                row++;
            }
        }
        return count;
    }

    public static void main(String[] args) {
        int[][] matrix = {{4,3,2,-1},{3,2,1,-1},{1,1,-1,-2},{-1,-1,-2,-3}};
        System.out.println(countNegatives(matrix)); // Output: 8
    }
}

Line Notes

int m = grid.length, n = grid[0].length;Get matrix dimensions

int row = 0, col = n - 1;Start at top-right corner

while (row < m && col >= 0)Traverse while inside matrix bounds

if (grid[row][col] < 0)Check if current element is negative

count += m - row;Add count of all negatives below in column

col--;Move left to next column

else { row++; }Move down if current element non-negative

return count;Return total negative count

#include <iostream>
#include <vector>
using namespace std;

int countNegatives(vector<vector<int>>& grid) {
    int m = (int)grid.size(), n = (int)grid[0].size();
    int count = 0;
    int row = 0, col = n - 1;
    while (row < m && col >= 0) {
        if (grid[row][col] < 0) {
            count += m - row;
            col--;
        } else {
            row++;
        }
    }
    return count;
}

int main() {
    vector<vector<int>> matrix = {{4,3,2,-1},{3,2,1,-1},{1,1,-1,-2},{-1,-1,-2,-3}};
    cout << countNegatives(matrix) << endl; // Output: 8
    return 0;
}

Line Notes

int m = (int)grid.size(), n = (int)grid[0].size();Get matrix dimensions

int row = 0, col = n - 1;Initialize starting position at top-right

while (row < m && col >= 0)Traverse matrix within bounds

if (grid[row][col] < 0)Check if current element is negative

count += m - row;Add count of all negatives below current position

col--;Move left to next column

else { row++; }Move down if element is non-negative

return count;Return total count after traversal

function countNegatives(grid) {
    const m = grid.length, n = grid[0].length;
    let count = 0;
    let row = 0, col = n - 1;
    while (row < m && col >= 0) {
        if (grid[row][col] < 0) {
            count += m - row;
            col--;
        } else {
            row++;
        }
    }
    return count;
}

// Driver code
const matrix = [[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]];
console.log(countNegatives(matrix)); // Output: 8

Line Notes

const m = grid.length, n = grid[0].length;Get matrix dimensions

let row = 0, col = n - 1;Start from top-right corner

while (row < m && col >= 0)Traverse while inside matrix bounds

if (grid[row][col] < 0)Check if current element is negative

count += m - row;Add count of all negatives below current position

col--;Move left to next column

else { row++; }Move down if element is non-negative

return count;Return total negative count

⏱

Complexity

TimeO(m + n)

SpaceO(1)

Each step moves either left or down, so at most m + n steps are taken.

💡 For a 1000x1000 matrix, this means about 2000 operations, which is very efficient.

Interview Verdict: Accepted and optimal

This is the best approach to implement in interviews for this problem, demonstrating mastery of matrix properties.

📊

All Approaches - One-Glance Tradeoffs

💡 In interviews, coding the optimal staircase search is recommended for efficiency and clarity.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(m*n)	O(1)	No	N/A	Mention only - never code
2. Row-wise Binary Search	O(m*log n)	O(1)	No	N/A	Good to mention as improvement
3. Staircase Search (Optimal)	O(m + n)	O(1)	No	N/A	Code this approach in interviews

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice all approaches, and prepare to explain tradeoffs clearly in interviews.

How to Present

Step 1: Clarify the problem and constraints with the interviewer.Step 2: Present the brute force approach to show understanding.Step 3: Discuss how the sorted property can be leveraged with binary search.Step 4: Explain the optimal staircase search approach and why it is efficient.Step 5: Code the optimal approach and test with examples.

Time Allocation

Clarify: 2min → Approach: 3min → Code: 10min → Test: 5min. Total ~20min

What the Interviewer Tests

Interviewer tests your ability to recognize sorted matrix properties, optimize search, and write clean, efficient code.

Common Follow-ups

• What if the matrix is sorted in increasing order instead? → Adjust search direction accordingly.
• Can you count negative numbers if only rows or only columns are sorted? → Discuss partial optimizations.

💡 These follow-ups test your adaptability and deeper understanding of matrix sorting variations.

🔍

Pattern Recognition

When to Use

Use this pattern when given a matrix sorted row-wise and column-wise and asked to count or search for elements efficiently.

Signature Phrases

'matrix sorted in non-increasing order''count negative numbers in matrix''each row and column sorted'

NOT This Pattern When

Problems where matrix is unsorted or only partially sorted require different approaches.

Similar Problems

Find Kth Smallest Element in a Sorted Matrix - uses similar binary search and staircase techniquesSearch a 2D Matrix II - also uses staircase search for efficient lookup

Practice

1. Given the following code for maximum hourglass sum using sliding window, what is the value of max_sum after processing the first row (i=0) of the matrix below? Matrix: [[1, 1, 1, 0], [0, 1, 0, 0], [1, 1, 1, 0]]

def max_hourglass_sum_sliding(matrix):
    n = len(matrix)
    m = len(matrix[0])
    max_sum = float('-inf')

    for i in range(n - 2):
        current_sum = (matrix[i][0] + matrix[i][1] + matrix[i][2] +
                       matrix[i+1][1] +
                       matrix[i+2][0] + matrix[i+2][1] + matrix[i+2][2])
        if current_sum > max_sum:
            max_sum = current_sum

        for j in range(1, m - 2):
            current_sum -= (matrix[i][j-1] + matrix[i+1][j] + matrix[i+2][j-1])
            current_sum += (matrix[i][j+2] + matrix[i+1][j+1] + matrix[i+2][j+2])
            if current_sum > max_sum:
                max_sum = current_sum
    return max_sum

easy

A. 7

B. 8

C. 6

D. 9

Solution

1. Step 1: Calculate initial hourglass sum at i=0, j=0

   Sum = 1+1+1 + 1 + 1+1+1 = 7

2. Step 2: Check sliding window for j=1 (only one possible)

   Subtract left column: 1 + 1 + 1 = 3; Add right column: 0 + 0 + 0 = 0; New sum = 7 - 3 + 0 = 4; max_sum remains 7

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Initial sum 7 is max after first row [OK]

Hint: Initial hourglass sum sets max before sliding [OK]

Common Mistakes:

• Off-by-one in sliding window update
• Forgetting to update max_sum after sliding
• Misindexing matrix elements

2. Given the following code implementing the optimal in-place Set Matrix Zeroes algorithm, what is the final state of the matrix after calling setZeroes(matrix) on matrix = [[1,1,1],[1,0,1],[1,1,1]]?

easy

A. [[1,0,1],[0,0,0],[1,0,1]]

B. [[1,0,1],[0,0,0],[1,0,1]]

C. [[1,1,1],[1,0,1],[1,1,1]]

D. [[1,1,1],[0,0,0],[1,0,1]]

Solution

1. Step 1: Mark rows and columns

   Zero found at matrix[1][1], so set matrix[1][0] = 0 and matrix[0][1] = 0.

2. Step 2: Update matrix based on flags

   For i=1, j=1 and j=2: matrix[1][0] = 0 -> zero row 1; for i=2, j=1: matrix[0][1] = 0 -> zero column 1.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Only row 1 and column 1 zeroed, matching output [OK]

Hint: Mark first row/col, then zero inner matrix [OK]

Common Mistakes:

• Forgetting to check first row/column zero flags
• Zeroing during first pass loses info
• Off-by-one errors in loops

3. You are given a 2D matrix and asked to output all elements starting from the outermost layer and moving inward in a clockwise manner, visiting each element exactly once. Which algorithmic approach best guarantees an efficient and correct solution for this problem?

easy

A. Perform a depth-first search (DFS) starting from the top-left corner, marking visited cells to avoid repeats.

B. Use a greedy approach that picks the next available element in clockwise order without tracking boundaries.

C. Apply dynamic programming to store intermediate traversal states and build the spiral order iteratively.

D. Simulate the traversal by shrinking the boundaries inward after completing each outer layer, ensuring no element is revisited.

Solution

1. Step 1: Understand the problem constraints

   The problem requires visiting all elements in a matrix in a spiral order without repetition, moving layer by layer inward.

2. Step 2: Identify the approach that guarantees correctness and efficiency

   Simulating the traversal by shrinking boundaries after completing each layer ensures no element is revisited and the traversal is orderly and complete.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Boundary shrinking matches the spiral traversal pattern perfectly [OK]

Hint: Boundary shrinking ensures no repeats and full coverage [OK]

Common Mistakes:

• Greedy approach misses boundary checks causing repeats
• DFS can revisit or miss elements without careful visited tracking
• DP is not suitable for traversal order problems

4. What is the time complexity of the optimal in-place boundary shrinking approach to generate an n x n spiral matrix, and why?

medium

A. O(n²) because every cell in the matrix is visited exactly once

B. O(n) because each boundary shrinks linearly

C. O(n³) due to nested loops and repeated boundary checks

D. O(n log n) because of direction cycling and boundary updates

Solution

1. Step 1: Identify the number of cells to fill

   The matrix has n² cells, each must be assigned a value exactly once.

2. Step 2: Analyze loops and operations

   Each iteration fills one side of the current boundary, and boundaries shrink inward. The total number of assignments sums to n², so time complexity is O(n²).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Every cell visited once -> O(n²) time [OK]

Hint: Each cell visited once -> O(n²) time [OK]

Common Mistakes:

• Confusing boundary shrinking with linear time
• Assuming nested loops multiply to cubic time
• Ignoring that direction cycling is constant time

5. Suppose the problem is modified so that the matrix is rectangular (not necessarily square). Which of the following statements about adapting the in-place rotation algorithm is true?

hard

A. The layer-by-layer four-way swap algorithm works unchanged for rectangular matrices.

B. In-place rotation is impossible for non-square matrices; extra space or a different approach is required.

C. Transposing and reversing rows can rotate rectangular matrices in-place without issues.

D. Rotating rectangular matrices by 90 degrees clockwise can be done by swapping elements only in the first row.

Solution

1. Step 1: Understand matrix shape constraints

   In-place rotation by 90 degrees requires the matrix to be square because dimensions swap (rows become columns).

2. Step 2: Evaluate options

   Layer-by-layer swaps rely on equal row and column counts; rectangular matrices require extra space or new matrix to hold rotated result.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Non-square matrices cannot be rotated in-place without dimension mismatch [OK]

Hint: In-place 90° rotation requires square matrix due to dimension swap [OK]

Common Mistakes:

• Assuming in-place rotation works for rectangular matrices
• Confusing transpose with rotation for non-square matrices