There is an O(n³) 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.