Блог пользователя hi_cf

Автор hi_cf, 11 лет назад, По-английски

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 ?

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
11 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Hi, do you have the source of the problem?

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      11 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

      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.