[MEDIUM] #1075 - Project Employees I

[hackdartstorm]

🎯 Problem: Number of Submatrices That Sum to Target

📖 The Real Problem

You are given:

1. A 2D matrix of integers
2. A target sum value

Your task: Count how many submatrices (rectangular regions) in the matrix have a sum equal to the target.

What is a submatrix?

• Any rectangular region within the matrix
• Defined by its top-left and bottom-right corners
• Can be 1x1 (single cell), 1xn (row segment), nx1 (column segment), or nxm (full rectangle)

The Challenge:

• Brute force checks all possible submatrices: O(n²m²)
• Need to optimize using prefix sums and hash maps
• Handle negative numbers correctly
• Count ALL submatrices that sum to target (not just find one)

Why this problem exists:

• Tests understanding of 2D prefix sums
• Combines multiple algorithmic techniques
• Real-world pattern matching in images/data

💡 Why This Matters

Real-world applications:

• Image Processing - Finding regions with specific properties
• Financial Analysis - Finding time periods with target returns
• Heat Map Analysis - Identifying hot/cold zones in data
• Game Development - Collision detection, region queries

Skills you'll develop:

• ✅ 2D prefix sum calculation
• ✅ Hash map for subarray sum counting
• ✅ Optimization from O(n⁴) to O(n³)
• ✅ Multi-dimensional problem solving
• ✅ Sliding window in 2D

📋 Contributor Tasks

Step 1: Understand the Problem

1. Draw a small matrix (3x3) on paper
2. Identify all possible submatrices manually
3. Calculate sum for each submatrix
4. Count how many equal the target

Step 2: Plan Your Approach

Approach 1: Brute Force (Understand first)

1. Iterate all possible top-left corners (r1, c1)
2. Iterate all possible bottom-right corners (r2, c2)
3. Calculate sum for each submatrix
4. Count matches

Approach 2: Optimized with Prefix Sum (Implement this)

1. Precompute 2D prefix sums
2. For each pair of rows, treat as 1D problem
3. Use hash map to count subarrays with target sum
4. Sum up all counts

Step 3: Implement the Solution

1. Build 2D prefix sum matrix
2. For each pair of rows (r1, r2):
   • Create 1D array of column sums between these rows
   • Use subarray sum equals K technique
   • Count valid submatrices
3. Return total count

Step 4: Test Your Solution

1. Test with 1x1 matrix
2. Test with all zeros
3. Test with target = 0
4. Test with negative numbers
5. Test with no matching submatrices

✅ Expected Outcome

Function Signature:

def numSubmatrixSumTarget(matrix, target):
    """
    Count submatrices whose sum equals target.
    
    Args:
        matrix: List[List[int]] - 2D matrix of integers
        target: int - target sum
    
    Returns:
        int: count of submatrices with sum = target
    
    Example:
        >>> matrix = [[0,1,0],[1,1,1],[0,1,0]]
        >>> numSubmatrixSumTarget(matrix, 0)
        4
    """

Expected Behavior:

• ✅ Counts ALL submatrices with sum = target
• ✅ Handles negative numbers
• ✅ Handles target = 0
• ✅ Works with any rectangular matrix
• ✅ Returns 0 if no submatrices match

Example Test Cases:

# Test 1: Basic example
matrix = [
    [0, 1, 0],
    [1, 1, 1],
    [0, 1, 0]
]
numSubmatrixSumTarget(matrix, 0)  # Returns: 4
# The four 0 cells are the only submatrices summing to 0

# Test 2: All ones
matrix = [
    [1, 1, 1],
    [1, 1, 1]
]
numSubmatrixSumTarget(matrix, 3)  # Returns: 4
# Four 1x3 or 3x1 submatrices sum to 3

# Test 3: Single cell
matrix = [[5]]
numSubmatrixSumTarget(matrix, 5)  # Returns: 1
numSubmatrixSumTarget(matrix, 3)  # Returns: 0

# Test 4: With negative numbers
matrix = [
    [1, -1],
    [-1, 1]
]
numSubmatrixSumTarget(matrix, 0)  # Returns: 5
# Four 1x1 cells with 0 sum + entire 2x2 matrix

📚 Additional Context & References

Understanding the Problem

Key Insight:
This is a 2D extension of "Subarray Sum Equals K". If you can solve the 1D version, you can extend it to 2D.

1D Problem (Prerequisite):

def subarraySum(nums, k):
    count = 0
    sum_so_far = 0
    prefix_sum_count = {0: 1}
    
    for num in nums:
        sum_so_far += num
        if (sum_so_far - k) in prefix_sum_count:
            count += prefix_sum_count[sum_so_far - k]
        prefix_sum_count[sum_so_far] = prefix_sum_count.get(sum_so_far, 0) + 1
    
    return count

Solution Approach

Optimized Solution O(rows² × cols):

def numSubmatrixSumTarget(matrix, target):
    rows, cols = len(matrix), len(matrix[0])
    
    # Precompute prefix sums for each row
    for r in range(rows):
        for c in range(1, cols):
            matrix[r][c] += matrix[r][c-1]
    
    count = 0
    
    # For each pair of columns
    for c1 in range(cols):
        for c2 in range(c1, cols):
            # Use 1D subarray sum technique
            prefix_sum_count = {0: 1}
            sum_so_far = 0
            
            for r in range(rows):
                # Calculate sum between columns c1 and c2 for row r
                row_sum = matrix[r][c2] - (matrix[r][c1-1] if c1 > 0 else 0)
                sum_so_far += row_sum
                
                if (sum_so_far - target) in prefix_sum_count:
                    count += prefix_sum_count[sum_so_far - target]
                
                prefix_sum_count[sum_so_far] = prefix_sum_count.get(sum_so_far, 0) + 1
    
    return count

Hints (Use Only If Stuck!)

💡 Hint 1

Can you reduce the 2D problem to multiple 1D problems?

💡 Hint 2

For each pair of columns, treat the rows between them as a 1D array.

💡 Hint 3

Use prefix sums and a hash map, similar to the 1D "subarray sum equals K" problem.

Complexity Analysis

Time Complexity: O(rows² × cols) or O(rows × cols²)

• Prefix sum computation: O(rows × cols)
• For each pair of columns: O(cols²)
• For each pair, scan all rows: O(rows)
• Hash map operations: O(1) average
• Total: O(rows × cols²)

Space Complexity: O(rows × cols)

• Prefix sum matrix: O(rows × cols)
• Hash map: O(rows) in worst case

Related Problems

Once you solve this, try:

• Subarray Sum Equals K - 1D version
• Maximum Size Subarray Sum Equals K - Variation
• Max Sum of Rectangle No Larger Than K - Harder version
• Count Submatrices With All Ones - Different condition

Helpful Resources

• Prefix Sum Array
• Subarray Sum Equals K
• 2D Prefix Sum
• LeetCode 1074 - Number of Submatrices That Sum to Target

📝 Notes

• Matrix dimensions: 1 to 100 (both rows and cols)
• Element values: -1000 to 1000
• Target value: -10^8 to 10^8
• Submatrices can be any size (1x1 to rows×cols)
• Count ALL submatrices, not just find one
• Overlapping submatrices count separately

---

Ready to contribute?

1. Fork the repository
2. Create your solution file
3. Test with provided examples
4. Submit a pull request!

File Location: exercises/1000_programs/medium/1074_submatrices_sum_target.py

🚀 Happy coding!