Pour Water - Practice Coding Problems

Pour Water - Problem

Array Simulation Medium

You are given an elevation map represented as an integer array heights where heights[i] represents the height of the terrain at index i. The width at each index is 1.

You are also given two integers volume and k. volume units of water will fall at index k.

Water first drops at index k and rests on top of the highest terrain or water at that index. Then, it flows according to these rules:

If the droplet would eventually fall by moving left, then move left
Otherwise, if the droplet would eventually fall by moving right, then move right
Otherwise, rise to its current position

Here, "eventually fall" means that the droplet will eventually be at a lower level if it moves in that direction. Level means the height of terrain plus any water in that column.

Note: We assume there is infinitely high terrain on both sides out of bounds. Each unit of water must be in exactly one block.

Input & Output

Example 1 — Basic Water Flow

$ Input: heights = [2,1,1,2,1,2,2], volume = 4, k = 3

› Output: [2,3,3,2,2,2,2]

💡 Note: Water drops at index 3 (height 2). First drop flows left to index 1 (height 1+1=2). Second drop flows left to index 2 (height 1+1=2). Third drop flows left to index 1 (height 2+1=3). Fourth drop flows left to index 2 (height 2+1=3).

Example 2 — Water Stays at Drop Position

$ Input: heights = [1,2,3,4], volume = 2, k = 2

› Output: [1,2,5,4]

💡 Note: Water drops at index 2 (height 3). Both drops cannot flow left (heights increase) or right (height increases), so they stay at position 2: 3+2=5.

Example 3 — Water Flows Right

$ Input: heights = [3,1,3], volume = 5, k = 0

› Output: [3,6,3]

💡 Note: Water drops at index 0 (height 3). Cannot flow left (out of bounds), but can flow right to index 1 (lower height). All 5 units flow right and settle at index 1: 1+5=6.

Constraints

1 ≤ heights.length ≤ 100
0 ≤ heights[i] ≤ 99
0 ≤ volume ≤ 2000
0 ≤ k < heights.length

Visualization

Tap to expand

Understanding the Visualization

Input

Terrain heights array, water volume, and drop position

Flow Simulation

Each water drop flows left first, then right, seeking lowest level

Final Heights

Original terrain heights plus accumulated water

Key Takeaway

🎯 Key Insight: Water simulation requires checking left flow first, then right flow, with each drop settling at the lowest reachable position

Asked in

G Google 15 f Facebook 12 a Amazon 8

The key insight is to simulate water flow by checking left direction first, then right direction for each water drop. Water flows to the lowest reachable position, with left preference when tied. Best approach is simulation with helper functions. Time: O(volume × n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Simulation	O(volume × n)	O(n)	Drop each water unit individually and simulate its flow path
Optimized Simulation	O(volume × n)	O(n)	Efficient water flow simulation with better position finding

Brute Force Simulation — Algorithm Steps

For each of the volume water drops
Start at position k and try to flow left first
If can't flow left, try to flow right
Otherwise settle at current position
Update water level and repeat

Visualization

Tap to expand

Step-by-Step Walkthrough

Initial State

Terrain with drop position marked

Water Flows

Each drop flows left first, then right

Final State

All water settled at lowest reachable positions

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int* solution(int* heights, int n, int volume, int k, int* returnSize) {
    int* water = (int*)calloc(n, sizeof(int));
    
    for (int drop = 0; drop < volume; drop++) {
        int pos = k;
        
        // Try to flow left
        int leftPos = pos;
        while (leftPos > 0) {
            int currentLevel = heights[leftPos] + water[leftPos];
            int leftLevel = heights[leftPos - 1] + water[leftPos - 1];
            if (leftLevel < currentLevel) {
                leftPos--;
            } else {
                break;
            }
        }
        
        // Try to flow right if couldn't go left
        if (leftPos == pos) {
            int rightPos = pos;
            while (rightPos < n - 1) {
                int currentLevel = heights[rightPos] + water[rightPos];
                int rightLevel = heights[rightPos + 1] + water[rightPos + 1];
                if (rightLevel < currentLevel) {
                    rightPos++;
                } else {
                    break;
                }
            }
            pos = rightPos;
        } else {
            pos = leftPos;
        }
        
        water[pos]++;
    }
    
    int* result = (int*)malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) {
        result[i] = heights[i] + water[i];
    }
    
    free(water);
    *returnSize = n;
    return result;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Parse heights array
    int heights[100];
    int n = 0;
    char* token = strtok(line, "[,]\n");
    while (token != NULL && n < 100) {
        heights[n++] = atoi(token);
        token = strtok(NULL, "[,]\n");
    }
    
    int volume, k;
    scanf("%d", &volume);
    scanf("%d", &k);
    
    int returnSize;
    int* result = solution(heights, n, volume, k, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%d", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(volume × n)

For each water drop, we might scan the entire array to find settling position

✓ Linear Growth

Space Complexity

O(n)

Extra array to track water levels at each position

⚡ Linearithmic Space

23.4K Views

Medium Frequency

~25 min Avg. Time

580 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Simulation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler