Largest rectangle in 2d array

Question

Input

The board: A 2D container (matrix, list of lists, etc.) of letters like:

  ["B", "C", "C", "C", "C", "B", "B", "C", "A", "A"],
  ["B", "A", "C", "B", "B", "A", "B", "B", "A", "A"],
  ["B", "C", "B", "C", "A", "A", "A", "B", "C", "B"],
  ["B", "B", "B", "A", "C", "B", "A", "C", "B", "A"],
  ["A", "A", "A", "C", "A", "C", "C", "B", "A", "C"],
  ["A", "B", "B", "A", "A", "C", "B", "C", "C", "C"],
  ["C", "B", "A", "A", "C", "B", "B", "C", "A", "A"]

If you choose a list of lists you may assume that all of the sublists are of the same length.

Rules

• To make a valid rectangle you need all rectangle corners with the same 'letter'.
• Example, look the sample board with X bellow. You can see 'X' on (1,0) also on (4,0) also on ( 1,3) and on (4,3) then you have the rectange [1,0,4,3] that means from (1,0) to (4,3):

Sample board with X:

  ["B", "X", "C", "C", "X", "B", "B", "C", "A", "A"],
  ["B", "A", "C", "B", "B", "A", "B", "B", "A", "A"],
  ["B", "C", "B", "C", "A", "A", "A", "B", "C", "B"],
  ["B", "X", "B", "A", "X", "B", "A", "C", "B", "A"],
  ["A", "A", "A", "C", "A", "C", "C", "B", "A", "C"],
  ["A", "B", "B", "A", "A", "C", "B", "C", "C", "C"],
  ["C", "B", "A", "A", "C", "B", "B", "C", "A", "A"]

• The goal is to find the rectangle or one of the rectangles with the largest area, calculated by (right-left+1)*(bottom-top+1)
• If there are multiple rectangles with the same maximum area, output any one. Optionally the one with (top coordinate, left coordinate, right coordinate, bottom coordinate) lexicographically smallest.
• Rectangles must have edges parallel to the board's edge.
• Each letter is a printable ASCII char from A to Z (both included).

Output

The output should be the left-up and right-down positions of the largest area rectangle corners. For the first sample "board" the big square is the yellow one:

And the answer should be:

[1, 1, 8, 4]

A second example test case

An input of:

["C", "D", "D", "D", "A", "A"],
["B", "D", "C", "D", "A", "A"],
["B", "D", "D", "C", "A", "C"],
["B", "D", "B", "C", "A", "C"]

Should yield one of these three coordinate lists identifying an area six rectangles:

[1, 0, 2, 2]
[1, 0, 3, 1]
[3, 2, 5, 3]

This question is posted on Stack Overflow with title: How to find the largest rectangle in a 2D array formed by four identical corners? and with this rude JS solution (I can say "rude" because is my code ;) :

Ok, is my first post, be tolerant with me please. I will change all you say to improve the quiz.

Answer 1

Python 2, 148 130 bytes

lambda x,e=enumerate:min(((a-c)*(d-b),b,a,d,c)for a,y in e(x)for c,k in e(x)for b,g in e(y)for d,h in e(y)if g==h==k[b]==k[d])[1:]

Try it online!

Answer 2

Retina, 163 162 bytes

Lw$`(?<=(.*\n)*((.)*))(?=(.))((.)*(?<=(.*))\4)((.*\n)*((?>(?<-3>.)*)(?=\4)(?>(?<-6>.)*))\4)?
$.7,$#1,$.2,-$.($5$#9*$5),$.2,$#1,$.7,$.($#1*_$#9*
4{N`
)m`^.*?,

0G`

Try it online! Edit: Saved 1 byte because the trailing ) matching the $.( is implicit. Explanation:

Lw$`(?<=(.*\n)*((.)*))(?=(.))((.)*(?<=(.*))\4)((.*\n)*((?>(?<-3>.)*)(?=\4)(?>(?<-6>.)*))\4)?

This regular expression matches rectangles. The groups are as follows: 1) Top row (as capture count) 2) Left column (as length) 3) Balancing to ensure the left corners align 4) Letter for the corners 5) Width + 1 (as length) 6) Balancing to ensure the right corners align 7) Right column (as length) 8) unused 9) Height (as capture count). The w option ensures that all possible widths of rectangles are matched for each given top left corner. The $ options lists the results using the following substitution pattern.

$.7,$#1,$.2,-$.($5$#9*$5),$.2,$#1,$.7,$.($#1*_$#9*

The substitutions are as follows: The right column, the top row, the left column, the negation of the area of the rectangle (literally calculated as the length of repeating the width string by one more than height number of times), the left column, the top row, the right column, followed by an expression that evaluates to the bottom row (a capture would have cost 12 bytes plus I've run out of single-digit variables). The first four captures represent the sort order in order of priority. As Retina sorts stably, a multicolumn sort can be established by sorting by each sort column in turn from least to greatest priority. (The area must be sorted in descending order, so a single string sort cannot be used.)

4{N`

Four numeric sorts are then performed.

)m`^.*?,

The sort column is then deleted after each sort.

0G`

The first entry is therefore now the desired result.

Note: The restriction on the choice of rectangle of a given area has since been relaxed and the following 144 143-byte version prefers a wider rather than a taller rectangle:

Lw$`(?<=(.*\n)*((.)*))(?=(.))((.)*(?<=(.*))\4)((.*\n)*((?>(?<-3>.)*)(?=\4)(?>(?<-6>.)*))\4)?
-$.($5$#9*$5);$.2,$#1,$.7,$.($#1*_$#9*
N`
0G`
.*;

Try it online!

Answer 3

Jelly, (27?)  29  28 bytes

^{27 if 1-based indexing is allowed - remove trailing ’}

Fṙ1s2;Uœị³EaZI‘P
ZLpLŒċÇÞṪF’

A full program.

Try it online! (or see the other test case)

How?

Fṙ1s2;Uœị³EaZI‘P - Link 1, areaOrZero: list of pairs [[b,l],[t,r]]
F                - flatten the input                 [b,l,t,r]
 ṙ1              - rotate left one                   [l,t,r,b]
   s2            - split into twos                   [[l,t],[r,b]]
      U          - upend the input                   [[l,b],[r,t]]
     ;           - concatenate                       [[l,t],[r,b],[l,b],[r,t]]
         ³       - program's input
       œị        - multidimensional index into
          E      - all equal?                       X
            Z    - transpose the input              [[b,t],[l,r]]
           a     - logical AND (vectorises)         (if not X we now have [[0,0],[0,0]]
             I   - incremental differences          [t-b,r-l] (or [0,0] if not X)
              ‘  - increment (vectorises)           [t-b+1,r-l+1] (or [1,1] if not X)
               P - product                          area (or 1 if not X)

ZLpLŒċÇÞṪF’ - Main link: list of lists
Z           - transpose the input
 L          - length
   L        - length of the input
  p         - Cartesian product
    Œċ      - pairs with replacement
       Þ    - (stable) sort by:
      Ç     -   last link (1) as a monad
        Ṫ   - tail (note that the rightmost pre-sort represents the bottom-right 1x1
            -       so cannot be superseded by a non-matching rectangle)
         F  - flatten
          ’ - decrement (vectorises) (to get to 0-based indexing)

Answer 4

Perl 6, 83 73 bytes

{([X] (^$^a[0]X ^$a)xx 2).max:{[eq] $a[.[*;1];.[*;0]]and[*] 1 X-[Z-] $_}}

Try it online!

Returns a list of lists ((x0 y0) (x1 y1)).

Explanation

{
  ([X]                   # Cross product of corner pairs.
    (^$^a[0]             # Range of x coords.
     X                   # Cross product of coords.
     ^$a                 # Range of y coords.
    )xx 2                # Duplicate list.
  ).max:                 # Find maximum of all ((x0 y0) (x1 y1)) lists
  {                      # using the following filter.
    [eq]                 # All letters equal?
      $a[.[*;1];.[*;0]]  # Multidimensional subscript with y and x coord pairs.
    and                  # Stop if false.
    [*]                  # Multiply
      1 X-[Z-] $_        # for each axis 1 - (c0 - c1) == c1 - c0 + 1.
  }
}

Answer 5

JavaScript (ES6), 121 bytes

-1 byte thanks to @l4m2
-1 byte thanks to @tsh
+2 bytes to comply with the new rectangle scoring rule

Takes input as a matrix of strings. Returns 0-indexed coordinates: [x0, y0, x1, y1].

a=>a.map(b=(r,y)=>r.map((v,x)=>a.map((R,Y)=>R.map((V,X)=>V+R[x]+r[X]!=v+v+v|(A=(x+~X)*(y+~Y))<b||(o=[x,y,X,Y],b=A)))))&&o

Try it online!

Answer 6

Haskell, 144 bytes

import Data.Array
o=assocs
f r=snd$maximum[((c-a+1)*(d-b+1),[a,b,c,d])|((a,b),x)<-o r,((c,d),y)<-o r,x==y,r!(a,d)==r!(c,b),x==r!(a,d),a<=c,b<=d]

Try it online!

Answer 7

Jelly, 24 bytes

XLṭLp`€p/⁺œị€EɗÐfI‘PɗÞ0Ṫ

Try it online!

⁺ proves to be useful.

Output format: [top,bottom],[left,right]. 1-indexing.

Answer 8

APL (Dyalog Classic), 38 bytes

a⊃⍨⊃⍒×/1+-/↑2 2∘⍴¨a←⍸≢¨↑∘.(∩¨)⍨∘.∩¨⍨↓⎕

Try it online!

Answer 9

Java 8, 208 205 bytes

m->{int r=0,R[]={},i=m.length,j,y,z,u,t,T;for(;i-->0;)for(j=m[i].length;j-->0;)for(y=i*j;y-->0;)if((T=m[i][j])==m[u=y/j][z=y%j]&T==m[i][z]&T==m[u][j]&r<(t=(i-u)*(j-z))){r=t;R=new int[]{z,u,j,i};}return R;}

Can definitely be golfed.. I now use the most obvious approach of using four three nested for-loops.

-3 bytes thanks to @ceilingcat combining the inner loops of rows and columns into a single loop.

Explanation:

Try it online.

m->{                         // Method with char-matrix parameter and int-array return-type
  int r=0,                   //  Largest area found, starting at 0
      R[]={},                //  Result coordinates, starting empty
      i=m.length,j,          //  x,y indices of the first corner
      y,z,                   //  x,y indices of the second corner
      u,t,T;                 //  Temp integers to reduce bytes
  for(;i-->0;)               //  Loop `i` over the rows
    for(j=m[i].length;j-->0;)//   Inner loop `j` over the columns
      for(y=i*j;y-->0;)      //    Inner loop over the rows and columns
        if((T=m[i][j])==m[u=y/j][z=y%j]
                             //      If the values at coordinates [i,j] and [y,z] are equal
           &T==m[i][z]       //      as well as the values at [i,j] and [i,z]
           &T==m[u][j]       //      as well as the values at [i,j] and [y,j]
           &r<(t=(i-u)*(j-z))){
                             //      And the current area is larger than the largest
          r=t;               //       Set `r` to this new largest area
          R=new int[]{z,u,j,i};}
                             //       And save the coordinates in `R`
  return R;}                 //  Return the largest rectangle coordinates `R`