Leetcode 755. Pour Water
Problem Description
Given an array of nonnegative integers heights[i]
representing the height of the terrain at the index i
. The width at each index is 1. After V
units of water are poured at a certain index K
, we are asked to determine how much water is at each index after the water flows.
When water is poured at an index, it adheres to the following rules:
- The water first rests atop of the highest terrain or water at that index.
- It flows towards the direction where it would eventually go down to a lower level. If moving left makes the water to go to a lower level, then it moves left. And similarly, if moving right lets the water down, then it moves right.
- If both left and right directions don't let the water down, it stays at its current position.
Also, it is assumed that there's infinitely high terrain on the two sides outside of the array's bounds. Furthermore, each unit of water must be in precisely one block; water will not be spread evenly across multiple blocks.
Approach
The logic of this problem is to keep pouring water on the given terrain (array) until there are no more units of water left. We use three pointers/indices: k
, i
and j
, where k
index at which we want to pour the water. While we pour the water, we:
- First, move left as far as possible by comparing the
i
-th element withi - 1
-th element untilheight[i] >= height[i - 1]
, which means water cannot move left anymore. So the water-filled index should bei
after the loop. - Similarly, we check the right movement by comparing
i
-th element withi + 1
-th element, and move right until the water cannot move right anymore. - Then, we check if moving right has brought us back to the original index by comparing elements at
i
andi - 1
. We keep moving left untilheight[i]
will be greater thanheight[i - 1]
. - Finally, we increment the water level at index
i
by 1.
This process must be repeated until all the units of water have been poured.
Python Solution
1 2python 3class Solution: 4 def pourWater(self, heights, V, k): 5 while V: 6 i, dist, d = k, [-1, 1], [0, 0] 7 for j in range(2): 8 while 0 <= i + dist[j] < len(heights) and heights[i] >= heights[i + dist[j]]: 9 if heights[i] > heights[i + dist[j]]: 10 d[j] = dist[j] 11 i += dist[j] 12 i = k + d[d[0] < d[1]] 13 heights[i] += 1 14 V -= 1 15 return heights
Java Solution
1 2java 3class Solution { 4 public int[] pourWater(int[] heights, int V, int K) { 5 for (int i = 0; i < V; i++) { 6 int j = K; 7 while (j > 0 && heights[j - 1] <= heights[j]) j--; 8 while (j < K && heights[j] <= heights[j + 1]) j++; 9 heights[j]++; 10 } 11 return heights; 12 } 13}
JavaScript Solution
1 2java 3class Solution { 4 pourWater(heights, V, k) { 5 for (let _ = 0; _ < V; _++){ 6 let cur = k; 7 while (cur > 0 && heights[cur - 1] <= heights[cur]) 8 cur--; 9 while (cur < heights.length - 1 && heights[cur] >= heights[cur + 1]) 10 if (heights[cur] > heights[cur + 1]) 11 break; 12 else 13 cur++; 14 while (cur > k && heights[cur - 1] === heights[cur]) 15 cur--; 16 heights[cur]++; 17 } 18 return heights; 19 } 20};
C++ Solution
1 2cpp 3class Solution { 4public: 5 vector<int> pourWater(vector<int>& heights, int V, int K) { 6 while (V-- > 0) { 7 int i = K, j = K; 8 while (i > 0 && heights[i - 1] <= heights[i]) i--; 9 while (j + 1 < heights.size() && heights[j + 1] <= heights[j]) j++; 10 heights[(heights[i] <= heights[j]) ? i : j]++; 11 } 12 return heights; 13 } 14};
C# Solution
1 2csharp 3public class Solution { 4 public int[] PourWater(int[] heights, int V, int K) { 5 while (V-- > 0) { 6 int i = K, j = K; 7 while (i > 0 && heights[i] >= heights[i-1]) i--; 8 while (j < heights.Length-1 && heights[j] >= heights[j+1]) j++; 9 if (heights[j] < heights[i]) i = j; 10 heights[i]++; 11 } 12 return heights; 13 } 14}
Overall, the problem demands an understanding of how water would flow on a terrain and implementing that via programming. Thus, using the above solutions, one could easily solve this problem across multiple languages.# Conclusion
This problem is an interesting application of applying simple physical properties of water to the realm of computer algorithms. The solution is quite intuitive once the behavior of water is clearly understood - water flows towards the lowest level possible.
Python, Java, JavaScript, C++, and C# are some of the most popular coding languages and our solution covers them all. Though the syntax and specific method of implementation may vary based on the language used, the crux of the logic remains the same across all languages.
This problem also showcases the power of programming in simulating real-world phenomena and understanding them better. The solutions provided here can be used as a starting point to further explore and model the movement of water on complex terrain, potentially leading to more accurate and powerful simulation tools for geologists and climate scientists.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.