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:

  1. The water first rests atop of the highest terrain or water at that index.
  2. 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.
  3. 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:

  1. First, move left as far as possible by comparing the i-th element with i - 1-th element until height[i] >= height[i - 1], which means water cannot move left anymore. So the water-filled index should be i after the loop.
  2. Similarly, we check the right movement by comparing i-th element with i + 1-th element, and move right until the water cannot move right anymore.
  3. Then, we check if moving right has brought us back to the original index by comparing elements at i and i - 1. We keep moving left until height[i] will be greater than height[i - 1].
  4. 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.


TA 👨‍🏫