maximum sum subrectangle in a sparse matrix

Question

Finding the maximum sum subrectangle in an NxN matrix can be done in O(n^3) time using 2-d kadane's algorithm, as pointed out in other posts. However, if the matrix is sparse, specifically O(n) non-zero entries, can the O(n^3) time be beaten?

If it helps, for the current application I'm interested in, it would suffice to have a solution that assumes at most one non-zero value in each row and in each column of the matrix. However, in my future applications this assumption might not be appropriate (just sparsity will hold), and anyway my mathematical intuition is that there may be good solution(s) that simply exploit sparsity and don't further exploit the fact that the matrix is a product of a diagonal and a permutation matrix.

If there is at most non non-zero value in each row and in each column, then project those values onto the x-axis and y-axis, you will get two one-dimensional arrays each of size n. Find the maximum contiguous subarray of the two arrays. I think this will give you the maximum subrectangle. This can be done in O(n) time and O(n) space complexity. — Jason L
Unfortunately this proposed O(n) solution doesn't work, as the following counter-example shows: 1 0 0\\ 0 0 2\\ 0 -1 0\\ — user2566092

fuch fuch · Accepted Answer · 2013-07-11T13:57:18

Yes, it can be done better.

First of all, let's think about a data structure which allows us to

Update any single value of the underlying 1D array in O(logn) time
Find the sum of maximum subarray of the array in O(1) time

Actually, a balanced binary tree which looks like below can do the job. The tree structure can be described as:

Every leaf node of the tree represents every element of the array.
If an internal node covers range [a, b], its left child covers range [a, c] and its right child covers range [c + 1, b], where c = floor((a + b) / 2)).

The root node covers range [1, n].

                      O
                    /   \
                  /       \
                /           \
              /               \
            /                   \
          O                       O
        /   \                   /   \
       /     \                 /     \
      /       \               /       \
    O           O           O           O
   / \         / \         / \         / \
 o     o     o     o     o     o     o     o
A[1]  A[2]  A[3]  A[4]  A[5]  A[6]  A[7]  A[8]

There are 4 fields attached to every node v (including leaf nodes and internal nodes):

S[v]: the sum of all values in v's range
M[v]: the maximum subarray sum in v's range
L[v]: the sum of maximum subarray that starts at the left side of v's range
R[v]: the sum of maximum subarray that ends at the right side of v's range

Based on the above definitions, we may find the following updating rules:

For any leaf node v, S[v] = A[v], M[v] = L[v] = R[v] = max{0, A[v]}
For any internal node v and its children l and r,
- S[v] = S[l] + S[r]
- M[v] = max{M[l], M[r], R[l] + L[r]}
- L[v] = max{L[l], L[r] + S[l]}
- R[v] = max{R[r], R[l] + S[r]}

Finally, we can implement the operations mentioned in the beginning.

To update A[i], we may find the corresponding leaf node in the tree, and update the fields along its path to the root using the above rules.
The maximum subarray sum is simply M[root].

Now let's discuss how to find the maximum rectangle using this data structure. If we fix the upper row and the lower row of the rectangle to ith and jth rows, the problem turns to be the 1D maximum subarray sum problem, where A[k] = sum{B[i..j, k]}. The key insight is that, for a fixed i, if we enumerate j in ascending order, we can use the above data structure to maintain the underlying 1D array and find the answer very quickly. The pseudocode describes the idea:

result = 0
for i in (1, 2, ..., n)
    set all fields of the binary tree T to 0
    for j in (i, i + 1, ..., n)
        for any k where B[j, k] != 0
            T.update(k, A[k] + B[j, k])
        result = max{M[root], result}
return result

Suppose the matrix contains m non-zero elements, the time complexity of this algorithm is O(mn logn). In your case m = O(n), so the time complexity is O(n^2 logn) and is better than O(n^3).

maximum sum subrectangle in a sparse matrix

1 Answers