Summed Matrix

JavaView on GFG

Time: O(1)

Space: O(1)

Intuition

Find value at (i,j) in infinite matrix where matrix[i][j] = i+j. Count frequency of target value.

Algorithm

1Value k appears at positions where i+j=k, for i,j in [1,n]. Count valid (i,j) pairs.

Common Pitfalls

•For value k in n*n matrix: i+j=k, 1<=i,j<=n. Count pairs: max(0, min(k-1,n) - max(1,k-n) + 1).

Summed Matrix.java

Java

// Approach: Mathematical observation: cell (i,j) value is a function of (i+j). Derive count formula.
// Time: O(1) Space: O(1)
class Solution {
    static long sumMatrix(long n, long q) {
        if (q < 2 || q > 2 * n)
            return 0;
        else if (q <= n + 1)
            return q - 1;
        else
            return 2 * n - (q - 1);
    }
}

Was this solution helpful?