42. trapping-rain-water.cpp

Putting code in C++ for problem 42.trapping-rain-water problem

1. For every element we can precalculate and store the highest bar on the left and on the right (say stored in arrays left[] and right[]).
2. Then iterate the array and use the precalculated values to find the amount of water stored in this index, which is the same as ( min(left[i], right[i]) – arr[i] )

Follow the steps mentioned below to implement the approach:

1. Create two arrays left[] and right[] of size N. Create a variable (say max) to store the maximum found till a certain index during traversal.
2. Run one loop from start to end:
3. In each iteration update max and also assign left[i] = max.
4. Run another loop from end to start:
5. In each iteration update max found till now and also assign right[i] = max.
6. Traverse the array from start to end.
7. The amount of water that will be stored in this column is min(left[i], right[i]) – array[i]
8. Add this value to the total amount of water stored
9. Print the total amount of water stored.

test cases : // test case 1 // height = [0,1,0,2,1,0,1,3,2,1,2,1] // output = 6

// test case 2 // height = [4,2,0,3,2,5] // output = 9

Complexity Analysis:

Time Complexity: O(N). Only one traversal of the array is needed, So time Complexity is O(N). Space Complexity: O(N). Two extra arrays are needed, each of size N.

I can tell this is your first pull request! Thank you I'm so honored. :tada::tada::tada: I'll take a look at it ASAP!

@anandfresh please suggest me changes in this pull request .

now i updated the file. now it will pass the checks.

can you help me with some changes what changes should i do to it