1) Brute Force Approach

The idea is to traverse every array element and find the highest bars on the left and right sides. Take the smaller of two heights. The difference between the smaller height and height of the current element is the amount of water that can be stored in this array element.

We will traverse the array from start to end, for every element we will find the maximum value from left and right and then take the minimum value and subtract that from the current height of the building. We will keep summing the values from first to last.

Pseudo Code:

maxwater(int arr[],int n):
    for (int i = 1; i < n-1; i++){ 
        // Find the maximum element on its 
        // left and keep it on left vaiable. 
        int left = arr[i]   
        for (int j=0; j<i; j++) 
            left = max(left, arr[j]); 
          
        // Find the maximum element on its 
        // right and keep it on right variable.   
        int right = arr[i]; 
        for (int j=i+1; j<n; j++) 
            right = max(right, arr[j]);  
         
        // keep updating values in res variable.     
        res = res + (min(left, right) - arr[i]);    
    }

• Time Complexity for above approach: O(n*n)
• space Complexity for above approach: O(1)

C++ Implementation:

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

int main()
{
    int t;
    cout << "Enter number of test cases: ";
    cin >> t;

    while (t--) {
        int n;
        cout << "Enter size of array: ";
        cin >> n;

        cout << "Enter number of elements: ";
        int arr[n];
        for (int i = 0; i < n; i++)
            cin >> arr[i];
        
        int sum = 0;
        for (int i = 1; i < n - 1; i++) {
            //initialise left temporary variable.
            int left = arr[i]; 
            //initialise right temporary variable.
            int right = arr[i]; 

            for (int j = 0; j < i; j++)
                left = max(arr[j], left); //find left maximum values.
            //int right=arr[i];
            for (int j = i + 1; j < n; j++)
                right = max(right, arr[j]); //find right maximum values.
            //take the amount of water it can hold and take summation.
            sum += (min(left, right) - arr[i]); 
        }
        cout << sum << "\n";
    }
    
    return 0;
}

Output

Enter number of test cases: 3
Enter size of array: 5
Enter number of elements: 4 5 6 2 3
1
Enter size of array: 6
Enter number of elements: 6 2 4 2 4 6
12
Enter size of array: 4   
Enter number of elements: 1 2 3 4
0

2) Efficient Approach

We will use precomputed values of height in two arrays left and right.

Initially left[0] value will be same as left[0]=arr[0] as there are no other element left of it and right[n-1] will be arr[n-1] as there is no other right element. For other elements we will take min(left[i],right[i])-arr[i] as the sum of water.

Pseudo Code:

maxwater(int arr[],int n):
    //left and right array declaration.
    left[n],right[n]
	
    //left[0]=arr[0] as there are no elements to left of it.
    left[0]=arr[0]
	    
    //right[n-1] =arr[n-1] as there is no elements.
    right[n-1]=arr[n-1]
 
    for(int i=1;i<n;i++)
        //iterate each element from index 1 to n-1 and 
        //keep checking left of it for maximum values.
        left[i]=max(left[i-1],arr[i])  

    for(int j=n-2;j>=0;j--)
        //iterate each element from index n-2 to 0 and 
        //keep checking right of it for maximum values.
        right[i]=max(right[i+1],arr[i])

    for(int i=0;i<n;i++)
        //keep summation of the maximum water values.
        sum+=((left[i]-right[i])-arr[i]) 

    return sum

• Time Complexity for above approach:  O(n)
• Space Complexity for above approach: O(n)

C++ Implementation:

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

typedef long long ll;

int main()
{
    ll t;
    cout << "Enter number of test cases: ";
    cin >> t;

    while (t--) {
        ll n;
        cout << "Enter size of array: ";
        cin >> n;

        ll arr[n];

        cout << "Enter array elements: ";
        for (ll i = 0; i < n; i++)
            cin >> arr[i];
        
        //declare array elements left and right.
        ll left[n], right[n]; 
        left[0] = arr[0];
        right[n - 1] = arr[n - 1];
        
        for (int i = 1; i < n; i++) {
            //take max of left values.
            left[i] = max(left[i - 1], arr[i]); 
        }
        for (int i = n - 2; i >= 0; i--)
            //take max of right values.
            right[i] = max(right[i + 1], arr[i]); 

        ll sum = 0;
        for (ll i = 1; i < n - 1; i++) {
            //take summation of maximum water amount of water.
            sum += (min(left[i], right[i]) - arr[i]); 
        }
        
        //print maximum amount of water.
        cout << sum << "\n";
    }
    
    return 0;
}

Output

Enter number of test cases: 3
Enter size of array: 5   
Enter array elements: 1 2 3 4 5
0
Enter size of array: 5
Enter array elements: 5 4 3 2 1
0
Enter size of array: 6
Enter array elements: 9 2 5 2 4 1
5