Given

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

Given

Given

`[0,1,0,2,1,0,1,3,2,1,2,1]`

, return `6`

.
The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped

**Solution:**

Simple approach is to find rightmax and leftmax of every element and determine the excess water, it can be calculated by formula:

**trap_water_on_current_bar = min(leftmax, rightmax) - current_value**

**Implementation:**

`int`

`findWater(`

`int`

`arr[], `

`int`

`n)`

`{`

` `

`int`

*max_`left = new int[n] ;`

` `

`int`

*max_`right = new int[n];`

` `

`int`

`water = 0;`

` `

`// Fill left array`

` `

`left[0] = arr[0];`

` `

`for`

`(`

`int`

`i = 1; i < n; i++)`

` `

`left[i] = max(left[i-1], arr[i]);`

` `

`// Fill right array`

` `

`right[n-1] = arr[n-1];`

` `

`for`

`(`

`int`

`i = n-2; i >= 0; i--)`

` `

`right[i] = max(right[i+1], arr[i]);`

` `

`// Calculate the accumulated water element by element`

` `

`// consider the amount of water on i'th bar, the`

` `

`// amount of water accumulated on this particular`

` `

`// bar will be equal to min(left[i], right[i]) - arr[i] .`

` `

`for`

`(`

`int`

`i = 0; i < n; i++)`

` `

`water += min(left[i],right[i]) - arr[i];`

` `

`return`

`water;`

`}`

Source:- LeetCode, GeeksForGeeks

can u post some Tic-tac-toe related interview Question???

ReplyDeleteI prefer to read this kind of stuff. The quality of content is fine and the conclusion is good. Thanks for the post

ReplyDeletewindows blinds suppliers in india