Can this Problem be solved in DP?


  • 0
    S

    I know if we need to find maximum square, it can be solved with DP. Can this Problem be solved in DP?
    Please check out this: http://www.geeksforgeeks.org/maximum-size-sub-matrix-with-all-1s-in-a-binary-matrix/


  • 0
    E

    My DP solution for your reference. It definitely can be simplified, but it should be clear and easy to follow.

    The main idea is:
    Keep a list of lists, in which each element is the index of the left most element of contiguous '1's in the same row if this index greater than the left most index of the '1' in the contiguous '1's of the current position and current scanning line, otherwise this element is the index of the first '1' in in the contiguous '1's of the contiguous '1's of the current position and current scanning line.

    One example is :

    1 1 0 0 1 1 1 0

    0 0 1 1 1 1 1 1

    1 0 0 1 1 1 1 0

    When you scan the first line, the list looks like:

    storage = [[0], [0], [], [], [4], [4], [4], []]

    When you scan the second line, the list looks like:

    storage = [[], [], [2], [2], [4,2], [4,2], [4,2], [2]]

    When you scan the third line, the list looks like:

    storage = [[0], [], [], [3,3], [4,3,3], [4,3,3], [4,3,3], []]

    In the list of 'storage', no element is smaller than the last added element. And if a position in the scanning row is '0', then empty the list of that position in the 'storage'

    Use this list to calculate the maximum rectangular area:

    For each position in a row, you need to iterate through the list and calculate the maximum area by:

    max_area = max(max_area, (len(storage[X]) - idx)*(X + 1 - storage[X][idx]))

    Where the 'idx' is the iterator of the list of the current position starts from 0.

    The time complexity of my method is O(n^2), where n is the total number of all the elements in the matrix.

    class Solution:
        # @param matrix, a list of lists of 1 length string
        # @return an integer
        def maximalRectangle(self, matrix):
            if len(matrix) == 0 or len(matrix[0]) == 0:
                return 0
            storage = []
            max_area = 0
            for idx, each in enumerate(matrix[0]):
                if idx == 0:
                    if each == '1':
                        storage.append([0])
                        max_area = 1
                    else:
                        storage.append([])
                else:
                    if each == '1':
                        if storage[idx-1] == []:
                            storage.append([idx])
                            max_area = max(max_area, 1)
                        else:
                            storage.append([storage[idx-1][-1]])
                            max_area = max(max_area, (idx + 1 - storage[idx][-1]))
                    else:
                        storage.append([])
            for Y in xrange(1, len(matrix)):
                for X in xrange(len(matrix[0])):
                    if X == 0:
                        if matrix[Y][X] == '1':
                            max_area = max(max_area, len(storage[0])+1)
                            storage[0].append(0)
                        else:
                            storage[0] = []
                    else:
                        if matrix[Y][X] == '1':
                            if storage[X-1] == []:
                                max_area = max(max_area, len(storage[X])+1)
                                for idx in xrange(len(storage[X])):
                                    if storage[X][idx] < X:
                                        storage[X][idx] = X
                                storage[X].append(X)
                            else:
                                for idx in xrange(len(storage[X])):
                                    if storage[X][idx] < storage[X-1][-1]:
                                        storage[X][idx] = storage[X-1][-1]
                                        max_area = max(max_area, (len(storage[X]) + 1 - idx)*(X + 1 - storage[X-1][-1]))
                                    else:
                                        max_area = max(max_area, (len(storage[X]) + 1 - idx)*(X + 1 - storage[X][idx]))
                                max_area = max(max_area, X + 1 - storage[X-1][-1])
                                storage[X].append(storage[X-1][-1])
                        else:
                            storage[X] = []
            return max_area

  • 0
    V

    I'm not sure if this is O(n^2) - you have 3 nested loops there


  • 0
    E

    'N' by definition is the total number of the elements in the matrix, the first two for-loops iterate through the n elements once.


  • 0
    V

    ok, but what's the upper bound for len(storage[X])) in the loop

    for idx in xrange(len(storage[X])):


  • 1
    V

    I initially approached this problem with a DP solution, similar to the one described at the link you provided.

    Let w(i,j) be the width of max rectangle for the cell (i,j), h(i,j) be the height.
    Let left(i,j) be the number of contigious series of 1 to the left of (i, j) cell, including the cell itself
    Let top(i, j) be the number of contigious series of 1 on top of (i,j) cell, including the cell itself.

    I was thinking that the problem exhibits optimal substructure in the following way: the maximal rectangle for (i, j) will always be one of the following:

    1. an extension of a maximal rectangle for (i-1, j) so that: h(i,j) = h(i-1, j) +1, w(i, j) = min(left(i, j), w(i-1, j))

    2. an extension of a maximal rectangle for (i, j-1) so that h(i, j) = min(h(i, j-1), top(i, j)), w(i, j) = w(i, j-1) + 1

    3. an extension of a maximal rectangle for (i-1, j-1), with a similar idea - extend the rectangle as much as we can in both directions.

    4. a horizontal line, h(i, j) = 1, w(i, j) = left(i, j)

    5. a vertical line, w(i, j) = 1, h(i, j) = top(i, j)

    My O(m*n) solution, where m, n are the dimentsions of the matrix, passed the OJ, BUT when I tried to prove its correctness, I found a counterexample.

    It is a histogram with the following bar heights (see the histogram problem):
    [3, 3, 3, 3, 3, 3, 3, 3, 8, 8, 8, 30, 19]. If you draw this, you'll see that the maximum rectangle for the down right corner does not fall into any of the categories described in 1-5.


  • 0
    H

    nice counter-example!!! thanks a lot... I have been troubled for a really long time.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.