Prepin
Log in

M

Given a collection of integers that depict an elevation map, determine the volume of water that the area can retain following rainfall.

Approach / Explanation

This question requires you to develop an algorithm that computes the volume of water a specific area can retain after rainfall, based on a series of integers that depict an elevation map. Each integer corresponds to the height at a specific point on the map. Your task is to determine the amount of water that would accumulate in the 'valleys' formed between the 'hills', which is the core of this problem. To effectively tackle this question: Gain a clear understanding of the problem by visualizing it; consider drawing a simple diagram if necessary. Recognize and comprehend the characteristics of the problem, such as noticing that water collects in the dips located between the peaks in the data. Devise a method to traverse the data and compute the water retention, keeping in mind that the levels will be limited by the shorter peak on either side of a 'valley'. Implement your strategy in code in a straightforward and clear manner, which may involve a single pass through the dataset or potentially two passes in certain situations.

Suggested Answer

Consider an array of integers that represents an elevation map, for example, [0,1,0,2,1,0,1,3,2,1,2,1]. This elevation map can be visualized as a series of peaks and valleys, with water pooling in the valleys that are flanked by peaks on either side. A straightforward and effective method to solve this is by employing a two-pointer strategy. We can position two pointers, one on the left and the other on the right end of the array. Additionally, we will maintain two variables to keep track of the maximum height encountered so far from both ends. We then move the pointers toward the center while updating our maximum height variables and calculating the total water trapped. def calculateWater ( height ) : left = 0 right = len ( height ) - 1 max_left = max_right = water = 0 while left <= right : if max_left <= max_right : if height [ left ] <= max_left : water += max_left - height [ left ] else : max_left = height [ left ] left += 1 else : if height [ right ] <= max_right : water += max_right - height [ right ] else : max_right = height [ right ] right -= 1 return water This implementation returns the total volume of water collected after a single traversal of the input data, achieving a time complexity of O(n), where n is the length of the array.

Alternative Answer

Here's another illustration: [3, 0, 0, 2, 0, 4]. In this scenario, water can be retained at the indices 1, 2, and 4. This problem can be efficiently addressed using a two-pass technique. During the first pass, we determine the maximum height of bars to the left of each element. In the second pass, we assess the maximum height of bars to the right of each element. Ultimately, for each element, we calculate the potential water it can contain, which equals the lesser of the maximum heights of the bars on either side, minus its own height. def findWater ( arr , n ) : left = [ 0 ] * n right = [ 0 ] * n water = 0 left [ 0 ] = arr [ 0 ] for i in range ( 1 , n ) : left [ i ] = max ( left [ i - 1 ], arr [ i ]) right [ n - 1 ] = arr [ n - 1 ] for i in range ( n - 2 , - 1 , - 1 ) : right [ i ] = max ( right [ i + 1 ], arr [ i ]) ; for i in range ( 0 , n ) : water += min ( left [ i ], right [ i ]) - arr [ i ] return water Make sure to articulate your code and reasoning clearly during the interview. Interviewers will evaluate not only your programming abilities but also how well you explain and dissect the problem and the solution you have implemented.

Question Details

Difficulty & Category

Medium
algorithms

Companies

Meta (Facebook)

Product

AI Candidate AgentCompaniesBrowse JobsDeep ProfileSkill AssessmentOpportunity Matching
Prepin.ai

© 2026 Prepin | All rights reserved.