Unit of water trapped on the map

You are given an array of non-negative integers that represents a two-dimensional elevation map where each element is the unit-width wall and the integer is the height. Suppose it will rain and all spots between two walls get filled up.

Compute how many units of water remain trapped on the map in O(N) time and O(1) space.

For example, given the input [2, 1, 2], we can hold 1 unit of water in the middle.

Given the input [3, 0, 1, 3, 0, 5], we can hold 3 units in the first index, 2 in the second, and 3 in the fourth index (we cannot hold 5 since it would run off to the left), so we can trap 8 units of water.

Example:

Input:  height = {3,0,1,3,0,5}
Output: 8

Approach

C++

#include <bits/stdc++.h>
using namespace std;

int trap(vector<int> &height)
{
    if (height.size() <= 2)
        return 0;
    vector<int> left(height.size());
    vector<int> right(height.size());

    left[0] = height[0];
    right[right.size() - 1] = height[height.size() - 1];

    //find left height for all the indices
    for (int i = 1; i < right.size(); i++)
    {
        left[i] = max(height[i], left[i - 1]);
    }

    //find the right height of all the indices
    for (int i = right.size() - 2; i >= 0; i--)
    {
        right[i] = max(height[i], right[i + 1]);
    }
    int water = 0;

    //find the total water collected
    for (int i = 0; i < right.size(); i++)
    {
        water += max(min(right[i], left[i]) - height[i], 0);
    }
    return water;
}

int main()
{
    vector<int> height = {3, 0, 1, 3, 0, 5};

    cout << trap(height);

    return 0;
}