Elevation Water Accumulation — Problem Statement & Solution Guide

RecursionHardTrapping Rainwater

TimeO(n)

SpaceO(1)

Problem Description

You are given an array of non‑negative integers, where each element represents the height of a vertical bar in a one‑dimensional elevation map. When rain falls over this map, water can accumulate between bars of higher elevation. Your task is to compute the total volume of water that can be trapped after the rain has stopped.

Input: A single line containing the array of integers, e.g. "[0,1,0,2]".

Output: A single integer representing the total units of water that can be held.

The algorithm must handle large inputs efficiently, with a time complexity better than O(n²).

DSA Pattern Breakdown

"Elevation Water Accumulation"

hard

WHY DOES IT MATTER?

The two‑pointer pattern exemplifies how to convert a seemingly quadratic problem into linear time by exploiting monotonic properties and boundary constraints, a skill that recurs in many array‑based interview challenges.

OPTIMIZATION CHALLENGE

The key insight is that the water level at any index is limited by the smaller of the highest bars seen so far from each side, allowing us to discard one side's computation once its max is known to be lower.

REAL-WORLD CONNECTION

Think of a dam system where water flows between two levees; the lower levee determines the maximum water level until a higher barrier is encountered, mirroring the left‑max/right‑max comparison in the algorithm.

During an interview, start by articulating the naive O(n²) idea, then immediately point out the redundant scans and propose the two‑pointer invariant; this demonstrates both problem awareness and optimization thinking.

COMPLEXITY AT A GLANCE

⏱ Time:O(n)

💾 Space:O(1)

Core Theory — Why This Approach?

The elevation‑water problem is a classic example of using two‑pointer or stack techniques to achieve linear time processing. The naive view treats each index independently, scanning left and right to find the maximum bar height on both sides; the water trapped at that index is the minimum of those maxima minus the bar height. However, this double scan per element leads to O(n²) time, which quickly becomes infeasible for large inputs (n can be up to 10⁶ in interview constraints). The optimal paradigm leverages the observation that water level at any position is bounded by the shorter of the highest bars seen so far from the left and from the right. By maintaining running maxima while traversing from both ends, we can compute trapped water on the fly, eliminating redundant scans. This yields an O(n) time, O(1) extra‑space solution that scales gracefully.

An alternative optimal approach uses a monotonic decreasing stack to identify boundaries where water can be trapped. When a higher bar appears, the stack’s top (a valley) is popped, and the distance between the current bar and the new stack top determines the width of the water container. The height is the difference between the lower of the two bounding bars and the valley height. While elegant, the stack method also runs in O(n) time but requires O(n) auxiliary space, making the two‑pointer technique the most space‑efficient.

Understanding why the naive method fails and how the two‑pointer insight reduces work is crucial: each element’s left‑max and right‑max can be pre‑computed in a single pass from each direction, but storing both arrays costs O(n) space. The two‑pointer method merges these passes, updating pointers based on which side has the smaller current max, guaranteeing that the water level is correctly determined without extra storage.

Interview Questions on This Problem

Q1How would you modify the algorithm to also return the indices of the bars that actually hold water?

Maintain two pointers and their max values as usual; whenever water is added at a position, record that index in a list. The list will contain all positions where trapped water > 0, which can be returned alongside the total volume.

Q2Can you solve the problem in a single pass without using extra arrays or a stack? Explain the reasoning.

Yes. Use two pointers (left, right) starting at the ends, and keep track of leftMax and rightMax. At each step, move the pointer with the smaller current height inward; the water trapped at that pointer is max(0, leftMax - height[left]) or max(0, rightMax - height[right]) respectively. This works because the smaller side determines the limiting height for water accumulation.

Q3If the elevation map is streamed in real time (you receive heights one by one), how would you compute trapped water using O(1) additional memory?

You cannot compute the final trapped water exactly without future information because right boundaries are unknown. However, you can maintain a running leftMax and a stack of decreasing heights; when a new height exceeds the stack top, you can resolve water for popped valleys using the new height as the right boundary. This yields an online algorithm with amortized O(1) extra space per element.

Examples

Example 1

Input

[0,1,0,2,1,0,1,3,2,1,2,1]

Output

Explanation: The water trapped at each position is calculated by the minimum of the maximum height to its left and right minus its own height. Summing these values for all positions yields 6 units of water.

Example 2

Input

[4,2,0,3,2,5]

Output

Explanation: Positions 1,2,3,4 trap 2,4,1,2 units respectively. Adding them gives 9 units of water.

Example 3

Input

[1,0,2,1,0,1,3,2,1,2,1]

Output

Explanation: Water is trapped at positions 1,4,5,7,8,9,10 with amounts 1,1,1,1,1,1,1 respectively, totaling 7 units.

Constraints

1 <= nums.length <= 100000
0 <= nums[i] <= 10^9
The array contains only integers
The solution must run in O(n) time and O(1) additional space

Optimal Approach & Strategy

Use two pointers with leftMax and rightMax variables; move the pointer with the smaller current height inward, add water based on the difference between its max and current height, and update the max accordingly.

Brute Force Approach

For each index, scan leftwards to find the maximum height, scan rightwards for the maximum height, compute trapped water as min(leftMax, rightMax) - height[i]; repeat for all indices.

Verified Code Solutions

Language:

JavaScript Solution

Time: O(n)

function solution(height) {
   let left = 0, right = height.length - 1, maxLeft = 0, maxRight = 0, res = 0;
   while (left <= right) {
       if (height[left] < height[right]) {
           if (height[left] >= maxLeft) {
               maxLeft = height[left];
           } else {
               res += maxLeft - height[left];
           }
           left++;
       } else {
           if (height[right] >= maxRight) {
               maxRight = height[right];
           } else {
               res += maxRight - height[right];
           }
           right--;
       }
   }
   return res;
}

class Solution {
   public:
       int solution(vector<int>& height) {
           int left = 0, right = height.size() - 1, maxLeft = 0, maxRight = 0, res = 0;
           while (left <= right) {
               if (height[left] < height[right]) {
                   if (height[left] >= maxLeft) {
                       maxLeft = height[left];
                   } else {
                       res += maxLeft - height[left];
                   }
                   left++;
               } else {
                   if (height[right] >= maxRight) {
                       maxRight = height[right];
                   } else {
                       res += maxRight - height[right];
                   }
                   right--;
               }
           }
           return res;
       }
   };

class Solution {
   public int solution(int[] height) {
       int left = 0, right = height.length - 1, maxLeft = 0, maxRight = 0, res = 0;
       while (left <= right) {
           if (height[left] < height[right]) {
               if (height[left] >= maxLeft) {
                   maxLeft = height[left];
               } else {
                   res += maxLeft - height[left];
               }
               left++;
           } else {
               if (height[right] >= maxRight) {
                   maxRight = height[right];
               } else {
                   res += maxRight - height[right];
               }
               right--;
           }
       }
       return res;
   }
}

def solution(height):
   left = 0
   right = len(height) - 1
   maxLeft = 0
   maxRight = 0
   res = 0
   while left <= right:
       if height[left] < height[right]:
           if height[left] >= maxLeft:
               maxLeft = height[left]
           else:
               res += maxLeft - height[left]
           left += 1
       else:
           if height[right] >= maxRight:
               maxRight = height[right]
           else:
               res += maxRight - height[right]
           right -= 1
   return res

function solution(height) {
   let left = 0, right = height.length - 1, maxLeft = 0, maxRight = 0, res = 0;
   while (left <= right) {
       if (height[left] < height[right]) {
           if (height[left] >= maxLeft) {
               maxLeft = height[left];
           } else {
               res += maxLeft - height[left];
           }
           left++;
       } else {
           if (height[right] >= maxRight) {
               maxRight = height[right];
           } else {
               res += maxRight - height[right];
           }
           right--;
       }
   }
   return res;
}

Solve in Interative Editor

Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.

Elevation Water Accumulation Solution

Problem Statement

Input

Output

Input

Output

Input

Output

Constraints

More Recursion

Optimized Approach

Brute Force Approach

Step-by-Step Dry Run

Tested Solutions

Elevation Water Accumulation — Problem Statement & Solution Guide

Problem Description

DSA Pattern Breakdown

Core Theory — Why This Approach?

Interview Questions on This Problem

Examples

Constraints

Optimal Approach & Strategy

Brute Force Approach

Verified Code Solutions

Solve in Interative Editor