Matrix Stream Evaluator — Problem Statement & Solution Guide
Quick Answer & Algorithm Key Takeaway
Conditional sum using a running accumulator
O(n * m)O(1)Problem Description
Given a rectangular integer matrix grid and an integer K, return the sum of all values strictly greater than K. Visit each cell independently; adjacency and connectivity do not affect whether a value is included. Return 0 if no value qualifies. Do not modify the matrix.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Matrix Stream Evaluator"
WHY DOES IT MATTER?
A conditional sum combines filtering and aggregation in one pass.
OPTIMIZATION CHALLENGE
Accumulate qualifying values directly to avoid allocating a filtered list.
REAL-WORLD CONNECTION
Add measurements that exceed a chosen threshold without copying them into another collection.
Use strict greater-than, include qualifying negative numbers, and choose a sum type wide enough for the constraints.
COMPLEXITY AT A GLANCE
O(n * m)O(1)Core Theory — Why This Approach?
The inclusion rule depends only on each value and K. Maintain the invariant that total is the sum of all qualifying values already visited. Initially no values have been visited, so total is 0. Adding a value exactly when it exceeds K preserves the invariant. After the last value, total is the required sum. Every value may affect the result, so a single query on arbitrary input requires examining all n * m values in the worst case. One running sum uses constant auxiliary space. The largest possible sum is 250000000000000, which requires a 64-bit integer in C++ and Java and is exactly representable by JavaScript Number. Python integers support this range.
Interview Questions on This Problem
Q1What happens when a value equals K?
It is excluded because the comparison is strictly greater than K.
Q2Can the result be negative?
Yes. With a negative threshold, qualifying negative values can produce a negative sum.
Q3Why use a 64-bit sum in C++ and Java?
Individual values fit in 32 bits, but their combined sum can exceed the signed 32-bit range.
Examples
Input
grid = [[5, 6, 7], [8, 9, 10], [11, 12, 13]], K = 4
Output
81
Explanation: Every value exceeds 4. The row sums are 18, 27 and 36, giving 81.
Input
grid = [[5, 6, 7], [8, 3, 10], [11, 12, 13]], K = 4
Output
72
Explanation: Exclude only 3. The qualifying values sum to 72; a smaller neighbor does not exclude other cells.
Input
grid = [[5, 0, 7], [8, 0, 10], [11, 0, 13]], K = 4
Output
54
Explanation: Exclude the zeros and sum 5 + 7 + 8 + 10 + 11 + 13 = 54.
Input
grid = [[1, 2], [3, 4]], K = 2
Output
7
Explanation: Only 3 and 4 exceed 2, so return 7.
Input
grid = [[-5, -1], [0, 5]], K = -2
Output
4
Explanation: The qualifying values are -1, 0 and 5, totaling 4.
Constraints
- 1 <= n, m <= 500
- -10^9 <= grid[i][j] <= 10^9
- -10^9 <= K <= 10^9
- The total number of elements n*m <= 250000
Optimal Approach & Strategy
Initialize total to 0. Visit each row and each value in that row; add the value only when it is strictly greater than K. After each visit, total equals the sum of qualifying values seen so far. Return total after the scan. This takes O(n * m) time and O(1) auxiliary space without modifying the input. Use a 64-bit integer for the sum in C++ and Java.
Brute Force Approach
Collect all values greater than K in a temporary list, then sum that list. This takes O(n * m) time and up to O(n * m) extra space. Sorting or checking combinations is unnecessary.
Step-by-Step Dry Run
For grid = [[1, 2], [3, 4]] and K = 2: start total = 0. Skip 1 and 2 because neither exceeds 2. Add 3 to get total = 3, then add 4 to get total = 7. Return 7.
Code Solutions
function solution(grid, K) {
let total = 0;
for (const row of grid) {
for (const value of row) {
if (value > K) total += value;
}
}
return total;
}
// Input driver: length/dimensions, values, then K when applicable.
if (require.main === module) {
const input = require("fs").readFileSync(0, "utf8").trim();
if (input) {
const tokens = input.split(/\s+/).map(Number); let pos = 0;
const n = tokens[pos++], m = tokens[pos++];
const grid = Array.from({ length: n }, () => Array.from({ length: m }, () => tokens[pos++]));
const K = tokens[pos++];
console.log(solution(grid, K));
}
}#include <iostream>
#include <vector>
class Solution {
public:
long long solution(const std::vector<std::vector<int>>& grid, int K) {
long long total = 0;
for (const auto& row : grid) {
for (int value : row) {
if (value > K) total += value;
}
}
return total;
}
};
// Input driver: length/dimensions, values, then K when applicable.
int main() {
int n, m; if (!(std::cin >> n >> m)) return 0;
std::vector<std::vector<int>> grid(n, std::vector<int>(m));
for (auto& row : grid) for (int& value : row) std::cin >> value;
int K; std::cin >> K;
std::cout << Solution().solution(grid, K) << "\n";
}
class Solution {
public long solution(int[][] grid, int K) {
long total = 0L;
for (int[] row : grid) {
for (int value : row) {
if (value > K) total += value;
}
}
return total;
}
}
// Input driver: length/dimensions, values, then K when applicable.
public class Main {
public static void main(String[] args) {
java.util.Scanner in = new java.util.Scanner(System.in);
if (!in.hasNextInt()) return;
int n = in.nextInt(), m = in.nextInt();
int[][] grid = new int[n][m];
for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) grid[i][j] = in.nextInt();
int K = in.nextInt();
System.out.println(new Solution().solution(grid, K));
}
}
def solution(grid, K):
total = 0
for row in grid:
for value in row:
if value > K:
total += value
return total
# Input driver: length/dimensions, values, then K when applicable.
if __name__ == "__main__":
import sys
tokens = iter(map(int, sys.stdin.buffer.read().split()))
n = next(tokens)
m = next(tokens)
grid = [[next(tokens) for _ in range(m)] for _ in range(n)]
K = next(tokens)
print(solution(grid, K))
function solution(grid, K) {
let total = 0;
for (const row of grid) {
for (const value of row) {
if (value > K) total += value;
}
}
return total;
}
// Input driver: length/dimensions, values, then K when applicable.
if (require.main === module) {
const input = require("fs").readFileSync(0, "utf8").trim();
if (input) {
const tokens = input.split(/\s+/).map(Number); let pos = 0;
const n = tokens[pos++], m = tokens[pos++];
const grid = Array.from({ length: n }, () => Array.from({ length: m }, () => tokens[pos++]));
const K = tokens[pos++];
console.log(solution(grid, K));
}
}
Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.