[Community Puzzle] Max Area

Puzzles
#1

Coding Games and Programming Challenges to Code Better

Send your feedback or ask for help here!

Created by @minhtan143,validated by @ChuckTheNinja,@NinjaFoxYT and @_NikJ.
If you have any issues, feel free to ping them.

#2

I am wondering if a solution better than Θ(n²) exists for this…
(Although not needed here, the dumb brute-force algo passes even in a slow language, as n is not too big in the tests.)

#3

Yes you can do a first iteration to identify the potential endpoints.
They form a decreasing subsequence.

Then you iterate over every possible startpoint and find its optimal corresponding endpoint with bisection.

It results in a O(n log n) algorithm.
Worst case would be an increasing then decreasing sequence like this:
1, 2, 3, … top - 1, top, top -1, …, 3, 2, 1.

2 Likes
#4

Could you say something more about your bisection method. I’ve been giving it a try to no avail.

Not really a spoiler but just in case.

For instance, for the big test I have as candidates (in the format (index, height)):
starts [(0, 316), (6, 337), (7, 469), (13, 490), (43, 493)]
ends [(99, 255), (93, 453), (69, 479), (43, 493)]
solution ((7, 469), (93, 453))

Now I found the solution by trying every combination, I don’t see how to binary search it, if that’s what you meant.

#5

This should work:

for each start s:
    binary search the bigger index i that meets the following: ends[i][1] >= s[1]

for each end e:
    binary search the smallest index i that meets the following: starts[i][1] >= e[1]

Edit : didn’t see that your ends list was reversed so you want to reverse it first.

2 Likes
#6

Took me longer than I’m willing to admit but it was quite fun. Thanks for the hints.

I shared it in case anyone wants to check it. I was testing a bit the performance and apparently it can pass this (worst case):

n = 1000000
arr = [i for i in range(1, n//2+1)] + [n//2-i for i in range(n//2)]

and this:

import numpy as np
n = 1000000
arr = [np.random.randint(2, n) for _ in range(n)]

Edit: I didn’t need to reverse it at the end.

2 Likes
#7

I published solution in C++ with time O(n). And algorithm is even simpler:

Start with leftId=0, rightId=n-1 and remember corresponding heights
while (leftId < rightId)
    calculate volume and check if is greater
    if left height is smaller than right height
        from leftId go right and find next bigger height
    else
        from rightId go left and find next bigger height
5 Likes
#8

Very elegant :slight_smile:

#9

Very nice indeed. I learned quite a bit with this puzzle. Thanks to everyone :+1:.

#10

Good puzzle!

I understood the description and the validators seem solid.