Problem Description
You are given an elevation map represented by an integer array, where heights[i] represents the height of the terrain at index i. A total of volume water units are dropped one-by-one at index k. Each droplet first lands at index k then may flow left or right according to these rules: if moving left eventually reaches a lower level than the current one, the droplet flows left; if not, it checks the right direction for a similar drop; otherwise, it stays at index k. The goal is to simulate this process and output the final state of the elevation map with water included.
Key Insights
- Simulate the process for each water droplet individually.
- Search to the left from k for the first index where the droplet can settle by finding a lower height (considering both terrain and water).
- If no valid left move is found, search to the right.
- If neither direction provides a lower location, deposit the droplet at index k.
- Repeat the process for all volume droplets, updating the heights array accordingly.
Space and Time Complexity
Time Complexity: O(volume * n), where n is the length of the heights array. Space Complexity: O(1) extra space (in-place simulation).
Solution
We simulate each water droplet as it falls. For each droplet, we first try to move left from the starting index k. While moving left, if the adjacent cell is lower than the current cell, we continue; if a cell higher than the previous is encountered, we break the loop. If a lower cell is found along the way, the water droplet settles there. If not, we then try moving right with a similar approach. If neither move is possible, the droplet settles at k. Updating the heights array for each droplet results in the final water distribution.