Submatrices with given sum

Problem

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

Solution

Prerequisite Problem

Given an array and a traget, find the number of subarrays with sum equal to sum.

Solution

O(n^2) solution : Simply compare sum of all subarrays with target.

O(n) solution : Store the current overall sum in a variable, curr_sum. Also, store the count of previous cur_sum(s) in a map. At each index in the array, find the value curr_sum - target in the map. Add map[curr_sum - target] to the solution.