Amazon Interview Question: Count Negative Integers in Matrix

💡Strategies for Solving This Problem

The Amazon Classic

Got this in my Amazon phone screen. The key detail: matrix is sorted both row-wise and column-wise. That's your hint that binary search or two-pointer will work.

The Setup

Matrix like this:

[-5, -4, -3,  1]
[-3, -2,  0,  2]
[-1,  0,  1,  3]
[ 1,  2,  3,  4]

Count negative numbers. Naive: check every cell = O(n×m). We can do better.

Approach 1: Start Bottom-Left (My Solution)

Start at bottom-left corner. Why? Because:

Moving right → numbers increase
Moving up → numbers decrease

If current number is negative, entire column above is negative. Count and move right. If positive, move up.

This is O(n+m) time - way better than O(n×m).

Approach 2: Binary Search Per Row

For each row, binary search for the first non-negative number. Count negatives in that row.

O(n log m) time. Works but slower than two-pointer approach.

My Interview

I initially tried to do something complex with diagonals. My interviewer said "Start simple - what about the corners?" That hint saved me. Always consider the corners in matrix problems.

✅Solution

Solution: Two-Pointer from Bottom-Left

function countNegatives(matrix) {
    if (!matrix || matrix.length === 0) return 0;

    let rows = matrix.length;
    let cols = matrix[0].length;
    let count = 0;

    // Start at bottom-left corner
    let row = rows - 1;
    let col = 0;

    while (row >= 0 && col < cols) {
        if (matrix[row][col] < 0) {
            // All elements above in this column are negative
            count += row + 1;
            col++;  // Move right
        } else {
            // Current element is non-negative
            row--;  // Move up
        }
    }

    return count;
}

// Test
const matrix1 = [
    [-5, -4, -3,  1],
    [-3, -2,  0,  2],
    [-1,  0,  1,  3],
    [ 1,  2,  3,  4]
];

console.log(countNegatives(matrix1));  // 6

const matrix2 = [
    [-3, -2, -1],
    [-2, -1,  0],
    [-1,  0,  1]
];

console.log(countNegatives(matrix2));  // 6 (all in upper-left)

How It Works

Let's trace through matrix1 starting at (3,0) = 1:

(3,0) = 1 (positive) → move up to (2,0)
(2,0) = -1 (negative) → count 3 rows (0,1,2), move right to (2,1)
(2,1) = 0 (non-negative) → move up to (1,1)
(1,1) = -2 (negative) → count 2 rows (0,1), move right to (1,2)
(1,2) = 0 (non-negative) → move up to (0,2)
(0,2) = -3 (negative) → count 1 row (0), move right to (0,3)
(0,3) = 1 (positive) → move up, exit loop

Total: 3 + 2 + 1 = 6 negatives

Alternative: Binary Search

function countNegativesBinary(matrix) {
    let count = 0;

    for (let row of matrix) {
        // Binary search for first non-negative
        let left = 0;
        let right = row.length - 1;
        let firstNonNeg = row.length;

        while (left <= right) {
            let mid = Math.floor((left + right) / 2);

            if (row[mid] < 0) {
                left = mid + 1;
            } else {
                firstNonNeg = mid;
                right = mid - 1;
            }
        }

        count += firstNonNeg;
    }

    return count;
}

console.log(countNegativesBinary(matrix1));  // 6

Complexity Comparison

Method	Time	Space	When to Use
Two-Pointer	O(n+m)	O(1)	Best for sorted matrix
Binary Search	O(n log m)	O(1)	If only rows sorted
Brute Force	O(n×m)	O(1)	Never in interview

Edge Cases

All negative: Count = n × m
All positive: Count = 0
Empty matrix: Count = 0
Single row/column: Algorithm still works

Amazon tip: They love matrix problems. Practice: search in sorted matrix, spiral traversal, set matrix zeros.