Two peaks

See the original problem on HackerRank.

Solutions

A brute force solution to this problem involves checking every possible pair of numbers in the array and calculating their product. To do this, we use two nested loops: the outer loop selects the first number, and the inner loop selects the second number, which comes after the first. For each pair, we compute the product and check if it exceeds the current maximum product found. This approach guarantees finding the pair with the highest product, but it is inefficient because it examines all pairs, resulting in a quadratic time complexity.

To find the area efficiently, we can use a two-pointer greedy approach: one at the start and one at the end of the array. The area between the two lines is determined by the shorter line and the distance between them.

At each step, the function calculates the area, then moves the pointer pointing to the shorter line inward. This is because the area is determined by the shorter line. If the left line is shorter, moving it rightward may find a taller line, potentially increasing the area. If the right line is shorter, moving it leftward could also find a taller line. Moving the taller line doesn’t help because it doesn’t increase the minimum height, which limits the area. By always moving the pointer pointing to the shorter line, we efficiently explore possible pairs that could yield a larger area. The process continues until the pointers meet. This approach ensures the solution is found in linear time.

Here is an implementation in C++:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

int n;
cin >> n;
vector<int> heights(istream_iterator<int>(cin), {});

auto out = 0;
auto i=0ul, j=heights.size()-1;
while (i != j)
{
    const auto height = min(heights[i], heights[j]);
    const int base = j-i;
    out = max(out, base*height);
    if (heights[i] < heights[j])
    {
        ++i;
    }
    else
    {
        --j;
    }
}

cout << out;

Here is the same in Python:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

n = int(input())
heights = list(map(int, input().split()))

out = 0
i, j = 0, len(heights) - 1
while i != j:
    height = min(heights[i], heights[j])
    base = j - i
    out = max(out, base * height)
    
    if heights[i] < heights[j]:
        i += 1
    else:
        j -= 1

print(out)