Trapping Rainwater
Monotonic Stack & Queue Problems DSA practice problem on Onlearn.
Difficulty: hard.
Topics: Trapping Rain Water Problem: Calculate the amount of water that can be trapped after raining given an array representing elevation levels., Arrays, Brute Force, Optimization, Two Pointers, Prefix Sum, Time Complexity, Space Complexity, Loops, Conditional Statements, space complexity, brute force, array, prefix/suffix arrays, time complexity analysis, two pointer technique, Prefix & Suffix Arrays.
Trapping Rain Water Given an array of non negative integers representing the elevation map where the width of each bar is 1, compute how much water it can trap after raining. Input Specification The input consists of a single line containing a list of non negative integers, height. Output Specification Return the total amount of water that can be trapped. Examples Example 1: Input: height = [0,1,0,2,1,0,1,3,2,1,2,1] Output: 6 Explanation: The array represents elevation map [0,1,0,2,1,0,1,3,2,1,2,1]. Water trapped is 6 units. Example 2: Input: height = [4,2,0,3,2,5] Output: 9 Explanation: The array represents elevation map [4,2,0,3,2,5]. Water trapped is 9 units.