# Smallest maximal 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:

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


A maximal rectangle is a rectangle that cannot be extended in any direction while being contained in the skyline. For example, the following is a maximal rectangle:

    #
# #
## ###
AAAAAA
#AAAAAA


While the following is not:

    #
# #
## #BB
####BB
#####BB


Since you can extend it to the left like so:

    #
# #
## CCC
###CCC
####CCC


This would be a maximal rectangle.

Your task is to take a skyline as input (list of positive integers) and return the area of the smallest maximal rectangle. You can assume the length of the input is at least 1.

# Testcases

[1] -> 1
[1,1] -> 2
[2,2,2] -> 6
[3,2,3] -> 3
[3,2,1] -> 3
[6,3,1,5] -> 4
[1,5,5,5] -> 4
[5,5,5,1] -> 4
[1,2,3,4] -> 4
[1,2,3,4,5] -> 5
[1,1,1,5,1,1,1] -> 5
[10,3,1,1,1,1,1,3,10] -> 6


This is code-golf, so shortest bytes in any language wins!

• Is the answer for the last testcase 9 or 6? Feb 18, 2022 at 0:04
• What is the correct answer for 6 3 1 5 ? Feb 18, 2022 at 1:19
• @alephalpha I would also think the final test case is 6 Feb 18, 2022 at 1:32
• @Jonah Fixed last test case, correct answer for your example is 4 Feb 18, 2022 at 8:37
• @qwr I think this answer, with a bit of modification, would be a O(n) solution. Feb 18, 2022 at 20:56

# J, 61 bytes

0<./@-.~[:,[:(~.*#-I.@~:)"1@|:[:(0-.~#;._1@,~&0)"1@|.@|:#"+&1


Try it online!

I believe the final test case should be 6 and that 6 3 1 5 should return 4. Needs to be verified by OP.

Grotesquely long, but perhaps an interesting idea...

## how

Consider 6 3 1 5.

• #"+&1 Expand into a sideways bar chart of ones:

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

• |.@|: Rotate it regular-ways:

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

• [:(0-.~#;._1@,~&0)"1 For each row, count the runs of ones:

1 0
1 1
1 1
2 1
2 1
4 0

• |: Transpose:

1 1 1 2 2 4
0 1 1 1 1 0

• [:(~....I.@~:)"1 For each row, get the nub (uniq) and the nub sieve positions (ie, positions of first occurence of each). Eg with row 1:

1 1 1 2 2 4  - Row 1
1 2 4        - Uniq
0 3 5        - Positions of first occurrences

• #- Subtract the positions from length:

0 3 5        - Positions of first occurrences
6 3 1        - Length minus positions

• * Multiply those by the uniq values: gives us sizes of maximal rectangles. (Remember we're still showing just 1 row even though there are multiple)

1 2 4        - Uniq
6 3 1        - Length minus positions
-------------
6 6 4        - Elementwise product

• 0<./@-.~[:, Flatten, remove zeroes, take the min.

4


# Wolfram Language (Mathematica), 56 bytes

Min[(aTr/@Pick[a+0(l=SplitBy[#,#<a&]),Min/@l,a])/@#]&


Try it online!

• What is happening here: aTr? Feb 18, 2022 at 15:01
• @Jonah  is \[Function]. (aTr/@Pick[a+0(l=SplitBy[#,#<a&]),Min/@l,a]) defines an anonymous function, which is equivalent to Function[a, Tr /@ Pick[a + 0 (l = SplitBy[#1, #1 < a &]), Min /@ l, a]]. Feb 19, 2022 at 3:49
• Oh weird, when I pasted it into Wolfram, it looks like an arrow, but on this site it displays as an Asian character for me. Feb 19, 2022 at 4:03
• @Jonah The character is in the Private Use Area. Feb 19, 2022 at 4:33

# 05AB1E, 24 bytes

Å1ζRεÅγsÏ}ζεDÙþ©kygα®*}ß


A port of @Neil's Charcoal answer is 24 bytes as well:

0.øŒʒD¦¨ß‹Á2£P}ε¦¨Wsg*}ß


Explanation:

Å1                # Map each value in the (implicit) input-list to a list of that
# many 1s
ζ               # Zip/transpose; swapping rows/columns,
# using a space as filler by default for rows of unequal length
R              # Reverse the rows
ε             # Map over each row:
Åγ           #  Run-length encode it, pushing a list of values and lengths
#  separated to the stack
s          #  Swap so the values are at the top
Ï         #  Only leave the lengths at truthy (==1) positions
}ζ            # After the map: zip/transpose with space filler again
ε           # Map over each row:
D          #  Duplicate the current list
Ù         #  Uniquify the items in the copy
þ        #  Remove all spaces by only keeping digits
©       #  Store this in variable ® (without popping)
k      #  Get the first 0-based index of each unique value in the list
α   #  Calculate the absolute difference of each index with
yg    #  the length of the current row-list
®* #  Multiply the values to list ® at the same positions
}ß          # After the map: pop and push the flattened minimum
# (which is output implicitly as result)

0.ø               # Surround the (implicit) input-list with leading/trailing 0
Œ              # Pop and push all sublists
ʒ                 # Filter this list of lists by:
D                #  Duplicate the sublist
¦¨              #  Remove the first and last items in the copy
ß             #  Pop and push the minimum
‹            #  Check for each value in the list if this minimum is larger
Á           #  Rotate the list of checks once towards the right
2£         #  Pop and leave just the first two
P        #  Product to check if both of them are truthy
}ε                # After the filter: map over the remaining sublists:
¦¨              #  Remove the first and last items again
W             #  Push the minimum (without popping the list)
#  (this will be an empty string for empty lists)
s            #  Swap so the list is at the top
g           #  Pop and push its length
*          #  Multiply the length by this minimum
}ß               # After the map: pop and push the minimum integer (ignoring any
# empty strings)
# (which is output implicitly as result)


# Jelly, 16 bytes

Ø0jẆµḢ»Ṫ<aṂ)ȦƇ§Ṃ


A monadic Link accepting a list of positive integers that yields a positive integer.

Try it online! Or see the test-suite.

### How?

Ø0jẆµḢ»Ṫ<aṂ)ȦƇ§Ṃ - Link: list of positive integers, H
Ø0               - [0,0]
j              - join with S -> [0,h1,h2,...,hn,0]
Ẇ             - all contiguous sublists
µ      )     - for each sublist, S:
Ḣ           -   remove & yield the head from S
Ṫ         -   remove & yield the tail from S (yields 0 if S was empty)
»          -   maximum
<        -   less than? (vectorises across the altered S)
Ṃ      -   minimum (of the altered S; 0 if S is empty)
a       -   logical AND (vecorises)
Ƈ   - filter keep those for which:
Ȧ    -   any and all? (i.e. non-empty and all non-zero)
§  - sums
Ṃ - minimum


Also at 16 (TIO), and perhaps more elegant:

>Ɱ’aṣ€0Ẏ¹ƇṂ×LƊ€Ṃ - Link: H
Ɱ’              - map across decremented values of H with:
>                -   H greater than? (vectorises)
a             - logical AND H (vectorises)
ṣ€0          - split each at zeros
Ẏ         - tighten
¹Ƈ       - keep the truthy (i.e. non-empty) ones
Ɗ€  - for each:
Ṃ      -   minimum
L    -   length
×     -   multiply
Ṃ - minimum

• 3 1 3 3 should return 3 Feb 18, 2022 at 14:01
• @Jonah - hmm, will need to leave it until later to address, don't think it'll be hard to fix though... Feb 18, 2022 at 14:07
• @Jonah it wasn't an easy fix like I thought, so a complete change of tack. I feel like this may not be the shortest possible though... Feb 18, 2022 at 18:37

# JavaScript (Node.js), 64 bytes

-2 bytes by Arnauld

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


Try it online!

Simply find the smallest one from all maximal rectangles:

    *       *       *       *       #       *       *
* *     * *     # *     * *     * #     * *     * *
** ***  ## ***  *# ***  ** ***  ** #**  ** ###  ** ###
******  ##****  *#****  ######  ***#**  ***###  ***###
####### *##**** **#**** *###### ****#** ****### ****###


Above example show all possible maximal rectangles with height $$\a_i\$$.

Related

# Charcoal, 40 bytes

⊞θ⁰ＦＬθＦιＦ⬤⟦⊖κι⟧›⌊✂θκι¹§θλ⊞υ×⁻ικ⌊✂θκι¹Ｉ⌊υ


Try it online! Link is to verbose version of code. Explanation:

⊞θ⁰


Push a guard value to the input array. (This also simplifies the iteration as in my answer to the linked question I had to increment variables all over the place but here I effectively get a free increment.)

ＦＬθＦι


Loop over all of the sublists of the original array.

Ｆ⬤⟦⊖κι⟧›⌊✂θκι¹§θλ


Check that the minimum of this sublist is greater than both of its neighbours.

⊞υ×⁻ικ⌊✂θκι¹


Calculate the size of this maximal rectangle.

Ｉ⌊υ


Output the minimum of all the sizes.

# Jelly, 22 bytes

>Ḣ×\×«\ŒɠÄ×QƲ
ŻÇÐƤẎ¹ƇṂ


Try it online!

Should work now. Filters each suffix to the longest prefix which wouldn't contain suffixes of other suffixes' rectangles, computes the area of each maximal rectangle sharing its left edge with each of those substrings, and returns the smallest non-zero such area.

>Ḣ×\×«\ŒɠÄ×QƲ    Monadic helper link: compute areas from "maximal zone" of suffix
Ḣ               Remove the first item
>                and compute the mask of which remaining items are greater.
×\             Zero any ones after the first zero,
×            then multiply with corresponding elements of
«\          the cumulative minima.
Œɠ        Compute the lengths of runs of equal minima,
Ä       take the cumulative sums of those,
×      and multiply with corresponding elements of
QƲ    the nub of the cumulative minima.

Ż           Prepend a 0.
ÇÐƤ        Call the helper on each suffix,
Ẏ       concatenate the resulting lists of areas,
¹Ƈ     remove 0s,
Ṃ    and return the minimum.

• @alephalpha Right you are... puts the lie to the assumption that every column begins at most one maximal rectangle Feb 18, 2022 at 2:33
• ... never mind that [3,2,1] does too and this simply happens to be right on that one Feb 18, 2022 at 2:39

Doesn't work as intended... yet

# Husk, 16 bytes

▼M₁¹
*⁰▲mLfo=⁰▼Q


Try it online!

### Explanation

▼M₁¹    translates to ▼M₁⁰⁰
M₁⁰⁰   for each number in the input, call the second line with (each number N, the whole input A)
▼       take the minimum of the results

*⁰▲mLfo=⁰▼Q    translates to *⁰▲mLfo=⁰▼Q²
Q²   each contiguous sublist of A
fo=⁰▼     filter out the sublists where it's minimum value is N
mL          take the lengths
*⁰▲            multiply N with the maximum of the lengths

• 3 1 3 3 should return 3 Feb 18, 2022 at 13:57

# Wolfram Language (Mathematica), 52 bytes

aMin[SequenceCases[a,b_/;Min@b==#:>Tr[0b+#]]&/@a]


Try it online!

                                            /@a     for each height:
SequenceCases[a,b_          :>Tr[0b+#]]           areas of maximal rectangles
/;Min@b==#                          with that height
Min[                                           ]    smallest


# Haskell + hgl, 24 bytes.

nM(mn*×l)<(bn*^fgF^.ge)


In the interested of transparency, since hgl is under heavy development some features used in this answer were only merged into master recently. I wanted to make this answer to show them off.

## Explanation

There are two parts to this first is bn*^fgF^.ge this takes every element of the list and gives contiguous sections where all elements are above that height.

So for example [1,9,3,5,6,7,5]:

  [9]
[9]     [7]
[9]   [6,7]
[9] [5,6,7,5]
[9,3,5,6,7,5]
[1,9,3,5,6,7,5]


Note that there are some duplicates, e.g. [9] appears here several times. In addition they are not actually output in this order show here but this is fine for demonstration purposes.

Each list here represents the footprint of a box which cannot be widened. The height of that box is then the minimum element that appears in the footprint.

The second part is nM(mn*×l). This takes each element produced in the first step and multiplies its length by its minimum to get the size of the box. It takes the overall minimum as the result.

## Reflections

This feels a tad long, we have some really powerful tools here like nM and fgF, but we mostly get bogged down in other stuff. Unfortunately I have few thoughts on how this could be improved.