Find a maximal rectangle of 1s

Question

Background

I want to buy an plot of land and build my house on it. My house should be rectangular, and as large as possible; however, the available plots have lots of rocky areas that I cannot build on, and I'm having trouble fitting a potential house on the plots. I want you to write a program that analyzes the plots for me.

Input and output

Your input is a rectangular 2D array of bits, of size at least 1×1, in any reasonable format. The array represents a plot of land; 1s are "good" areas where I could build my house, and 0s are "rocky" areas where the house cannot be built.

Your output shall be the maximal area of a solid rectangle of 1s in the input array. It represents the area of the largest house I could build on the plot. Note that if there are no 1s in the input, then the output is 0.

Example

Consider the input

101
011
111

The largest rectangle of 1s is the 2×2 rectangle in the lower right corner. This means that the correct output is 4.

Rules and scoring

You can write a full program or a function. The lowest byte count wins, and standard loopholes are disallowed.

Test cases

0
-> 0

1
-> 1

00
00
-> 0

01
10
-> 1

01
11
-> 2

111
010
111
-> 3

101
011
111
-> 4

0111
1110
1100
-> 4

1111111
1110111
1011101
-> 7

111011000
110111100
001111110
011111111
001111110
000111100
000011000
-> 20

000110000
110110010
110111110
110011100
010011111
111111111
111101110
-> 12

Answer 1

Jelly, 21 20 18 17 bytes

ṡṂ€€×"
‘×¥\ç"Ụ€FṀ

Try it online! or verify all test cases.

Background

Let M be a matrix of bits such as

0 0 0 1 1 0 0 0 0
1 1 0 1 1 0 0 1 0
1 1 0 1 1 1 1 1 0
1 1 0 0 1 1 1 0 0
0 1 0 0 1 1 1 1 1
1 1 1 1 1 1 1 1 1
1 1 1 1 0 1 1 1 0

We start by counting the number of 1 bits in each column of M, resetting the count every time we encounter a 0 bit.

For our example matrix, this gives

0 0 0 1 1 0 0 0 0
1 1 0 2 2 0 0 1 0
2 2 0 3 3 1 1 2 0
3 3 0 0 4 2 2 0 0
0 4 0 0 5 3 3 1 1
1 5 1 1 6 4 4 2 2
2 6 2 2 0 5 5 3 0

Next, we compute all contiguous sublists of each row. We achieve this by generating all slices of length k, where k varies between 1 and the number of entries in each row.

For the penultimate row, this gives

[1], [5], [1], [1], [6], [4], [4], [2], [2]
[1, 5], [5, 1], [1, 1], [1, 6], [6, 4], [4, 4], [4, 2], [2, 2]
[1, 5, 1], [5, 1, 1], [1, 1, 6], [1, 6, 4], [6, 4, 4], [4, 4, 2], [4, 2, 2]
[1, 5, 1, 1], [5, 1, 1, 6], [1, 1, 6, 4], [1, 6, 4, 4], [6, 4, 4, 2], [4, 4, 2, 2]
[1, 5, 1, 1, 6], [5, 1, 1, 6, 4], [1, 1, 6, 4, 4], [1, 6, 4, 4, 2], [6, 4, 4, 2, 2]
[1, 5, 1, 1, 6, 4], [5, 1, 1, 6, 4, 4], [1, 1, 6, 4, 4, 2], [1, 6, 4, 4, 2, 2]
[1, 5, 1, 1, 6, 4, 4], [5, 1, 1, 6, 4, 4, 2], [1, 1, 6, 4, 4, 2, 2]
[1, 5, 1, 1, 6, 4, 4, 2], [5, 1, 1, 6, 4, 4, 2, 2]
[1, 5, 1, 1, 6, 4, 4, 2, 2]

Next, we map each slice to the product of its minimum and its length. For each slice, this computes the area of the rectangle of 1 bits of maximum height that has the given slice as bottom row.

For the slices of length 3 of the penultimate row of our example matrix, this gives

3 3 3 3 12 6 6

All that's left to do is take the maximum across all slices of all rows.

For our example matrix, this gives 12.

How it works

‘×¥\ç"Ụ€FṀ  Main link. Argument: M (2D list of bits)

   \        Reduce the columns of M by the link to the left.
  ¥           Combine the two atoms to the left into a dyadic chain.
‘               Increment the left argument.
 ×              Multiply the result with the right argument.
      Ụ€    Grade up each; yield the indices of each row of M, sorted by their
            values. The order is not important here; we just need the indices.
    ç"      Apply the helper link to each element of the result to the left and
            the corresponding element of the result to the right.
        F   Flatten the resulting, nested list.
         Ṁ  Extract the maximum.


ṡṂ€€×"      Helper link. Arguments: R (row), X (indices of R)

ṡ           For each k in X, split R into overlapping slices of length k.
 Ṁ€€        Compute the minimum of each individual slice.
    ×"      Multiply the minima of all slices of length k by k.

Answer 2

MATL, 32 31 27 bytes

n:"@:"@1M2$ltntG4$bZ+=a*vX>

This uses a brute-force 2D convolution-based approach. All possible rectangle sizes are created and convolved with the terrain. The maximum result of all convolutions is the maximal rectangle area.

This is an extremely inefficient solution because in order to save bytes, I create kernels for all rectangles between [1, 1] and [numel(input) numel(input)] rather than actually determining the number of rows/columns in the input to determine the proper rectangle dimension ranges.

Thanks to @Luis for suggesting the usage of M and omitting the ]].

Try it Online!

Explanation

        % Implicitly grab input as a 2D numeric array
n       % Compute the number of elements in the input (over estimation of max kernel size)
:       % Create array 1:n
"       % For each value
  @     % Current loop index
  :     % Create an array from 1:(current_index)
  "     % For each of these values   
    @   % Push the current index onto the stack
    1M  % Grab the input to the previous function call (the outer index)
    2$l % Create an array of 1's whose dimensions are specified by top two stack elements
    tn  % Duplicate this array and compute number of elements
    t   % Duplicate this number
    G   % Explicitly grab input
    4$b % Bubble up the 4th element from the stack (the kernel)
    Z+  % Perform 2D convolution of this kernel and the input
    =a  % Determine if any convolution result (in each column) is equal to the area of the kernel.
        % This yields a row vector
    *   % Multiply the logical result by the area
    v   % Vertically concatenate all results (forces the row vectors above to be column vectors)
    X>  % Compute the maximum yielding the largest area
        % Implicitly display the result.

Answer 3

Julia, 83 60 57 53 bytes

!M=M⊆1?sum(M):maximum(t->!rotr90(M,t)[2:end,:],0:3)

Try it online! The last test case exceeds TIO's time limit, but I've verified it locally.

How it works

First, ! checks if its matrix argument M consists entirely of 1's.

• If so, ! returns the sum of M's entries, which is equal to its area.

• If not, ! does the following:

  1. Rotate M by 0°, 90°, 180° and 270° clockwise.

  2. Remove the first row of each of the four rotations, effectively removing one of top row, bottom row, leftmost column and rightmost column of M.

  3. Call itself recursively on each of the submatrices.

  4. Return the maximum of the return values from the recursive calls.

Answer 4

JavaScript (ES6), 97 bytes

a=>a.map((b,i)=>a.slice(i).map((c,j)=>c.map((d,k)=>(n=(b[k]&=d)&&n+j+1)>r?r=n:0,n=0),c=[]),r=0)|r

Turns out bit twiddling still wins. Accepts an array of array of integers. Ungolfed:

function rect(array) {
    var max = 0;
    for (var i = 0; i < array.length; i++) {
        var bits = array[i];
        for (var j = 0; i + j < array.length;) {
            var row = array[i + j];
            j++;
            var size = 0;
            for (var k = 0; k < row.length; k++) {
                if (!row[k]) bits[k] = 0;
                size = ones[k] ? size + j : 0;
                if (size > max) max = size;
            }
        }
    }
    return max;
}

The array is sliced by rows as per the other answers, so each possible range of rows is looped over. Given a range of rows, the next step is to measure the available rectangles. This is achieved by ANDing the rows together bitwise; the result is a list of bits which were set in the entire range of rows. It then remains to find the maximal length of set bits in the row and multiply that by the height of the range. Test shamelessly stolen from @ed65:

f=
a=>a.map((b,i)=>a.slice(i).map((c,j)=>c.map((d,k)=>(n=(b[k]&=d)&&n+j+1)>r?r=n:0,n=0),c=[]),r=0)|r

// test cases as strings, converted to 2d arrays
result.textContent = [
  ['0', 0],
  ['1', 1], 
  ['00 00', 0],
  ['01 10', 1],
  ['01 11', 2],
  ['111 010 111', 3],
  ['101 011 111', 4],
  ['0111 1110 1100', 4],
  ['1111111 1110111 1011101', 7],
  ['111011000 110111100 001111110 011111111 001111110 000111100 000011000', 20],
  ['000110000 110110010 110111110 110011100 010011111 111111111 111101110', 12]
].map(t => t[0].replace(/ /g, '\n') + '\n' + t[1] + '\n' + f(t[0].split` `.map(r => [...r]))).join`\n\n`

<pre id=result></pre>

Answer 5

Python 2.7, 93 91 89 81 79 bytes

f=lambda M,t=1:max(f(M[1:]),f(zip(*M)[::-1],t+1))if`t/3`in`M`else`M`.count(`t`)

Input is a list of tuples. Verify the smaller test cases here and the larger test cases here.

Without memoization, the last two test cases exceed Ideone's time limit, as they require, resp., 1,530,831,935 and 2,848,806,121 calls to f, which takes 39 and 72 minutes on my machine.

Algorithm

For a given matrix M, the general idea is to iterate over all submatrices of M by removing top rows and rotating quarter turns counterclockwise, keeping track of the sizes of encountered submatrices that consist entirely of 1 bits.

Golfing a straightforward recursive implementation of the above idea lead to a function f(M) that does the following.

1. If M doesn't contain any 0 bits, return its number of 1 bits.

2. If we have rotated M two times already and it doesn't contain any 1 bits, return 0.

3. If we have rotated M five times already, return 0.

4. Recursively call f on M without its top row.

5. Recursively call f on M rotated a quarter turn counterclockwise.

6. Return the maximum of the return values from the recursive calls.

Code

In the implementation, we use an additional function argument t that defaults to 1 to keep track of how many times we have rotated this particular matrix already. This allows condensing steps 1 to 3 into a single step by testing ​`t/3`in`M`​ and returning ​`M`.count(`t`)​ if the test fails.

1. If t = 1, we haven't rotated this particular submatrix previously in this branch.

   t / 3 = 0, so ​`t/3`in`M`​ will return True iff the string representation of M contains the character 0.

   If it doesn't, we return ​​`M`.count(`t`)​, the number of times the character 1 appears in the string representation of M.

   Note that a matrix without 0 bits can occur only if t = 1, since we do not recurse in this case.

2. If 3 ≤ t ≤ 5, we've previously rotated this particular submatrix at least two times in this branch.

   t / 3 = 1, so ​`t/3`in`M`​ will return True iff the string representation of M contains the character 1.

   If it doesn't, we return ​0 computed as ​`M`.count(`t`)​, the number of times the string representation of t (i.e., the character 3, 4 or 5) appears in the string representation of M.

3. If t = 6, we've previously rotated this particular submatrix five times in this branch.

   t / 3 = 2, so ​`t/3`in`M`​ will return False, because the string representation of M does not contain the character 2.

   We return ​0 computed as ​`M`.count(`t`)​, the number of times the character 6 appears in the string representation of M.

If f didn't return already, the remaining steps are executed.

4. f(M[1:]) calls f on M without its top row. Since t isn't specified, it defaults to 1, signaling that this is the first time f encounters this particular submatrix in this branch.

5. f(zip(*M)[::-1],t+1) calls f on M rotated a quarter turn counterclockwise, incrementing t to keep track of the time we've rotated this particular submatrix in this branch.

   The quarter turn is obtained by zipping the rows of M with each other, returning tuples of the corresponding elements of M's rows, thus transposing M, then reversing the order of rows (i.e., placing the top row at the bottom and vice versa).

6. Finally max returns the maximum of the return values from the recursive calls.

Answer 6

APL (Dyalog Extended), 27 23 20 bytes

-3 bytes by Adám and ngn

{⌈/∊(×/×⍵⍷⍨⍴∘1)¨⍳⍴⍵}

Try it online!

{⌈/∊(×/×⍵⍷⍨⍴∘1)¨⍳⍴⍵}    Monadic function taking an argument ⍵:
                 ⍳⍴⍵     Indices: e.g. for a 3x7 array
                                       (1 1) (1 2) ...  (1 7)
                                       (2 1) (2 2)  ... (2 7)
                                       (3 1) (3 2)  ... (3 7)
    (×/×⍵⍷⍨⍴∘1)         Helper fn: Takes ⍵ and x (e.g. (2 2))
            ⍴∘1             Make an array of 1s of shape x. Call it a.
        ⍵⍷⍨                 All places where a exists in x
     ×/                      Product of x's dims (size of a)
       ×                 Size of a where a is in ⍵, and 0 elsewhere.
    (×/×⍵⍷⍨⍴∘1)¨        Call the helper function on x and each (¨) index.
                            We now have a nested list containing sizes of blocks in ⍵
                            and many 0s.
   ∊                        Flatten
 ⌈/                        Find the maximum value.

Answer 7

JavaScript (ES6), 154 176

Edit tried to shorten a bit, but cannot compete against @Neil's solution

Try every possible rectangle, return the max size. Probably the same algorithm of the Matl answer, just 6 times longer.
Input as a 2d array of integers

g=>g.map((r,i)=>r.map((x,j)=>v=s(r,j,(_,l)=>s(g,i,(_,k)=>!s(g,k,r=>s(r,l,x=>!x,l+j+1),k+i+1)))&(t=-~i*-~j)>v?t:v),s=(a,i,l,j)=>a.slice(i,j).some(l),v=0)|v

Less golfed

This is the original algorithm, the golfed version abuse a lot of array traversing function istead of for loops

g=>{
  v = 0
  for(i = h = g.length; i; i--)
    for(j = w = g[0].length; j; j--)
    {
      p = true
      for(k=0; p && k <= h-i; k++)
        for(l=0; p && l <= w-j; j++)
          p = g.slice(k, k+i).some(r=>r.slice(l, l+j).some(x=>!x));
      if (!p && i*j<v)
        v = i*j
    }
  return v
}

Test

f=g=>g.map((r,i)=>r.map((x,j)=>v=s(r,j,(_,l)=>s(g,i,(_,k)=>!s(g,k,r=>s(r,l,x=>!x,l+j+1),k+i+1)))&(t=-~i*-~j)>v?t:v),s=(a,i,l,j)=>a.slice(i,j).some(l),v=0)|v

console.log=(...x)=>O.textContent+=x+'\n'

// test cases as strings, converted to 2d arrays
;[
  ['0',0],['1',1],['00 00',0],['01 10',1],['01 11',2],
  ['111 010 111',3],['101 011 111',4],
  ['0111 1110 1100',4],['1111111 1110111 1011101',7],
  ['111011000 110111100 001111110 011111111 001111110 000111100 000011000',20],
  ['000110000 110110010 110111110 110011100 010011111 111111111 111101110',12]
].forEach(t=>{
  var k=t[1]
  var p=t[0].split` `.map(r=>[...r].map(x=>+x))
  var r=f(p)
  console.log((r==k?'OK':'KO')+' '+r+(r==k?'':' expected '+k)+'\n'+p.join`\n`+'\n')
  })

<pre id=O></pre>

Answer 8

Brachylog, 20 17 15 bytes

Thanks to Kroppeb for 2 bytes

{s\sc≡ᵛ¹l}ᶠ⌉|hh

Try it online!

Explanation

{        }ᶠ      Find all possible outputs of the following predicate:
 s                Find a sublist of the array (i.e. remove 0 or more rows from the top
                  and/or bottom)
  \               Transpose the array
   s              Find a sublist again
                  The result is some sub-rectangle of the array
    c             Concatenate all the rows in that rectangle into one list
     ≡ᵛ¹          Verify that all the elements are 1
        l         Get the length (i.e. how many 1's make up the rectangle)
                 Now we have a list of the sizes of all possible 1-rectangles
           ⌉     Take the maximum

            |    If no 1-rectangles could be found:
             hh   Take the head of the head of the array (i.e. the top left element)
                 Since the array contains no 1's in this case, this will give 0

Answer 9

R, 129 122 bytes

function(M,D=dim(M),L=`for`){L(i,1:D,L(j,1:D[2],L(r,0:(D-i),L(c,0:(D[2]-j),F<-max(F,i*j*(i*j==sum(M[r+1:i,c+1:j])))))))
F}

Try it online!

Plain and simple brute force approach.

Unrolled code and explanation :

function(M){                       # M is the matrix of 0/1
n = 0                              # n is the biggest rectangle found
R=nrow(M)
C=ncol(M)
for(i in 1:R)                      # for each possible num of rows of the rectangle
  for(j in 1:C)                    # for each possible num of cols of the rectangle
    for(r in 0:(R-i))              # for each possible position offset on the rows
      for(c in 0:(C-j){            # for each possible position offset on the cols

         subM = M[1:i+r,1:j+c]     # sub-set the matrix given the size of rectangle and offsets

         if(sum(subM)==i*j)        # if sub-matrix is full of 1's
            rec = i*j              # (i.e. nrow*ncol == sum of values in sub-matrix)
         else                      # store the rectangle area
            rec = 0                # otherwise store 0

         n = max(n,rec)            # keep the maximum rectangle found
      }
}

Answer 10

Stax, 14 bytes

π└ÿ§L▓═J║φ§╦╢9

Run and debug it

Answer 11

Matlab 106 bytes

x=input('');[n,k]=size(x);r=0;for p=1:n;for m=1:k;r=max([p*m*(any(conv2(x,ones(p,m))==p*m)),r]);end;end;r

Ungolfed:

x=input(''); %//Take input
[n,k]=size(x); %//Determine array size
r=0; %//Variable for output. Initially zero
for p=1:n; %// Loop through the columns
    for m=1:k; %// Loop through the rows
        r=max([p*m*(any(conv2(x,ones(p,m))==p*m)),r]);%//See explanation below
    end;
end;
r %//Display result

The operation in the loop starts with 2D convolution conv2() of input array with the p*m array of ones. ==p*m checks if the resulting array contains an element equal to p*m. The corresponding element is turned to 1, all other elements are turned to 0. any() turns the array into vector. Columns containing at least one nonzero entry are turned to 1, otherwise 0. p*m*() multiplies the vector by p*m thereby turning all 1-s into p*m. [__,r] square brackets concatenate the obtained result with the previous maximum area stored in r. Finally, max() finds the maximum value in the resulting vector.

Answer 12

Matlab (222)(209)

Actually ,this solution brings me shame for being double-sized the actual same-language solution but ... blimey, i had been thinking of it for 6 hours! and the trick is a slightly different build off from Dennis and Neil 's answers.

    function p=g(x,a,u,i,j),i=i+~u;j=j+u;p=0;if(j*u+i*~u>=size(a,2-u))return;end,x=circshift(x,[0-u -1+u]),a=(x+a).*~~x.*~~a;for h=0+u:1,p=max([p,reshape(a(1:end-j,1:end-i),1,[]),g(~u*(a*h+x*~h)+u*x,a,h,i,j)]);end

• The function is called as

  y=[1 1 1 0 1 1 0 0 0;
  1 1 0 1 1 1 1 0 0;
  0 0 1 1 1 1 1 1 0;
  0 1 1 1 1 1 1 1 1;
  0 0 1 1 1 1 1 1 0;];
  t=g(y,y,[],0,0,0);t,
  

• I could save more bytes if introduced matrix length in function's dimentions, eventhough, more golfing is ongoing.

• How does this proceed?

  This algorithm adds the actual matrix to itself shifted of it to left direction, with a bit twiddling (&). in any stage the resulted matrix is set as initial and added to itself shifted upward repeatedly,then reloop from the beginning with the new matrix. All sub-elements of all the matrices generated by this operation (original_matrix+shifted_matrix)&shifted_and_original_matrices) are maximized to the output.

example:

     1 1 1         1 1 0                      2 2 0                  0 2 0                        0 4 0
 M0= 0 1 1  M0<<1= 1 1 0  M1=(M0+M0<<1)&both= 0 2 0    shift(M1,up)= 2 0 0  M2=(M1+sh(M1,u)&both= 0 0 0  
     1 1 0         1 0 0                      2 0 0                  0 0 0                        0 0 0
                        2 0 0                               4 0 0
 M3=(M0<<1+M0<<2)&both= 2 0 0 , M4=(M3+shift(M3,up))&both=  0 0 0
                        0 0 0                               0 0 0

                3 0 0                             
 M5=(M1+M0<<2)= 0 0 0 , M6=(M5+shift(M5,up))&both=zeros(3,3).
                0 0 0

 Max_of_all_values=Max(0,1,2,3,4)=4

Answer 13

Japt, 30 bytes

®åÏ*°X}ÃÕ®£ZãYÄÃm®rm *Zl}Ãc rw

Try all test cases

Approximately a port of Dennis's Jelly answer. The test cases are simply 2D arrays of numbers, converted from the question's format using this.

Explanation:

®      Ã                          #For each row:
 å    }                           # Replace each number with this running total:
    °X                            #  Increment the previous total
  Ï*                              #  Multiply it by the current number
        Õ                         #Transpose rows and columns
         ®               Ã        #For each column:
          £    Ã                  # Iterate over the range [0..length) as Y:
           ZãYÄ                   #  Get the subsections of that column with length Y+1
                m®      }         # For each subsection:
                  rm              #  Get the minimum
                     *Zl          #  Multiply it by the length
                          c       #Flatten everything to a single list of possible rectangle sizes
                            rw    #Get the maximum

Answer 14

J, 38 bytes

,"0/&(1+i.)/@$>./@,@:((#**/)@,;._3"$)]

Try it online!

how

,"0/&(1 + i.)/@$ >./@,@:((# * */)@,;._3"$) ]
              @$                             NB. pass the shape of
                                             NB. the input (rows, cols)
                                             NB. to...
,"0/&(1 + i.)/                               NB. this verb, which will
    &(1 + i.)/                               NB. will first create 2
                                             NB. lists: 1...num rows
                                             NB. and 1...num cols.
,"0/                                         NB. and then creat a cross
                                             NB. of every possible 
                                             NB. concatenation of the two,
                                             NB. giving us all possible 
                                             NB. rectangle sizes. pass 
                                             NB. that and...
                                           ] NB. the original input
                 >./@,@:((# * */)@,;._3"$)   NB. to this verb, which
                                   ;._3"$    NB. will take every 
                                             NB. possible rectangle of
                                             NB. every size,
                                 @,          NB. flatten it and...
                         (# * */)            NB. multiply the size of
                                             NB. the list by the list's 
                                             NB. product, yielding the
                                             NB. size of the list if it's
                                             NB. all ones, zero otherwise.
                     ,@:                     NB. Flatten all those results
                                             NB. into one big list
                 >./@                        NB. and take the max.