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

Thanks a lot everyone, your ideas helped! As I am not that advanced, I couldn't (and didn't really know how to) use vectors, auto (this one seems like magic to me), templates and other things. If anyone is still interested, this is the code I used and I got 100 points on the site:

#include <iostream>

using namespace std;

int main()
{
    int n, a[100001], left_max[100001], right_max[100001];
    int i, max_to_right, max_to_left, volume=0;

    cin >> n;

    for (i=0; i<n; i++) {

        // Input the array

        cin >> a[i];

        // Directly find the "maximum to the left" of each element

        if (i == 0) {
            left_max[i] = max_to_left = a[i];
        }
        else {
            if (a[i] > max_to_left) {
                max_to_left = a[i];
            }
            left_max[i] = max_to_left;
        }
    }

   // Not the only thing left is to find the "maximum to the right" of each element

    for (i=(n-1); i>=0; i--) {
        if (i == (n-1)) {
            right_max[i] = max_to_right = a[i];
        }
        else {
            if (a[i] > max_to_right) {
                max_to_right = a[i];
            }
            right_max[i] = max_to_right;
        }

        // No need to have another loop afterwards, add to volume as we go

        if (i>0 && i<(n-1)) {
            volume += (min(left_max[i], right_max[i]) - a[i]);
        }

    }

    cout << volume;

    return 0;
}

I basically did the same thing, but faster. I found the maximum to the right and to the left of each element, but I found the maximum to the left of each element while reading the input and then with another loop I found the maximum of each element, but to the right. The website had a very similar solution, just a bit shorter.

Answer 2

Let's try a different approach. We can do this in a single pass from left to right, except for a special case at the end of the array.

Consider that we're iterating from left to right, keeping track of what's the current water level. Each of these scenarios can happen:

• We reached a column that is higher than the water level;
• We reached a column that is lower than the water level;
• We reached a column that has the same height as the water level;

The first one defines a new water level. For the two others, notice that to count the blocks, all we need to do is add water_level - height to the current total.

This will only cause a problem once we reach the end. Consider this input, for instance:

{2, 0, 0, 3, 0, 0}

Notice that the water level on the two last items should be 0, but we have just set it to 3! To fix this, we simply discard the result of the last iteration (from 3 to the end) and do a reverse iteration from the end to that point.

If this all sounds a bit tricky, you will see that the implementation is actually quite simple. Following is what I came up with: It uses some recursion to simplify things, and works on any pair of iterators:

#include <iterator> // std::reverse_iterator

template<typename It>
int pass(It begin, It end) {
    if (end - begin <= 1) return 0;
    int result = 0;
    auto it = begin;
    while(++it != end) {
        // We keep track of the current water level by simply querying the begin iterator.
        if (*it <= *begin) {
            result += *begin - *it;
        } else {
            // We need to define a new water level. Let's just do a new pass, with the begin pointing to the new column.
            return result + pass(it, end);
        }
    }
    // If we got here, it means we reached the end. We should discard the result, and do a reverse pass instead
    return pass(std::reverse_iterator(end), std::reverse_iterator(begin));
}

Use it like this:

int main() {
    std::vector<int> v{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
    std::cout << pass(v.begin(), v.end());
}
// Output: 6

Answer 3

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 4

I would start off by asking off a few questions which would get me close to a solution. Think of it this way, if you poured water into the structure above, the empty spots would only ever accumulate to the right or the left of the 'Highest bar'. Once you have that insight, now from left to the highest bar do the following, currbar_from_left = -1 and the current value set to start of the array.

1- if the currbar_from_left > current then currbar_from_left = current

• else ans = ans + (currbar - currbar_from_left) - add the difference to the answer since we know definately that this would accmulate compared to our anchor point(the highest bar)

2- now do another traversal, this time from right of the array to the highest point. currbar_from_right = -1 and current set to the last value in the array

• if the currbar_from_right > current then currbar_from_right = current
• else ans = ans + (currbar - curbar_from_right)

3- The ans is now the total empty cubes.

You could combine steps 1 and 2 into a single loop with the conditions as they are but the above algorithm is more clear in terms of understanding.

The following code demostrates this:

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];
    }

    // Maximum height in the array
    int maximum_bar = -1, maximum_index = -1;
    for (i = 0; i < n; i++) {
        if (a[i] > maximum_bar)
        {
            maximum_bar = a[i];

            // where did i see it?
            maximum_index = i;
        }
    }

    //Left search, to the maximum_bar
    int left = -1;
    for (i = 0; i < maximum_index; i++) {
        if (a[i] > left) left = a[i];
        else volume = volume + (left - a[i]);
    }


    //Right search, to the maximum_bar
    int right = -1;
    for (i = n - 1; i >= maximum_index; i--) {
        if (a[i] > right) right = a[i];
        else volume = volume + (right - a[i]);
    }


    cout << volume;
    return 0;

Answer 5

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;
}