Katkat
Back

Count Matrix Cells Whose Row and Column Neighbors Match

Hudson River TradingSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenSoftware Engineering Fundamentals

Last updated

This problem tests your ability to efficiently traverse a grid while implementing conditional neighborhood logic and handling boundary constraints.

Problem Statement

Given an m x n matrix of integers, a cell (i, j) is considered a "matching cell" if the value of the cell is equal to the sum of its immediate horizontal neighbors (left and right) AND equal to the sum of its immediate vertical neighbors (top and bottom).

Formally, for a cell at index (i, j), it is a matching cell if:

  1. matrix[i][j] == matrix[i][j-1] + matrix[i][j+1] (if both neighbors exist)
  2. matrix[i][j] == matrix[i-1][j] + matrix[i+1][j] (if both neighbors exist)

If a neighbor does not exist (e.g., at the boundary of the matrix), that specific neighbor is treated as having a value of 0 for the summation.

Write a function count_matching_cells(matrix) that returns the total count of such cells in the matrix.

Constraints

  • m, n are between 1 and 500.
  • Matrix elements are integers between -1000 and 1000.

Example 1

Input: [[1, 2, 1], [3, 0, 3], [1, 2, 1]]

  • Cell (1, 1): value is 0. Horizontal neighbors 3+3 = 6. Vertical neighbors 2+2 = 4. 0 != 6 and 0 != 4. Not a match.
  • Cell (0, 1): value 2. Horizontal neighbors 1+1 = 2. Vertical neighbors 0+0 = 0 (boundary). 2 == 2 but 2 != 0. Not a match.

Example 2

Input: [[0, 0, 0], [0, 0, 0], [0, 0, 0]]

  • Every cell is a match because 0 == 0+0 and 0 == 0+0.
  • Output: 9
def count_matching_cells(matrix: list[list[int]]) -> int:
    # Implementation here

Hints

Hint 1

Handle boundary conditions by using a helper function that returns 0 if the requested coordinates are out of the matrix bounds.

Hint 2

Instead of complex if-else logic, represent the missing neighbors as 0 to simplify your summation expressions.

Hint 3

The time complexity should be O(m * n) since you need to visit every cell exactly once.

Follow-up questions

  • How would your logic change if we only considered cells that have all four neighbors present (i.e., non-boundary cells)?
  • How can you optimize the space complexity if the matrix is too large to fit in memory and must be processed in chunks?
  • If the matrix values were updated dynamically, what data structure would help you keep track of the matching cell count efficiently?