Matrix Region and Ring Sums
NVIDIA● MediumNEW GRADPHONE SCREENProblem statement
Given an immutable integer matrix and a batch of region queries, return one sum for each query.
Each query is [type, row1, col1, row2, col2], with inclusive corners and row1 <= row2, col1 <= col2.
type = 0: return the sum of every cell in the rectangle.type = 1: return the sum of the one-cell-thick border, or ring, of the rectangle. Count each corner once. If the rectangle is one row or one column, every cell in it belongs to the ring.
For the ring follow-up, accumulate border cells directly without computing an outer sum minus an inner sum. The matrix does not change between queries. Preprocess it so every type-0 rectangle query takes constant time.
Function
regionAndRingSums(matrix: int[][], queries: int[][]) → int[]Examples
Example 1
matrix = [[1,2,3],[4,5,6],[7,8,9]]queries = [[0,0,0,2,2],[1,0,0,2,2],[1,1,1,1,1]]return = [45,40,5]The full rectangle sums to 45. Its border omits only the center value 5, so it sums to 40; a one-cell ring contains that cell.
Example 2
matrix = [[-2,4,1],[3,-5,6]]queries = [[0,0,1,1,2],[1,0,0,1,2]]return = [6,7]The right two columns sum to 6. A two-row rectangle has no interior, so its ring includes all six values and sums to 7.
Example 3
matrix = [[1,-1,2,4]]queries = [[1,0,1,0,2],[0,0,0,0,3]]return = [1,6]The one-row ring uses -1 and 2. The full row sums to 6.
Constraints
1 <= matrix.length, matrix[0].length <= 200-10000 <= matrix[r][c] <= 100000 <= queries.length <= 10000- Every query has five integers,
typeis0or1, and its inclusive corners are within the matrix.