Quick Overview

This question evaluates proficiency in matrix manipulation, incremental updates, and complexity analysis, specifically maintaining main-diagonal and anti-diagonal sums under point updates.

Compute matrix trace and support updates

Company: Anthropic

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Given an n x n integer matrix M, implement a function trace (M) that returns the sum of its main diagonal. Follow-ups: (a) If you receive q point updates (i, j, val) changing M[i][j] to val, design a data structure to return the current trace after each update in O( 1) time; (b) Extend the function to also compute the anti-diagonal sum efficiently; (c) Discuss time and space complexities and edge cases (non-square input, large n).

Quick Answer: This question evaluates proficiency in matrix manipulation, incremental updates, and complexity analysis, specifically maintaining main-diagonal and anti-diagonal sums under point updates.

Part 1: Compute the main diagonal trace of a square matrix

Given an integer matrix `matrix`, return the sum of its main diagonal, from top-left to bottom-right. If the matrix is empty, return `0`. If the matrix is not square, return `None`.

Constraints

  • 0 <= n <= 2000, where n is the number of rows
  • -10^9 <= matrix[i][j] <= 10^9
  • If the matrix is non-empty, it should be square for a valid input

Examples

Input: ([[1, 2], [3, 4]],)

Expected Output: 5

Explanation: The main diagonal is 1 and 4, so the sum is 5.

Input: ([[7]],)

Expected Output: 7

Explanation: A 1x1 matrix has exactly one diagonal element.

Hints

  1. The main diagonal consists of entries where the row index equals the column index.
  2. Before summing, verify that every row has length `n`.

Part 2: Support O(1) trace queries after point updates

You are given an `n x n` integer matrix `matrix` and a list of point updates. Each update is a tuple `(i, j, val)` meaning `matrix[i][j]` becomes `val` using 0-based indexing. Return a list where the `k`-th value is the current main diagonal trace after applying the `k`-th update. Your solution should do O(1) work per update after initialization. If the initial matrix is not square, or any update index is out of bounds, return `None`.

Constraints

  • 0 <= n <= 2000
  • 0 <= q <= 200000, where q is the number of updates
  • -10^9 <= matrix[i][j], val <= 10^9
  • Updates use 0-based indices

Examples

Input: ([[1, 2], [3, 4]], [(0, 1, 10), (1, 1, 7), (0, 0, -1)])

Expected Output: [5, 8, 6]

Explanation: The first update is off-diagonal, so the trace stays 5. Then 4 becomes 7, making the trace 8. Finally 1 becomes -1, making the trace 6.

Input: ([[5]], [(0, 0, 3), (0, 0, 3)])

Expected Output: [3, 3]

Explanation: A 1x1 matrix's only cell is always on the main diagonal.

Hints

  1. Do not recompute the whole trace after each update. Store the current trace in a variable.
  2. Only updates with `i == j` change the trace, and the change is `val - old_value`.

Part 3: Maintain both main-diagonal and anti-diagonal sums under updates

You are given an `n x n` integer matrix `matrix` and a list of point updates. Each update is a tuple `(i, j, val)` meaning `matrix[i][j] = val` with 0-based indexing. After every update, return both the main diagonal sum and the anti-diagonal sum as a pair `(main_sum, anti_sum)`. Your solution should do O(1) work per update after initialization. If the initial matrix is not square, or any update index is out of bounds, return `None`. Note: in an odd-sized matrix, the center cell belongs to both diagonals.

Constraints

  • 0 <= n <= 2000
  • 0 <= q <= 200000
  • -10^9 <= matrix[i][j], val <= 10^9
  • Updates use 0-based indices
  • For anti-diagonal positions, `i + j == n - 1`

Examples

Input: ([[1, 2, 3], [4, 5, 6], [7, 8, 9]], [(0, 2, 10), (1, 1, 0), (2, 0, -1)])

Expected Output: [(15, 22), (10, 17), (10, 9)]

Explanation: The first update changes only the anti-diagonal. The second update hits the center, so it changes both sums. The third update changes only the anti-diagonal.

Input: ([[1, 2], [3, 4]], [(0, 0, 5), (0, 1, 7)])

Expected Output: [(9, 5), (9, 10)]

Explanation: In a 2x2 matrix, (0,0) is on the main diagonal only, while (0,1) is on the anti-diagonal only.

Hints

  1. Keep two running sums: one for the main diagonal and one for the anti-diagonal.
  2. When `n` is odd, the center cell satisfies both `i == j` and `i + j == n - 1`, so one update may affect both sums.

Loading coding console...