2
\$\begingroup\$

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
For complete description, please go to this link.

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){

    // Your code here
    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];
        
        //adding elements to the array
        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?

\$\endgroup\$
2
\$\begingroup\$

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){

    // Your code here
    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];
        
        //adding elements to the array
        for(int i =0; i<arrSize; i++){
            std::cin >> arr[i];            
        }
        
        //calling trappingWater() function
        std::cout << trappingWater(arr, arrSize) << std::endl;
        
    }
    
    return 0;
}  // } Driver Code Ends
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.