This problem requires identifying all submatrices within a matrix that sum to a specific target. The optimal approach leverages a 2D prefix sum combined with hash maps to track cumulative sums for each row pair. Iterating over row pairs while reducing the problem to a 1D prefix sum allows constant-time sum queries, minimizing time complexity compared to naive enumeration of all submatrices.
Problem Statement
Given a 2D integer matrix and a target value, return the total number of non-empty submatrices whose elements sum to exactly the target. A submatrix is defined by any rectangular region within the matrix, including all cells between two row indices and two column indices.
Two submatrices are considered different if any of their row or column boundaries differ. For example, if a submatrix spans rows x1 to x2 and columns y1 to y2, and another submatrix has at least one different boundary, they are counted separately.
Examples
Example 1
Input: matrix = [[0,1,0],[1,1,1],[0,1,0]], target = 0
Output: 4
The four 1x1 submatrices that only contain 0.
Example 2
Input: matrix = [[1,-1],[-1,1]], target = 0
Output: 5
The two 1x2 submatrices, plus the two 2x1 submatrices, plus the 2x2 submatrix.
Example 3
Input: matrix = [[904]], target = 0
Output: 0
Example details omitted.
Constraints
- 1 <= matrix.length <= 100
- 1 <= matrix[0].length <= 100
- -1000 <= matrix[i][j] <= 1000
- -10^8 <= target <= 10^8
Solution Approach
Use 2D Prefix Sums
Compute prefix sums for every row so that any submatrix sum can be calculated in constant time. This reduces repeated summation and is critical to efficiently handle large matrices.
Iterate Row Pairs and Reduce to 1D
For each pair of rows, calculate the column-wise sum between them to create a 1D array. The problem then reduces to finding subarrays within this array that sum to the target, enabling hash map usage for quick lookup.
Apply Hash Map for Prefix Sums
Maintain a running sum and a hash map to count the number of times each cumulative sum occurs. For each position, check if runningSum - target exists in the map to increment the total count efficiently.
Complexity Analysis
| Metric | Value |
|---|---|
| Time | Depends on the final approach |
| Space | Depends on the final approach |
Time complexity is O(rows^2 * cols) because each row pair iteration computes sums across columns with constant-time hash operations. Space complexity is O(cols) for the hash map per row pair, plus O(rows*cols) if using full 2D prefix sums.
What Interviewers Usually Probe
- Watch for the O(n^4) brute force attempt; hash map optimization is expected.
- They may ask about transforming 2D submatrix sums into a 1D prefix sum problem.
- Check if you recognize that cumulative sum differences allow constant-time subarray queries.
Common Pitfalls or Variants
Common pitfalls
- Not handling negative numbers in prefix sums correctly, leading to missing submatrices.
- Double-counting submatrices due to incorrect boundary handling.
- Attempting naive nested loops over all submatrices without reducing to row pairs and hash lookup.
Follow-up variants
- Count submatrices where the sum is less than or equal to a target instead of exact equality.
- Find the largest area submatrix with sum exactly equal to target.
- Return coordinates of all submatrices summing to target instead of just the count.
How GhostInterview Helps
- GhostInterview guides through the array scanning plus hash lookup pattern, providing incremental hints.
- It highlights the key step of converting 2D submatrix sum queries into 1D prefix sum checks.
- It alerts to common failure modes, like boundary mismanagement and negative numbers affecting cumulative sums.
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
FAQ
What is the main pattern used in Number of Submatrices That Sum to Target?
The pattern is array scanning combined with hash lookup, reducing 2D submatrix sum queries to 1D prefix sums for efficient counting.
Can negative numbers in the matrix affect the solution?
Yes, negative numbers require careful prefix sum handling since subarrays can sum to target even when elements are negative.
What is the time complexity for large matrices?
Using row pair iteration with hash maps, the time complexity is O(rows^2 * cols), which is much better than O(rows^2 * cols^2) brute force.
Do I need to store the full 2D prefix sum?
Storing full 2D prefix sums is optional; you can compute running column sums for row pairs to reduce space to O(cols).
How do I avoid double-counting submatrices?
Ensure each submatrix is defined by unique row and column boundaries, and carefully update the hash map only once per column iteration.
Need direct help with Number of Submatrices That Sum to Target instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Number of Submatrices That Sum to Target from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
The Longest Well-Performing Interval problem challenges you to find the longest subarray where tiring days exceed non-tiring ones.
Open problem page#1177 Can Make Palindrome from SubstringGiven a string and queries, determine if a substring can be rearranged and modified to form a palindrome.
Open problem page#959 Regions Cut By SlashesDetermine the number of regions in a grid divided by slashes using array scanning and union-find techniques efficiently.
Open problem page