Rain Water problem solved in python

abhinav5481 commented 3 years ago

Related Issue:

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much waterContent it is able to trap after raining.

Closes: #254

Describe the changes you've made

Logic: An element of the array can store waterContent if there are higher bars on left and right. The amount of waterContent to be stored in every element can be found out by finding the heights of bars on the left and right sides.

Approach: Traverse the element of the array one by one and find the largest element on the left as well as on the right-hand side. The difference between the smaller of two sides & the current element would give the amount of waterContent stored.

Algorithm:

Create two array left and right of size n. Initialize the waterContent to 0.
To fill the left array run a loop in the arr from index 1 to n. Initialize the first element of the left array to the first element of arr ( since the first element would be the largest for itself)
fill the elements of the left array with maximum values between its left element & itself.
Similarly, fill the right array by initializing the last element of the right array with the last element ofarrand traversingarr` from n-2 to start.
Finally the water content for i'th element would be calculated by: waterContent = min(left[i], right[i]) - arr[i] . Summing the content for each element would give the total amount of water stored.

Type of change

[ ] Bug fix (non-breaking change which fixes an issue)
[x] New feature (non-breaking change which adds functionality)
[x] Code style update (formatting, local variables)
[ ] Breaking change (fix or feature that would cause existing functionality to not work as expected)
[x] This change requires a documentation update

How Has This Been Tested?

It has been tested on my local machine.

Describe if there is any unusual behaviour of your code(Write `NA` if there isn't)

Na

Checklist:

[x] My code follows the style guidelines of this project.
[x] I have performed a self-review of my own code.
[x] I have commented my code, particularly in hard-to-understand areas.
[x] I have made corresponding changes to the documentation.
[x] My changes generate no new warnings.
[x] I have added tests that prove my fix is effective or that my feature works.
[x] New and existing unit tests pass locally with my changes.

Screenshots

Original	Updated
original screenshot	updated screenshot

Please review my code & let me know if any further changes are required.

ankitapuri commented 3 years ago

rest all i good to go but kindly take user input

abhinav5481 commented 3 years ago

Done.

ankitapuri / DSA-guide