Problem: Practice/Adhoc/Rain_water_harvesting

#1

Hi forum,
Can anyone please help me debug my code, i have a time-limt exceeded in one case.
Here’s the code:

#include<iostream>
#include<cassert>
using namespace std;

// function to get count of water that can be filled beteen location i and j 
void get_intermed_elmnt(int i,int j,int *arr, int *count){
    assert(arr[i] == arr[j]);
    int val = arr[i];
    for(int k=i;k<j;k++){
        *count += (val-arr[k]);
    }
}

// function to trim off global maximum
void trim_glob_max(int *arr, int arr_len){
    int max = 0;
    int  count,ptr = 0;
    for(int i=0; i<arr_len ; i++){
        count += (max == arr[i])?1:0;
        if(max < arr[i]){
            count = 0;
            max = arr[i];
            ptr = i;
        }
    }
    if(count > 1) return;
    else{
        assert(max == arr[ptr]);
        arr[ptr] -= 1;
        trim_glob_max(arr,arr_len);
        return;
    }
}

int main() {
    int a = 0;
    cin >> a;
    int *arr = new int[a];
    int count = 0;
    for(int i=0;i<a;i++)cin>>arr[i];

    trim_glob_max(arr,a);

    for(int i=0;i<a;){
        if((a-i)==2) break;
        for(int j=i+1;j<a;j++){
            if(arr[j]<arr[i]) { continue;}
            else{
                if((j-i)==1){ 
                    i=j;
                    break;
                }
                get_intermed_elmnt(i,j,arr,&count);
                i = j;
                break;
                
            }
        }
    }
    cout<<count;
}
#2

In worst case, your code runs in O(n^3), so quite qualifiable for a TLE verdict. It can be solved in O(n).

    int main() {
        int n, ans=0;
        cin >> n;
        int a[n],left[n],right[n];
        for(int i=0; i<n; cin >> a[i++]);
        left[0] = a[0]; right[n-1] = a[n-1];
        for(int i=1; i<n; left[i]=max(a[i], left[i-1]), ++i);
        for(int i=n-2; i>=0; right[i]=max(a[i], right[i+1]), --i);
        for(int i=0; i<n; ans += (min(left[i], right[i])-a[i]), ++i, (i==n)?cout<<ans<<endl:cout<<"");
    }