Pour Water

Pour Water

What is this problem about?

The Pour Water problem simulates dropping k units of water onto a terrain at a given index. Each water unit flows left first (to a lower point), then right (if it can't go left), and stays at the drop point if it can't flow anywhere lower. This coding problem simulates each water unit's movement. The array and simulation interview pattern is the core.

Why is this asked in interviews?

Airbnb and Oracle ask this simulation problem because it tests careful directional movement simulation with priority rules: try left before right. Each water unit follows a greedy downhill path.

Algorithmic pattern used

Per-unit simulation with directional priority. For each water unit: start at index. Try to flow left: move left while heights[pos-1] < heights[pos]. If pos == 0 or heights[pos-1] >= heights[pos], check if pos moved left from index. If yes, place water here (heights[pos]++). Else, try flowing right similarly. If neither works, place at index.

Example explanation

heights=[2,1,1,2,1,2,1,3,1,1,2,2], k=4, index=5.

• Drop 1: flow left: 5→4 (2>1✓)→3 (1=1 stop). At 4, try left: 4→3(1=1 no). Can't flow further left. Place at 4. heights[4]++.
• Drop 2: At 5, flow left: heights[4]=2 ≥ heights[5]=2, can't flow. Try right: heights[6]=1<2→flow right... but going right from 5: heights[6]=1<2, heights[7]=3>1 stop. Place at 6. Heights[6]++. Continue for all 4 drops.

Common mistakes candidates make

• Confusing the left-first, then right priority.
• Moving water past higher points (can only flow to strictly lower).
• Not returning to the drop point when neither direction is possible.
• Incorrect boundary handling (can't go past index 0 or n-1).

Interview preparation tip

Simulation problems require careful directional logic. Pour Water's rules: (1) try to find the leftmost position you can flow to, (2) if that position is lower than current, go there; (3) otherwise try right; (4) if neither, stay. Implement with two separate loops for left and right. Practice similar "gravity simulation" problems: "water levels in containers," "trapping rain water." Simulation correctness depends on precise rule encoding.