Given an array of integers representing walls, calculate the amount of water that would be trapped between walls and which two walls would contain the most amount of water.
Given the heights: 5, 3, 7, 2, 6, 4, 5, 9, 1, 2
Input: Array -> [5, 3, 7, 2, 6, 4, 5, 9, 1, 2]
Given the above input, between wall 3 and 8 we would find the most of amount of water. The amount of water trapped would be of size 11.
Output: Tuple -> [3, 8, 11]
Iterate over the array keeping track of a starting value. As you traverse the array keep track of every subsquent values that are lower than starting value. Stop when you hit a value that is greater than start or if the current value is greater than both previous and next values. Subtract each value that has been tracked from the lower of start and current value independtly. Then find the sum of the result of all of the subtraction operations. This is the amount of water trapped. Repeat the process starting at the current index. If at any point you hit a value greater than the previous ending value, recalculate the previous summation based on previous tracked values + new tracked values using this new value as your new ending value.
Since we will be travering the entire array once, the time complexity will be of O(n).
[5, 3, 7, 2, 6, 4, 5, 9, 1, 2]
| current | start | isLower | end | tracked values | notes | walls/water |
|---|---|---|---|---|---|---|
| 5 | 5 | - | - | - | - | - |
| 3 | 5 | true | - | [3] | - | - |
| 7 | 5 | false | 7 | [3] | (5 < 7) -> sum of 5 minus every tracked value | [1, 3, 2] |
| 7 | 7 | - | - | - | - | - |
| 2 | 7 | true | - | [2] | - | - |
| 6 | 7 | true | - | [2,6] | - | - |
| 4 | 7 | true | - | [2,6,4] | - | - |
| 5 | 7 | true | - | [2,6,4,5] | - | - |
| 9 | 7 | false | 9 | [2,6,4,5] | (7 < 9) -> sum of 7 minus every tracked value | [3, 8, 11] |
| 9 | 9 | - | - | - | - | - |
| 1 | 9 | true | - | [1] | - | - |
| 2 | 9 | true | 2(end of array) | [1] | (2 < 9) sum of 2 minus every tracked value | [8, 10, 1] |
Walls with greatest water between them: 3,8 with size 11.
const findGreatestWaterWalls = elevationMap => {
let start, end, tracked, previousTracked, calculated, waterWalls;
//iterate over the elevationMap array
// if at start of array or calculated is true
// set start equal to current value
// if current is greater than start and tracked length is greater than 1
//store sum of the subtraction of each tracked value from the lower of start and end
//set calculated to true
//set previous tracked equal tracked
//clear tracked
// if current is less than start
//push current to tracked
//sort waterWalls array by largest water size
//return the largest water walls
}