Largest rectangle in a skyline

A skyline is an array of positive integers where each integer represents how tall a building is. For example, if we had the array [1,3,4,2,5,3,3] this would be the skyline in ascii art:

    #
# #
## ###
######
#######


Your task is to find the area of the largest rectangle in the skyline. In this case, the largest rectangle has area 12. Here is the rectangle, highlighted:

    #
# #
## ###
RRRRRR
#RRRRRR


You can assume that the input contains at least one building (the length of the array is >0). This is , you know the drill.

Inspired by this Puzzling-SE post.

Test cases

[1] -> 1
[2, 2] -> 4
[3, 2, 1] -> 4
[1, 2, 3] -> 4
[1, 5, 1, 5] -> 5
[1, 4, 1, 4, 1] -> 5
[1, 4, 5, 4, 1] -> 12
[1, 5, 4, 5, 1] -> 12
[1, 2, 3, 5, 1, 3] -> 6
[1, 3, 3, 1, 4, 5, 2] -> 8
[1, 3, 3, 1, 1, 1, 1] -> 7

• can we take a boolean matrix as input? Feb 14, 2022 at 9:00
• @Razetime no, it would be a different challenge and regardless almost a dupe of this Feb 14, 2022 at 10:00

Octave, 50 bytes

@(a)max(([c,v]=runlength([(a<=a').*a;0*a](:))).*v)


Try it online!

Based on my PARI/GP answer, but more interesting. This worth writing a Jonah-style explanation.

how

Takes a = [1,3,4,2,5,3,3] as an example.

• a<=a' creates a matrix where the entry at (i,j) is a[j]<=a[i]:

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

• .*a multiplies the i-th column of the matrix with a[i]:

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

• [...;0*a] appends a row of zeros to the matrix, so that the columns are separated when taking run length encoding:

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

• ...(:) concatenates the matrix into a column vector (the actual output is the transpose of the following row vector):

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

• [c,v]=runlength gives the run length encoding, where each non-zero run corresponds to a rectangle in the skyline:

c =
7   2   2   1   3   3   1   1   1   4   6   5   1   4   2   1   3   2   2   1   3   1

v =
1   0   3   0   3   0   4   0   4   0   2   0   5   0   3   0   3   0   3   0   3   0

• ([c,v]=runlength(...)).*v multiplies c and v element by element, which gives the "area" of each run:

7    0    6    0    9    0    4    0    4    0   12    0    5    0    6    0    9    0    6    0    9    0

• Finally, max finds the maximum values of the result:

12


Jelly, 7 bytes

ẆṂ×LƊ€Ṁ


Try it online!

Ẇ   Ɗ€     For each contiguous sublist of the input,
Ṃ×        multiply its smallest element by
L       its length.
Ṁ    Return the largest product.


Wolfram Language (Mathematica), 35 bytes

-5 bytes thanks to @att.

Max[Tr[Min@#+0#]&/@Subsequences@#]&


Try it online!

• 35 bytes
– att
Feb 14, 2022 at 7:59

Python 3, 56 bytes basically by AnttiP

f=lambda x:x>[]and max(min(x)*len(x),f(x[1:]),f(x[:-1]))


Try it online!

Python 3, 72 bytes

lambda x:max(min(x[i:j])*(j-i)for j in range(len(x)+1)for i in range(j))


Try it online!

Python 3.8 (pre-release), 86 85 bytes

lambda x:(R:=range(0,len(x)+1))and max(min(x[i:j])*(j-i)for i in R for j in R if i<j)


Try it online!

Avoid something by pxeger

• I was going to say you could use the walrus operator in 3.8, but perhaps not... Feb 14, 2022 at 7:23
• @UnrelatedString Something would go wrong
– l4m2
Feb 14, 2022 at 7:24
• 59 bytes: Try it online! Feb 14, 2022 at 7:28
• -1 on the last one: Try it online! Feb 14, 2022 at 7:50

05AB1E, 8 bytes

ŒεWsg*}à


Port of @UnrelatedString's Jelly answer, so make sure to upvote him/her as well!

Explanation:

Œ       # Get all sublists of the (implicit) input-list
ε      # Map each sublist to:
W     #  Push its minimum (without popping the sublist)
s    #  Swap so the sublist is at the top again
g   #  Pop and push its length
*  #  Multiply it by the minimum
}à     # After the map: pop and push the maximum
# (after which it is output implicitly as result)


Vyxal, 9 bytes

ÞSƛgnL*;G


Try it Online!

Port of Unrelated String's Jelly answer.

ÞSƛ    ;  # For each contiguous sublist
g  *   # Multiply the smallest element
nL    # The length.
G # Get the largest product.

• -2 with a flag. Feb 14, 2022 at 8:26
• @lyxal I know.. Feb 14, 2022 at 8:26

BQN, 18 bytesSBCS

{⌈´(+´≠⥊⌊´)¨∾↓¨↑𝕩}


Run online!

↑𝕩 Prefixes of the input (includes the empty prefix)
↓¨ Suffixes of each prefix
∾ Flatten into a list of sublists
( )¨ For each sublist:
≠⥊⌊´ Reshape the minimum to the length of the sublist

+´ Sum the resulting list ⌈´ Get the maximum result

Instead of +´≠⥊⌊´ other answers use ≠×⌊´, but that results in 0×∞ = NaN for empty sublists, which ends up as the result of ⌈´.

R, 63 bytes

function(l,r=rle(c(t(cbind(outer(l,l,<=)*l,0)))))max(r$l*r$v)


Try it online!

Port of alephalpha's solution.

• I managed to get to 74 bytes porting the "try each subsequence" strategy, but perhaps there's still a big golf I'm missing? Feb 14, 2022 at 21:10
• Hmm, I don't see one, @Giuseppe. I also got around 70-something with taking rle along each row to omit zero-padding like in Sundar's MATL answer. Feb 15, 2022 at 7:32

Brachylog, 9 bytes

sᶠ⟨⌋×l⟩ᵐ⌉


Try it online!

sᶠ    ᵐ     For each contiguous sublist of the input,
⟨⌋× ⟩      multiply its smallest element by
l       its length.
⌉    Return the largest product.


MATL, 1715 14 bytes

&<~G!*"@Y'*vX>


(Edit: turns out alephalpha's idea is very similar, this just uses a loop instead of zero padding + linearization)

With input [1; 2; 3; 5; 1; 3]

&<~         % make a boolean matrix, each column denoting
%   which buildings are >= current one


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

G!*         % multiply by input


1 0 0 0 1 0
1 2 0 0 1 0
1 2 3 0 1 3
1 2 3 5 1 3
1 0 0 0 1 0
1 2 3 0 1 3

"@Y'        % for each column, take its run-length encoding


eg. for second column,
[0 2 0 2]
[1 3 1 1]

*           % multiply to get rectangle areas

vX>         % cumulatively, keep finding the maximum area

% implicit loop end, implicit output


-1 byte thanks to @LuisMendo.

• @LuisMendo I've probably done this every time there's a X> near the end, and you've helpful pointed it out every time. I never seem to learn though. :D Feb 14, 2022 at 20:13
• Haha, I didn't remember that. So, you may want to bookmark this Feb 14, 2022 at 20:53

Factor, 58 bytes

[ all-subseqs [ dup infimum swap length * ] map supremum ]


Try it online!

• all-subseqs Get every possible grouping of contiguous skyscrapers.
• [ dup infimum swap length * ] map Get the area of each grouping by multiplying the height of the shortest skyscraper in the grouping by the number of skyscrapers in the grouping.
• supremum Return the largest area.

Pari/GP, 50 bytes

a->m=vecmax;m([m([c=(t>=s)*c+=s|t<-a*!c=0])|s<-a])


Try it online!

Pari/GP, 50 bytes

a->m=0;[[m=max(m,c=(t>=s)*c+=s)|t<-a*!c=0]|s<-a];m


Try it online!

Charcoal, 19 bytes

Ｉ⌈Ｅθ⌈Ｅ⊕κ×⁻⊕κλ⌊✂θλ⊕κ


Try it online! Link is to verbose version of code. Explanation: Port of @l4m2's Python answer.

   θ                Input array
Ｅ                 Map over elements
κ            Current index
⊕             Incremented
Ｅ              Map over implicit range
κ        Outer index
⊕         Incremented
⁻          Subtract
λ       Inner index
×           Multiplied by
θ    Input array
✂     Sliced from
λ   Inner index to
κ Outer index
⊕  Incremented
⌊      Take the minimum
⌈               Take the maximum
⌈                  Take the maximum
Ｉ                   Cast to string
Implicitly print


JavaScript (ES6), 69 bytes

f=a=>+a||Math.max(Math.min(...a)*a.length,f(a.slice(1),a.pop()),f(a))


Try it online!

Commented

f =                // f is a recursive function taking:
a =>               //   a[] = skyline array
+a ||            // if a[] is a singleton, return its unique value
Math.max(        // otherwise, return the maximum of:
Math.min(...a) //   1) the smallest value of a[]
* a.length,    //      multiplied by the length of a[]
f(             //   2) the result of a recursive call
a.slice(1),  //      with the 1st item removed
a.pop()      //      (remove the last item for the next call)
),             //
f(a)           //   3) the result of a recursive call
//      with the last item removed
)                // end of Math.max()


Python3, 78 bytes:

f=lambda x,c=0,j=1:j>len(x)or max([min(x[c:j])*(j-c),f(x,c,j+1),f(x,c+1,j+1)])


Try it online!

C (gcc), 108 97 bytes

m;s;j;k;f(a,n)int*a;{for(m=0;n--;)for(j=a[n];s=j;--j,m=s>m?s:m)for(k=n;k--;)s+=a[k]<j?k=0:j;j=m;}


Try it online!

Inputs a pointer to an array of positive integers and its length (because pointers in C carry no length info).
Returns the area of the largest rectangle in the skyline.

APOL, 29 bytes

M(ƒ(z(Ŀ(s(i))) *(m(∋) l(∋))))

A port of UnrelatedString's Jelly answer.

Explanation

M(                Largest element of
ƒ(              For
z(Ŀ(s(i)))    every contiguous sublist of the input,
*(m(∋) l(∋))  multiply its smallest item by its length
)               and make a list of the results.
)
implicit print


Husk, 7 bytes

▲m§*▼LQ


Try it online!

Explanation

▲m§*▼LQ
m    Q   for each contiguous sublist
§*      multiply it's
▼L    minimum value by it's length
▲         maximum of that


JavaScript (Node.js), 64 bytes

a=>Math.max(...a.map((n,i)=>(g=d=>a[i+=d]>=n&&g(d)+n)(-1,g(1))))


Try it online!

Related

xM(mn*×l)<cg


In the interested of transparency, since hgl is under heavy development some features used in this answer were only merged into master recently.

Explanation

We just use the most straightforward possible algorithm.

cg gets all contiguous sublists we take these as the footprints for potential boxes. We then for each of these multiply it's length by it's minimum element with mn*×l and take the maximum overall.

This is just a simpler version of the algorithm employed in the more interesting version of this challenge.

f l=maximum[x*(minimum\$take x t)|t<-scanr(:)[]l,x<-[1..length t]]