dhurva challenge (hackerearth)

WATER LOGGING BETWEEN THE BUILDINGS

question link

Andrew has recently moved to Wengaluru. He finds this city amazing as all the buildings of the city are of same shape. There are N buildings in a row with no space in between. Buildings may have different heights while width in other two dimensions is always 1 unit.

Rain occurs very frequently in Wengaluru so Andrew being the curious boy thought that if the entire city is flooded with water then How much water would be collected between the buildings? Water would be collected between the buildings if a small sized building occurs between 2 big sized building i.e. if a building with small height occurs between buildings of relatively larger height.

Input
The first line contains T, the number of test cases.
Each test case consist of 2 lines. First line of each test case Would contain N- total no. of buildings in the city. Second line contains N integers, the height of N buildings.

Output
For each test case output the answer to the above query. As the total water collected between the buildings could be a huge number so output your answer by taking Modulus with 10^9+7(1000000007).

2
5
3 2 1 4 5
5
1 2 3 4 5

solution

1. /*
2. I Will Win Not Immediately But Definitely.. -Aniruddha Sharma
3. */
5. // Name:- Aniruddha Sharma
7. // Problem:- Andrew and Wengaluru City
9. // Site:- HackerEarth
11. #include<iostream>
12. #include<map>
13. #include<vector>
14. #include<iostream>
15. #include<algorithm>
16. #include<cstring>
17. #include<cstdio>
18. #include<cmath>
19. #include<functional>
20. #include<vector>
21. #include<stack>
22. #include<set>
23. #include<map>
24. #include<queue>
25. #include<deque>
26. using namespace std;
27. long long arr[100010],left_max[100010],right_max[100010];
28. int totalWaterFilled(int n)
29. {
30. long long i,ans=0;
31. left_max[0]=arr[0];
32. for(i=1;i<n;i++)
33. {
34. if(arr[i]>left_max[i-1])
35. left_max[i]=arr[i];
36. else
37. left_max[i]=left_max[i-1];
38. }
40. right_max[n-1]=arr[n-1];
41. for(i=n-2;i>=0;i--)
42. {// finding the rightmost and left most building whichever is bigger was the most important task
43. if(arr[i]>right_max[i+1])
44. right_max[i]=arr[i];
45. else
46. right_max[i]=right_max[i+1];
47. }
48. // now the only tast left is too see when a buling get a water logging or not and how much it gets ( that is equal to the smaller of the big buildings (right or left) to it)

1. for(i=1;i<=n-2;i++)
2. {
3. if((min(left_max[i-1],right_max[i+1])-arr[i])>0)
4. ans=(ans+(min(left_max[i-1],right_max[i+1])-arr[i]))%1000000007;
5. }
6. return ans;
7. }
8. int main()
9. {
10. int t;
11. cin>>t;
12. while(t--)
13. {
14. int n;
15. cin>>n;
16. for(int i=0;i<n;i++)
17. cin>>arr[i];
18. cout<<totalWaterFilled(n)<<endl;
19. }
20. return(0);
21. }