Count Negative Numbers in Sorted Matrix

▶

Steps

setup

Initialize variables

Set up initial variables: count is 0, row starts at 0 (top row), and col starts at the last column index (3).

💡 Starting at the top-right corner allows the algorithm to decide whether to move left or down based on the sign of the current element.

Line:

m, n = len(grid), len(grid[0])
count = 0
row, col = 0, n - 1

💡 The initial position at top-right is strategic for efficient traversal.

compare

Check element at (0,3)

Check if the element at row 0, col 3 is negative. It is -1, which is negative.

💡 This check determines whether to move left or down next.

Line:

if grid[row][col] < 0:

💡 Finding a negative means all elements below in this column are also negative due to sorting.

insert

Count negatives in column 3 from row 0 down

Add (m - row) = (4 - 0) = 4 to count because all elements below in this column are negative.

💡 This bulk counting avoids checking each element individually.

Line:

count += m - row

💡 Counting all negatives in this column at once is the key optimization.

shrink

Move left to column 2

Since the current element was negative, move the col pointer left by one to col = 2.

💡 Moving left checks the next element in the same row for negatives.

Line:

col -= 1

💡 Moving left narrows the search to smaller elements in the row.

compare

Check element at (0,2)

Check if element at row 0, col 2 is negative. It is 2, which is not negative.

💡 This check decides whether to move down or left next.

Line:

if grid[row][col] < 0:

💡 Non-negative means no negatives in this column at this row or above.

expand

Move down to row 1

Since the current element is not negative, move the row pointer down by one to row = 1.

💡 Moving down checks the next row in the same column for negatives.

Line:

row += 1

💡 Moving down explores the next row where negatives might appear in this column.

compare

Check element at (1,2)

Check if element at row 1, col 2 is negative. It is 1, which is not negative.

💡 This check again decides the next pointer movement.

Line:

if grid[row][col] < 0:

💡 Still no negatives in this column at this row or above.

expand

Move down to row 2

Move the row pointer down by one to row = 2 to check the next row.

💡 Continuing downward traversal to find negatives in this column.

Line:

row += 1

💡 Moving down explores deeper rows for negatives.

compare

Check element at (2,2)

Check if element at row 2, col 2 is negative. It is -1, which is negative.

💡 Finding a negative triggers counting all negatives below in this column.

Line:

if grid[row][col] < 0:

💡 Negative element means all elements below in this column are negative.

insert

Count negatives in column 2 from row 2 down

Add (m - row) = (4 - 2) = 2 to count for the negatives at rows 2 and 3 in this column.

💡 Bulk counting again speeds up the process.

Line:

count += m - row

💡 Counting all remaining negatives in this column at once is efficient.

shrink

Move left to column 1

Move the col pointer left by one to col = 1 to check the next element in the same row.

💡 Moving left continues the search for negatives in the current row.

Line:

col -= 1

💡 Moving left narrows the search space horizontally.

compare

Check element at (2,1)

Check if element at row 2, col 1 is negative. It is 1, which is not negative.

💡 This check determines the next pointer movement.

Line:

if grid[row][col] < 0:

💡 No negatives here, so move down to next row.

expand

Move down to row 3

Move the row pointer down by one to row = 3 to check the last row.

💡 Moving down explores the last row for negatives in this column.

Line:

row += 1

💡 Moving down continues the vertical search.

compare

Check element at (3,1)

Check if element at row 3, col 1 is negative. It is -1, which is negative.

💡 Finding a negative means counting all remaining negatives in this column.

Line:

if grid[row][col] < 0:

💡 All elements below (none here) plus current are negative.

insert

Count negatives in column 1 from row 3 down

Add (m - row) = (4 - 3) = 1 to count for the negative at row 3 in this column.

💡 Counting the last negative in this column.

Line:

count += m - row

💡 Counting remaining negatives completes the count for this column.

shrink

Move left to column 0

Move the col pointer left by one to col = 0 to check the last column on the left.

💡 Continuing to check for negatives in the last column.

Line:

col -= 1

💡 Moving left narrows the search to the first column.

compare

Check element at (3,0)

Check if element at row 3, col 0 is negative. It is -1, which is negative.

💡 Finding a negative means counting all remaining negatives in this column.

Line:

if grid[row][col] < 0:

💡 All elements below (none) plus current are negative.

insert

Count negatives in column 0 from row 3 down

Add (m - row) = (4 - 3) = 1 to count for the negative at row 3 in this column.

💡 Counting the last negative in the first column.

Line:

count += m - row

💡 Counting completes the total negative count.

shrink

Move left to column -1 (end)

Move the col pointer left by one to col = -1, which ends the while loop as col < 0.

💡 No more columns to check, algorithm terminates.

Line:

col -= 1

💡 Traversal complete, all negatives counted.

reconstruct

Return final count

The while loop ends and the function returns the total count of negative numbers, which is 8.

💡 Returning the final answer completes the algorithm.

Line:

return count

💡 The count variable holds the total negative numbers found efficiently.

def countNegatives(grid):
    m, n = len(grid), len(grid[0])  # STEP 1
    count = 0  # STEP 1
    row, col = 0, n - 1  # STEP 1
    while row < m and col >= 0:  # STEP 2 loop start
        if grid[row][col] < 0:  # STEP 2-3 compare
            count += m - row  # STEP 3 count negatives
            col -= 1  # STEP 4 move left
        else:
            row += 1  # STEP 4 move down
    return count  # STEP 20 return final count

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

📊

Count Negative Numbers in Sorted Matrix - Watch the Algorithm Execute, Step by Step

Watching each pointer move and count update reveals how the algorithm leverages the sorted property of the matrix to skip unnecessary checks.

setup

row

4

0

3

1

2

2

col

-1

3

Result: 0

compare

row

4

0

3

1

2

2

col

-1

3

Result: 0

record

row

4

0

3

1

2

2

col

-1

3

Result: 4

move_left

row

4

0

3

1

col

2

2

-1

3

Result: 4

compare

row

4

0

3

1

col

2

2

-1

3

Result: 4

move_down

3

0

row

2

1

col

1

2

-1

3

Result: 4

compare

3

0

row

2

1

col

1

2

-1

3

Result: 4

move_down

1

0

1

1

col

-1

2

-2

3

Result: 4

compare

1

0

1

1

col

-1

2

-2

3

Result: 4

record

1

0

1

1

col

-1

2

-2

3

Result: 6

move_left

1

0

col

1

1

row

-1

2

-2

3

Result: 6

compare

1

0

col

1

1

row

-1

2

-2

3

Result: 6

move_down

-1

0

col

-1

1

-2

2

row

-3

3

Result: 6

compare

-1

0

col

-1

1

-2

2

row

-3

3

Result: 6

record

-1

0

col

-1

1

-2

2

row

-3

3

Result: 7

move_left

col

-1

0

-1

1

-2

2

row

-3

3

Result: 7

compare

col

-1

0

-1

1

-2

2

row

-3

3

Result: 7

record

col

-1

0

-1

1

-2

2

row

-3

3

Result: 8

move_left

-1

0

-1

1

-2

2

row

-3

3

Result: 8

return

-1

0

-1

1

-2

2

row

-3

3

Result: 8

Key Takeaways

✓ Starting from the top-right corner allows the algorithm to efficiently skip entire columns of negative numbers.

This insight is hard to see from code alone because it relies on understanding the matrix's sorted property and how it enables bulk counting.

✓ When a negative number is found, all elements below in that column are also negative, so the algorithm adds them all at once to the count.

This bulk counting is the key optimization that reduces the time complexity from O(m*n) to O(m+n).

✓ Moving left when a negative is found and moving down when a non-negative is found ensures the algorithm covers the entire matrix without redundant checks.

The pointer movement pattern is a concrete example of a staircase search that leverages sorted rows and columns.

Practice

1. You are given a 9x9 grid partially filled with digits 1-9 and empty cells. You need to verify if the grid satisfies the constraints that each digit appears only once per row, column, and each of the nine 3x3 sub-boxes. Which algorithmic approach best guarantees an efficient and correct validation of this problem?

easy

A. Use a brute force approach checking each row, column, and box separately with nested loops and sets.

B. Use a single pass with hash sets to track digits seen in rows, columns, and boxes simultaneously.

C. Apply dynamic programming to store intermediate results of valid sub-grids and build up to the full grid.

D. Use a greedy approach by placing digits one by one and backtracking on conflicts.

Solution

1. Step 1: Understand problem constraints

   The problem requires checking uniqueness of digits in rows, columns, and 3x3 boxes simultaneously.

2. Step 2: Evaluate approaches

   Brute force (A) works but is less efficient and involves multiple passes. DP (C) is not applicable as this is a validation, not an optimization problem. Greedy with backtracking (D) is for solving Sudoku, not validating. Single pass with hash sets (B) efficiently tracks all constraints in one iteration.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Single pass with sets covers all constraints efficiently [OK]

Hint: Single pass with sets covers all constraints efficiently [OK]

Common Mistakes:

• Confusing validation with solving (greedy/backtracking)
• Thinking DP applies to validation
• Believing multiple passes are necessary

2. Consider this buggy code snippet for diagonal traversal. Which line contains the subtle bug that causes incorrect traversal or index errors?

def findDiagonalOrder(mat):
    if not mat or not mat[0]:
        return []
    m, n = len(mat), len(mat[0])
    result = []
    for d in range(m + n - 1):
        r_start = max(0, d - n + 1)
        r_end = min(d, m - 1)
        if d % 2 == 0:
            for r in range(r_start, r_end + 1):  # Bug here: direction wrong
                c = d - r
                result.append(mat[r][c])
        else:
            for r in range(r_end, r_start - 1, -1):
                c = d - r
                result.append(mat[r][c])
    return result

medium

A. Line with 'r_start = max(0, d - n + 1)'

B. Line with 'for r in range(r_start, r_end + 1):' inside even diagonal block

C. Line with 'c = d - r' inside loops

D. Line with 'for d in range(m + n - 1):'

Solution

1. Step 1: Identify traversal direction for even diagonals

   Even diagonals must traverse from r_end down to r_start (descending).

2. Step 2: Check loop direction in buggy code

   The loop uses ascending range from r_start to r_end, which is incorrect and causes wrong order or index errors.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Fixing loop direction restores correct traversal [OK]

Hint: Even diagonals traverse downward (descending indices) [OK]

Common Mistakes:

• Using ascending loop for even diagonals causing order errors

3. What is the time complexity of the sliding window approach for finding the maximum hourglass sum in an n x m matrix, and why?

medium

A. O(n^2 * m^2) because we check all 3x3 submatrices

B. O(n * m) because each hourglass sum is updated in constant time while sliding

C. O(n * m^2) because sliding window updates require scanning entire rows

D. O(n * m) but with O(n * m) extra space for prefix sums

Solution

1. Step 1: Identify loops in sliding window approach

   Outer loop runs (n-2) times, inner loop runs (m-2) times, total ~ O(n*m)

2. Step 2: Understand constant time updates

   Each hourglass sum update uses only 6 additions/subtractions, no full recomputation.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Sliding window avoids recomputing sums, achieving O(n*m) [OK]

Hint: Sliding window updates sums in O(1) per position [OK]

Common Mistakes:

• Confusing brute force O(n*m) with O(n^2*m^2)
• Assuming sliding window requires scanning entire rows
• Forgetting constant time update property

4. 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

5. Suppose you want to output the spiral order of a matrix but now the matrix can contain negative numbers and zero, and you want to skip all zeros during traversal. Which modification to the optimal boundary shrinking algorithm correctly handles this variant without revisiting elements or breaking order?

hard

A. Add a visited matrix to mark skipped zeros and continue traversal using direction vectors.

B. Modify the boundary shrinking algorithm to skip zeros during appending but still shrink boundaries normally.

C. Use a brute force nested loop with boundary checks and skip zeros when appending elements.

D. Traverse the matrix in spiral order but collect only non-zero elements, ignoring zeros without changing traversal.

Solution

1. Step 1: Understand the challenge of skipping zeros

   Skipping zeros means some elements are not appended, but traversal must still visit all cells exactly once without repeats.

2. Step 2: Why boundary shrinking alone fails

   Boundary shrinking assumes all elements are appended; skipping zeros breaks this assumption causing incorrect boundaries or missed elements.

3. Step 3: Using a visited matrix with direction vectors

   Tracking visited cells allows skipping zeros safely while continuing traversal correctly without revisiting or missing elements.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Visited matrix ensures correct traversal despite skipping zeros [OK]

Hint: Skipping elements breaks boundary assumptions; track visited cells [OK]

Common Mistakes:

• Skipping zeros but shrinking boundaries as usual causing missed elements
• Ignoring visited tracking leading to infinite loops or repeats
• Using brute force which is inefficient