How can I find the maximum element in the left and right sides of an array?

Question

I have a homework problem in C++ that I could (and did) solve, but not fast enough.

So the problem goes like this: On a platform, there are n bars of equal width and height. It starts raining. Find out the quantity of water that fits in between the bars (Very bad enunciation , I know, it's better to look at the example). Examples:

n = 6
bar lengths = {3, 0, 0, 2, 0, 4}
Answer would be = 10

The cubes of water would "fill out" the empty space between the bars and I need the find the number of cubes:

Explanation:

Another example:

n = 12
bar lengths = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1}
Answer = 6

What I tried:

For each spot in the array, I found the maximum height bar to the left of it and to the right of it and then I "filled" this spot with the minimum between the maximum to the left and the maximum to the right minus the height of the bar at the present spot:

#include <iostream>

using namespace std;

int main() {
    int n, a[100001], i, j, volume=0, max_left, max_right;
    cin >> n;

    // Input the array

    for (i=0; i<n; i++) {
        cin >> a[i];
    }

    // For each element (except the first and last)

    for (i=1; i<(n-1); i++) {

        max_left = max_right = a[i];

        // Find the maximum to the left of it and to the right of it

        for (j=0; j<i; j++) {
            if (a[j] > max_left) {
                max_left = a[j];
            }
        }

        for (j=(i+1); j<n; j++) {
            if (a[j] > max_right) {
                max_right = a[j];
            }
        }

        // The quantity of water that fits on this spot is equal to
        // the minimum between the maxes, minus the height of the
        // bar in this spot

        volume += (min(max_left, max_right) - a[i]);
    }
    cout << volume;
    return 0;
}

The solution is good, I get the corrent results. But the speed is a problem. I believe the complexity of this solution is O(n^2), if I'm not mistaken. Now the problem has to be solved in O(n). The problem is: How can I find the maxes in both directions for each element in O(n)? Any help will be appreciated. Thanks!

Answer 1

1. Find the highest bar in the complete list. This gives to sub-ranges Before and After (both excluding the highest bar).
2. Iterate over both sub-ranges (front to back for Before, back to front for After): Remember the highest bar you've found on the way, starting with 0. Add the difference of the current height to the result.
3. Add both results.

This works because once you've found the overall maximum height, all other heights for Front and Back are at least lower or equal than the maximum. This way you can skip searching in both directions and simply use the highest bar you've met so far.

Both steps are O(n). Here is an example:

#include <algorithm>
#include <cassert>
#include <iostream>
#include <numeric>
#include <vector>

template <typename First, typename Last>
int calcRange(First begin, Last end) {
  int max{0};
  int result{0};
  for (auto it = begin; it != end; ++it) {
    const auto current = *it;
    result += std::max(0, max - current);
    max = std::max(max, current);
  }
  return result;
}

int calc(const std::vector<int>& bars) {
  if (bars.size() <= 1) return 0;

  // find max = O(n)
  const auto maxIt = std::max_element(bars.cbegin(), bars.cend());
  assert(maxIt != bars.cend());

  // calculate left and right = O(n)
  const auto l = calcRange(bars.cbegin(), maxIt);
  const auto r = calcRange(bars.crbegin(), std::make_reverse_iterator(maxIt));

  return l + r;
}

int main() {
  std::cout << calc({3, 0, 0, 2, 0, 4}) << std::endl;
  std::cout << calc({0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1}) << std::endl;
}

Answer 2

I have to say, that I really liked this question.

This might give you an idea on how to solve this question. Basically, you are looking to leftmost and rightmost bar heights. Then you will raise the waterlevel to the minimum of both and compute the amount of water needed for this. Afterwards you can shrink the bars array and repeat the process.

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>

int main() {
    std::vector<int> bars{ 3, 0, 0, 2, 0, 4 };
    int waterCounter = 0;
    int waterLevel = 0;
    auto leftIter = bars.begin();
    auto rightIter = bars.end() - 1;
    while (true)
    {
        if (leftIter == rightIter) break;
        auto newWaterLevel = std::min(*leftIter, *rightIter);
        if (newWaterLevel > waterLevel)
        {
            auto newRight = std::next(rightIter);
            auto size=std::distance(leftIter, newRight);

            auto waterInGaps = 0;
            for (auto iter=leftIter; iter!=newRight; iter++ )
            {
                waterInGaps += *iter > newWaterLevel ? 0 : newWaterLevel-*iter;
                *iter = *iter>newWaterLevel?*iter:newWaterLevel;
            }
            waterCounter += waterInGaps;
        }
        while (leftIter!=rightIter)
        {
            if (*leftIter > newWaterLevel) break;
            std::advance(leftIter, 1);      
        }
        while (rightIter!=leftIter)
        {
            if (*rightIter > newWaterLevel) break;
            std::advance(rightIter, -1);
        }
        waterLevel = newWaterLevel;
    }
    std::cout << waterCounter << std::endl;
    return EXIT_SUCCESS;
}