# Geeks for Geeks: Trapping Rain Water Problem - time limit exceeded

Problem Statement:
Given an array arr[] of N non-negative integers representing the height of blocks. If width of each block is 1, compute how much water can be trapped between the blocks during the rainy season.

Input:
N = 6
arr[] = {3,0,0,2,0,4}
Output: 10

My Code:

// { Driver Code Starts
#include<bits/stdc++.h>

using namespace std;

// } Driver Code Ends

// function to find the trapped water in between buildings
// arr: input array
// n: size of array
int maxValueInArray(int arr[], int start, int end){
if(start == end) return arr[start];
int mx = 0;
for(int i = start; i<=end; i++){
mx = max(arr[i], mx);
}
return mx;

}
int trappingWater(int arr[], int n){

int ans = 0;
for(int i = 1; i<n-1; i++){
int curr = arr[i];
int maxLeft = maxValueInArray(arr,0, i-1);
int maxRight = maxValueInArray(arr, i+1, n-1);
if(maxLeft == curr || maxRight == curr) ans += 0; // 8, 8, 3
else if(maxLeft >= curr && curr >= maxRight) ans += 0; //8, 5, 3
else if(maxLeft <= curr && curr <= maxRight) ans+= 0; //2, 4, 7
else if(maxLeft < curr && curr > maxRight) ans+= 0; //5, 7, 6
else ans += min(maxLeft, maxRight) - arr[i];
}
return ans;
}

// { Driver Code Starts.

int main(){

int t;
//testcases
cin >> t;

while(t--){
int n;

//size of array
cin >> n;

int a[n];

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

//calling trappingWater() function
cout << trappingWater(a, n) << endl;

}

return 0;
}  // } Driver Code Ends


Issue:
I'm unable to understand why I'm getting a time exceeded error in this code. Can somebody tell what's going wrong?

Your current solution is $$\ O(n^2) \$$ because of the nested loops.

There are a couple ways to solve this in $$\ O(n) \$$ time without having to use any extra arrays. One way is to go from left-to-right while keeping track of the highest wall you’ve seen so far, then do the same thing from right-to-left until you reach the last highest wall you saw when going left-to-right. It’s $$\ O(n) \$$, but you‘ll need to look at almost every array index twice if the wall at index 0 is the highest.

The other way is to alternate between going from left-to-right or right-to-left depending on which side had the last highest wall seen. If you do it like this then you’ll always only need to look at each index one time. You can write the function like this:

int trappingWater(int arr[], int arr_size)
{
if (arr_size <= 0)
{
return 0;
}

int water = 0;

int max_left = arr[0];
int max_right = arr[arr_size - 1];

int left_ind = 0;
int right_ind = arr_size - 1;

while (left_ind < right_ind - 1)
{
if (max_left <= max_right)
{
left_ind += 1;
if (arr[left_ind] > max_left)
{
max_left = arr[left_ind];
}
else
{
water += max_left - arr[left_ind];
}
}
else
{
right_ind -= 1;
if (arr[right_ind] > max_right)
{
max_right = arr[right_ind];
}
else
{
water += max_right - arr[right_ind];
}
}
}
return water;
}


For your current code, it would be better if you avoided using namespace std; to avoid possible name conflicts: https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice. You could also use better variable names in some places. There are some spots where you explain what the variable is in a comment right after making the variable. Instead of doing that, you could just give the variable a more complete name. Then you don’t have to check the comment if you forget what it is. Here’s what your current code would look like with those two things in mind:

int maxValueInArray(int arr[], int start, int end){
if(start == end) return arr[start];
int maxHeight = 0;
for(int i = start; i<=end; i++){
maxHeight = std::max(arr[i], maxHeight);
}
return maxHeight;

}

int trappingWater(int arr[], int arrSize){

int ans = 0;
for(int i = 1; i<arrSize-1; i++){
int currentWall = arr[i];
int maxLeft = maxValueInArray(arr,0, i-1);
int maxRight = maxValueInArray(arr, i+1, arrSize-1);
if(maxLeft == currentWall || maxRight == currentWall) ans += 0; // 8, 8, 3
else if(maxLeft >= currentWall && currentWall >= maxRight) ans += 0; //8, 5, 3
else if(maxLeft <= currentWall && currentWall <= maxRight) ans+= 0; //2, 4, 7
else if(maxLeft < currentWall && currentWall > maxRight) ans+= 0; //5, 7, 6
else ans += std::min(maxLeft, maxRight) - arr[i];
}
return ans;
}

// { Driver Code Starts.

int main(){

int testCases;
std::cin >> testCases;

while(testCases--){
int arrSize;

std::cin >> arrSize;

int arr[arrSize];