Count all possible contiguous sub matices with exactly K 1's - Binary Matrix

Asked Nov 09 '16 at 16:14

Active Nov 09 '16 at 16:20

Viewed 187 times

The problem:

Given a NxN 0-1 matrix and a number K, count all sub matrices (any size) with exactly K 1's.

Constrains: 2 <= N <= 600, 1<= K <= 6

Example

1 0 1
0 0 0
1 0 1

Count: 8

With memoization of the sums of all possible sub matrices my algorithm has complexity O(n^4). I tried to combine various solutions for different but similar problems with no luck. I can't think a better way to reduce the time complexity. Could be done in O(n^3)?

I have read the following:

Kadane's algorithm

Submatrix with maximum sum

Minimum area submatrix with sum K

Minimal subrectangle with at least K 1's

This is a homework.

edited Nov 09 '16 at 16:20

asked Nov 09 '16 at 16:14

Laxmana

1,606
2
21
40

I am searching 5 days and I just find a duplicate in related section: https://stackoverflow.com/questions/40321927/how-to-check-sums-of-all-possible-rectangles-of-array Should I delete the post? – Laxmana Nov 10 '16 at 09:50

Count all possible contiguous sub matices with exactly K 1's - Binary Matrix

0 Answers0