Number of Submatrices That Sum to Target - Practice Coding Problems

Number of Submatrices That Sum to Target - Problem

Given a matrix and a target, return the number of non-empty submatrices that sum to target.

A submatrix x1, y1, x2, y2 is the set of all cells matrix[x][y] with x1 <= x <= x2 and y1 <= y <= y2.

Two submatrices (x1, y1, x2, y2) and (x1', y1', x2', y2') are different if they have some coordinate that is different: for example, if x1 != x1'.

Input & Output

Example 1 — Basic 2x2 Matrix

$ Input: matrix = [[0,1],[0,1]], target = 1

› Output: 4

💡 Note: Four submatrices sum to 1: [0,1] (top-right cell), [0,1] (bottom-right cell), [[1],[1]] (right column), and [1] (each individual 1)

Example 2 — Larger Matrix

$ Input: matrix = [[1,-1],[-1,1]], target = 0

› Output: 5

💡 Note: Five submatrices sum to 0: four 2x1 rectangles ([1,-1], [-1,1], [1],[-1]], [[1],[-1]]) and the entire 2x2 matrix

Example 3 — Single Element

$ Input: matrix = [[904]], target = 0

› Output: 0

💡 Note: Only one submatrix exists (the single cell with value 904), but it doesn't sum to 0

Constraints

1 ≤ matrix.length ≤ 100
1 ≤ matrix[i].length ≤ 100
-1000 ≤ matrix[i][j] ≤ 1000
-10⁸ ≤ target ≤ 10⁸

Visualization

Tap to expand

Understanding the Visualization

Input Matrix

2D matrix with target sum to find

Find Submatrices

Enumerate all possible rectangles

Count Matches

Count how many sum to target

Key Takeaway

🎯 Key Insight: Convert 2D matrix problem to multiple 1D array problems using prefix sums

Asked in

G Google 8 a Amazon 5 f Facebook 4

The key insight is converting the 2D submatrix sum problem into multiple 1D subarray sum problems. Build a 2D prefix sum array, then for each pair of rows, create a 1D array of column sums and use hash map technique to count subarrays with target sum. Best approach uses prefix sums with hash map. Time: O(m²n), Space: O(mn)

Common Approaches

Approach	Time	Space	Notes
✓ Prefix Sum with Hash Map	O(m²n)	O(mn)	Use 2D prefix sums and reduce to 1D subarray sum problem
Brute Force	O(m²n²)	O(1)	Check every possible submatrix and calculate its sum

Prefix Sum with Hash Map — Algorithm Steps

Build 2D prefix sum array for fast range sum queries
For each pair of rows (top, bottom), create 1D array of column sums
Use hash map to count subarrays in 1D array that sum to target
Accumulate counts from all row pairs

Visualization

Tap to expand

Step-by-Step Walkthrough

Build Prefix Sums

Create 2D prefix sum array

Fix Row Range

Choose top and bottom rows

Column Sums

Create 1D array of column totals

Hash Map Count

Count subarrays with target sum

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// Simple hash map for demonstration
#define HASH_SIZE 10007

struct HashNode {
    int key;
    int value;
    struct HashNode* next;
};

struct HashNode* hashTable[HASH_SIZE];

int hashFunction(int key) {
    return ((key % HASH_SIZE) + HASH_SIZE) % HASH_SIZE;
}

void insertOrUpdate(int key, int value) {
    int index = hashFunction(key);
    struct HashNode* node = hashTable[index];
    
    while (node) {
        if (node->key == key) {
            node->value += value;
            return;
        }
        node = node->next;
    }
    
    struct HashNode* newNode = (struct HashNode*)malloc(sizeof(struct HashNode));
    newNode->key = key;
    newNode->value = value;
    newNode->next = hashTable[index];
    hashTable[index] = newNode;
}

int getValue(int key) {
    int index = hashFunction(key);
    struct HashNode* node = hashTable[index];
    
    while (node) {
        if (node->key == key) {
            return node->value;
        }
        node = node->next;
    }
    return 0;
}

void clearHash() {
    for (int i = 0; i < HASH_SIZE; i++) {
        struct HashNode* node = hashTable[i];
        while (node) {
            struct HashNode* temp = node;
            node = node->next;
            free(temp);
        }
        hashTable[i] = NULL;
    }
}

int solution(int** matrix, int matrixSize, int* matrixColSize, int target) {
    if (matrixSize == 0 || matrixColSize[0] == 0) return 0;
    
    int m = matrixSize, n = matrixColSize[0];
    
    // Build prefix sum array
    int** prefix = (int**)malloc((m + 1) * sizeof(int*));
    for (int i = 0; i <= m; i++) {
        prefix[i] = (int*)calloc(n + 1, sizeof(int));
    }
    
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            prefix[i][j] = matrix[i-1][j-1] + prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1];
        }
    }
    
    int count = 0;
    // Try all pairs of rows
    for (int top = 0; top < m; top++) {
        for (int bottom = top; bottom < m; bottom++) {
            clearHash();
            
            // Create 1D array of column sums between these rows
            int prefixSum = 0;
            insertOrUpdate(0, 1);
            
            for (int j = 0; j < n; j++) {
                int colSum = prefix[bottom + 1][j + 1] - prefix[top][j + 1];
                prefixSum += colSum;
                count += getValue(prefixSum - target);
                insertOrUpdate(prefixSum, 1);
            }
        }
    }
    
    // Clean up
    for (int i = 0; i <= m; i++) {
        free(prefix[i]);
    }
    free(prefix);
    clearHash();
    
    return count;
}

int main() {
    // Demo with simple 2x2 matrix
    int matrix[2][2] = {{0, 1}, {0, 1}};
    int* matrixPtrs[2] = {matrix[0], matrix[1]};
    int matrixColSize[2] = {2, 2};
    int target = 1;
    
    int result = solution(matrixPtrs, 2, matrixColSize, target);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(m²n)

O(m²) pairs of rows, each processes O(n) columns with hash map lookups

✓ Linear Growth

Space Complexity

O(mn)

2D prefix sum array of size m×n plus hash map storage

⚡ Linearithmic Space

28.0K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Prefix Sum with Hash Map — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler