Submatrix with sum K Given an N*M matrix of only 0's and 1's I need to find a submatrix in this 2d array whose area is minimum and which contain exactly K 1's or we can say whose sum is K.If their is no such matrix possible then return -1.If it is possible i need to tell the minimum area of the subarray.
EXAMPLE : Let say we have $5\times6$ matrix and $K=4$.
$$\begin{matrix}
0 & 0 & 0 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 & 0 & 0  \\
0 & 0 & 1 & 1 & 0 & 0   \\
0 & 0 & 0 & 1 & 1 & 0    \\
0 & 0 & 0 & 0 & 0 & 0     \\
\end{matrix}$$
Then clearly here minimum area is $6$.
 A: The trivial solution to this problem, which involves brute-forcing the sum of every possible submatrix is O(n^6), which consists of O(n^4) for iterating over all possible submatrices and another O(n^2) for computing the sum of each submatrix.
A simple improvement over the trivial solution that runs in O(n^4) is as follows.
A summed area  table of matrix $A$ is defined by:
$$I(x,y) = \sum_{\begin{smallmatrix} x' \le x \\ y' \le y\end{smallmatrix}} A(x',y') $$
$I$ can be computing by performing a cumulative sum first over the rows and then over the columns of $A$, or vice versa. This requires O(n^2) time.
The sum of a submatrix of $A$ defined by the 4 corners A,B,C and D can be computed in O(1) using the formula: $$\sum_{\begin{smallmatrix} x0 \le x \le x1 \\ y0 \le y \le y1 \end{smallmatrix}} i(x,y) = I(C) + I(A) - I(B) - I(D)$$
We still need to iterate over all possible submatrices, so the runtime of this algorithm is O(n^4).
It's likely that a O(n^2) solution exists. Kadane's algorithm would be a good place to start figuring it out.
