Practice/Google/Leetcode 755. Pour Water

Leetcode 755. Pour Water

CodingMust

Problem

You are given an elevation map representing terrain heights as an array of non-negative integers. Water droplets are poured onto this terrain one at a time at a specific position. Each droplet follows these movement rules:

1. The droplet starts at the pour position
2. It first attempts to flow left, moving to adjacent positions with strictly lower height
3. Among all reachable positions to the left, it settles at the leftmost position with the minimum height
4. If no lower position exists to the left, the droplet attempts to flow right using the same logic
5. If neither left nor right has a lower position, the droplet settles at the pour position
6. Once settled, the height at that position increases by 1

Simulate the pouring of all droplets and return the final terrain heights.

Requirements

1. Process droplets one at a time in sequence
2. For each droplet, scan left first for the optimal settling position
3. Only scan right if no suitable left position exists
4. A droplet can only move to adjacent positions with strictly lower height
5. Among positions with equal minimum height, choose the leftmost one
6. Update the terrain height immediately after each droplet settles

Constraints

• 1 ≤ heights.length ≤ 100
• 0 ≤ heights[i] ≤ 99
• 0 ≤ drops ≤ 100
• 0 ≤ pour_at < heights.length

Examples

Example 1:

` Input: heights = [2, 1, 1, 2, 1, 2, 2], drops = 4, pour_at = 3 Output: [2, 2, 2, 2, 1, 2, 2] Explanation:

• Drop 1: Pours at index 3 (height 2), flows left to index 1 (height 1), settles there → [2, 2, 1, 2, 1, 2, 2]
• Drop 2: Pours at index 3 (height 2), flows left to index 2 (height 1), settles there → [2, 2, 2, 2, 1, 2, 2]
• Drop 3: Pours at index 3 (height 2), can't flow left (all ≥ 2), can't flow right (height 1 but blocked by height 2), settles at pour position → [2, 2, 2, 3, 1, 2, 2]
• Drop 4: Similar to drop 3 → [2, 2, 2, 4, 1, 2, 2] Wait, recalculating: after first two drops fill left valley, subsequent drops should check both directions properly. Actually: [2, 2, 2, 2, 1, 2, 2] means the first 3 drops filled indices 1, 2, and 3 to height 2 each, making them level. `

Example 2:

Input: heights = [3, 1, 3], drops = 5, pour_at = 1 Output: [3, 6, 3] Explanation: All 5 droplets pour directly into the valley at index 1, which is already the lowest point. The height increases from 1 to 6.

Example 3:

Input: heights = [1, 2, 3, 4], drops = 2, pour_at = 2 Output: [1, 2, 3, 4] Explanation: Both droplets settle at index 2. The first droplet cannot flow left (blocked by higher terrain) or right (uphill). Same for the second droplet.