hi_cf's blog

Find the largest size rectangle having all four borders as 1
By hi_cf, 11 years ago, In English

Given a 2D Boolean matrix consisting of 0s and 1s. Find the largest size rectangle having all four borders as 1. The interior of it may or may not be entirely filled with 1s . I can think of O(n^4) solution . How can we improve it ?

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
11 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Hi, do you have the source of the problem?

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Recently i attended amazon-india interview. They asked me this question .

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
      ← Rev. 2   Vote: I like it +3 Vote: I do not like it

      There is an O(n3) solution. First, calculate the partial sums for all rows: for column i this array is rowSum[i][]. Then we iterate over the rows, r. In array upperSide[i][j] we will store the highest row k such that from index i till j inclusive there are only 1's in row k, and in columns i and j from indices k till r inclusive are only 1's; or -1, if there is no such row. In each row iteration, r, we check for the pair of indices i, j, whether in this row from i to j inclusive there are only 1's (we do this in constant time with partial sums). If yes, then we check if upperSide[i][j] is not -1, and update the answer with this rectangle; if in this case upperSide[i][j] is -1, we update upperSide[i][j] with r. Last, if at positions i and j in this row r is at least one 0, we update upperSide[i][j] with -1.

      → Reply