What is the time complexity of Trapping Rain Water?

The optimal solution has a time complexity of O(n).

What data structures are used to solve Trapping Rain Water?

This problem uses Array, Two Pointers, Dynamic Programming, Stack, Monotonic Stack. Understanding these concepts is essential for solving this Hard problem efficiently.

What are the key insights for solving Trapping Rain Water?

Insight 1: The amount of water that can be trapped at any bar is determined by the minimum of the maximum height to its left and the maximum height to its right, minus the height of the bar itself. If this value is positive, then water is trapped. Insight 2: The two-pointer approach is efficient because it allows us to simultaneously iterate from both ends of the array, updating the left and right maximum heights and calculating the trapped water in a single pass.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Trapping Rain Water - LeetCode 42 Solution

Q: How to solve Trapping Rain Water?

The provided code employs a two-pointer approach to solve the trapping rain water problem. It initializes two pointers, 'left' and 'right', at the beginning and end of the height array, respectively. It also maintains two variables, 'left_max' and 'right_max', to keep track of the maximum height encountered so far from the left and right sides. The algorithm iterates as long as the left pointer is less than the right pointer. In each iteration, it compares the heights at the left and right pointers. If the height at the left pointer is smaller, it checks if it's greater than or equal to the 'left_max'. If so, it updates 'left_max'. Otherwise, it calculates the trapped water at the left pointer by subtracting its height from 'left_max' and adds it to the total. The left pointer is then incremented. A similar process is performed for the right pointer if the height at the right pointer is smaller. This process continues until the left and right pointers meet. The core idea is to incrementally compute how much water can be contained at a specific position based on `left_max` and `right_max` and move towards the inner part of array.

Q: Which companies ask LeetCode 42. Trapping Rain Water in interviews?

This problem is frequently asked at Accolite, Adobe, Airbnb, Amazon, American Express and 75 more companies.

Trapping Rain Water - Complete Solution Guide

Trapping Rain Water is LeetCode problem 42, a Hard level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

Given n non-negative integers representing an elevation map where the width of each bar is 1 , compute how much water it can trap after raining. Example 1: Input: height = [0,1,0,2,1,0,1,3,2,1,2,1] Output: 6 Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Example 2: Input: height = [4,2,0,3,2,5] Output: 9 Constraints: n == height.length 1 <= n <= 2 * 10 4 0 <= height[i] <

Detailed Explanation

The "Trapping Rain Water" problem asks us to calculate the total amount of rainwater that can be trapped between bars of varying heights. Imagine an elevation map represented by an array of non-negative integers, where each integer represents the height of a bar with a width of 1. When it rains, some areas between the bars will fill with water. We need to find the total volume of trapped water. The input is an array of integers representing the height of each bar, and the output is a single integer representing the total trapped water.

Solution Approach

The provided code employs a two-pointer approach to solve the trapping rain water problem. It initializes two pointers, 'left' and 'right', at the beginning and end of the height array, respectively. It also maintains two variables, 'left_max' and 'right_max', to keep track of the maximum height encountered so far from the left and right sides. The algorithm iterates as long as the left pointer is less than the right pointer. In each iteration, it compares the heights at the left and right pointers. If the height at the left pointer is smaller, it checks if it's greater than or equal to the 'left_max'. If so, it updates 'left_max'. Otherwise, it calculates the trapped water at the left pointer by subtracting its height from 'left_max' and adds it to the total. The left pointer is then incremented. A similar process is performed for the right pointer if the height at the right pointer is smaller. This process continues until the left and right pointers meet. The core idea is to incrementally compute how much water can be contained at a specific position based on `left_max` and `right_max` and move towards the inner part of array.

Step-by-Step Algorithm

Step 1: Initialize two pointers, 'left' to 0 and 'right' to len(height) - 1.
Step 2: Initialize 'left_max' and 'right_max' to 0.
Step 3: Initialize 'total_water' to 0.
Step 4: While 'left' is less than 'right':
Step 5: If height[left] < height[right]:
Step 6: If height[left] >= left_max:
Step 7: Update left_max = height[left]
Step 8: Else:
Step 9: Add (left_max - height[left]) to total_water
Step 10: Increment 'left'
Step 11: Else:
Step 12: If height[right] >= right_max:
Step 13: Update right_max = height[right]
Step 14: Else:
Step 15: Add (right_max - height[right]) to total_water
Step 16: Decrement 'right'
Step 17: Return total_water

Key Insights

Insight 1: The amount of water that can be trapped at any bar is determined by the minimum of the maximum height to its left and the maximum height to its right, minus the height of the bar itself. If this value is positive, then water is trapped.
Insight 2: The two-pointer approach is efficient because it allows us to simultaneously iterate from both ends of the array, updating the left and right maximum heights and calculating the trapped water in a single pass.
Insight 3: Maintaining separate 'left_max' and 'right_max' variables enables the algorithm to calculate trapped water locally without the need for extra data structures or repeated computations.

Complexity Analysis

Time Complexity: O(n)

Space Complexity: O(1)

Topics

This problem involves: Array, Two Pointers, Dynamic Programming, Stack, Monotonic Stack.

Companies

Asked at: Accolite, Adobe, Airbnb, Amazon, American Express, Apple, Atlassian, BitGo, Bloomberg, ByteDance, Capgemini, Cisco, Citadel, Coveo, CrowdStrike, DE Shaw, EPAM Systems, Expedia, Flipkart, Goldman Sachs, Google, Grammarly, Groww, HashedIn, Hive, IBM, InMobi, Infosys, Intel, Intuit, Jane Street, MAQ Software, MakeMyTrip, Media.net, Meta, Microsoft, Moloco, Myntra, National Instruments, Navan, Navi, Nextdoor, Nutanix, Nvidia, Oracle, PayPal, Paytm, PhonePe, PubMatic, Publicis Sapient, Qualcomm, Roblox, SAP, Salesforce, Samsung, ServiceNow, Snowflake, Splunk, Sprinklr, Swiggy, Tekion, Tesla, TikTok, Turvo, Uber, Visa, Walmart Labs, Wix, X, Yahoo, Yandex, Zenefits, Zepto, Zeta, Zoho, Zopsmart, carwale, jio, redbus, tcs.

Trapping Rain Water | LeetCode 42

Hard

Array Two Pointers Dynamic Programming Stack Monotonic Stack

Time: O(n)Space: O(1)

Solution Code

Available in:

class Solution {
    public int trap(int[] height) {
        if (height == null || height.length == 0) {
            return 0;
        }

        int left = 0;
        int right = height.length - 1;
        int left_max = 0;
        int right_max = 0;
        int total_water = 0;

        while (left < right) {
            if (height[left] < height[right]) {
                if (height[left] >= left_max) {
                    left_max = height[left];
                } else {
                    total_water += left_max - height[left];
                }
                left++;
            } else {
                if (height[right] >= right_max) {
                    right_max = height[right];
                } else {
                    total_water += right_max - height[right];
                }
                right--;
            }
        }

        return total_water;
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 42: Trapping Rain Water - Detailed explanation and solution approaches.

Topics

Array Two Pointers Dynamic Programming Stack Monotonic Stack

Companies

AccoliteAdobeAirbnbAmazonAmerican ExpressAppleAtlassianBitGo

Stats

Difficulty:Hard

Languages:4

Companies:80

Problem #:42

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

17 steps

1
Step 1: Initialize two pointers, 'left' to 0 and 'right' to len(height) - 1.
2
Step 2: Initialize 'left_max' and 'right_max' to 0.
3
Step 3: Initialize 'total_water' to 0.
4
Step 4: While 'left' is less than 'right':
5
Step 5: If height[left] < height[right]:
6
Step 6: If height[left] >= left_max:
7
Step 7: Update left_max = height[left]
8
Step 8: Else:
9
Step 9: Add (left_max - height[left]) to total_water
10
Step 10: Increment 'left'
11
Step 11: Else:
12
Step 12: If height[right] >= right_max:
13
Step 13: Update right_max = height[right]
14
Step 14: Else:
15
Step 15: Add (right_max - height[right]) to total_water
16
Step 16: Decrement 'right'
17
Step 17: Return total_water

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(n)

👍 Linear - Good! Visits each element once.

💾

Space Complexity

O(1)

💪 Constant space - Uses same memory regardless of input!

📝

Why?

The time complexity is O(n) because the algorithm iterates through the array once using the two pointers. The space complexity is O(1) because it uses a constant amount of extra space to store the pointers and maximum heights, regardless of the input size.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Dynamic Programming

This approach precomputes the maximum height to the left and right of each bar using two separate arrays. Then, for each bar, the trapped water is calculated based on these precomputed values.

Time: O(n)Space: O(n)

Trade-offs: DP uses extra space to store left and right max arrays. It might be easier to understand for some people, but the two pointer approach is more space efficient.

Stack

Use a monotonic decreasing stack to keep track of the bars. When encountering a bar taller than the top of the stack, calculate the water trapped between the current bar, the top of the stack, and the bar below the top.

Time: O(n)Space: O(n)

Trade-offs: Stack approach's complexity is the same as the other methods. The main drawback of stack approach is that it might be more difficult to understand than two-pointer or dynamic programming.

✨

Key Insights

1Insight 1: The amount of water that can be trapped at any bar is determined by the minimum of the maximum height to its left and the maximum height to its right, minus the height of the bar itself. If this value is positive, then water is trapped.
2Insight 2: The two-pointer approach is efficient because it allows us to simultaneously iterate from both ends of the array, updating the left and right maximum heights and calculating the trapped water in a single pass.
3Insight 3: Maintaining separate 'left_max' and 'right_max' variables enables the algorithm to calculate trapped water locally without the need for extra data structures or repeated computations.

📚

Key Terms Explained

For Students

Array

A collection of items stored at contiguous memory locations. Like a row of boxes.

Two Pointers

Using two indices to traverse data from different positions simultaneously.

Dynamic Programming

Breaking complex problems into smaller subproblems and storing results.

Stack

LIFO structure - Last In, First Out. Like a stack of plates!

Edge Cases

Edge case 1: Empty input array (height = []). The code handles this by returning 0 immediately, as no water can be trapped.
Edge case 2: Input array with all heights being the same (e.g., height = [2, 2, 2, 2]). The two pointers will move towards each other, and the maximum heights will be updated accordingly. Since no height is smaller than left_max/right_max no water will be accumulated. Therefore, the trapped water will remain 0, which is correct.
Edge case 3: Input array with only one element (e.g., height = [5]). The loop condition `left < right` will never be true, and the function will immediately return the initialized `total_water` value of 0, which is correct as no water can be trapped in such a scenario.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Incorrectly updating 'left_max' or 'right_max'. It's crucial to update these values only when a higher bar is encountered.

✗Common mistake 2: Not handling edge cases such as an empty array or an array with only one element. Failing to do so can lead to incorrect results or runtime errors.

✗Common mistake 3: Confusing the condition to move the left or right pointer. Always compare the heights at the 'left' and 'right' pointers and move the pointer with the smaller height.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Analyzing the capacity of reservoirs or dams to hold water based on the surrounding terrain.

🏦Real-world scenario 2: Optimizing the design of flood control systems to maximize water retention in specific areas.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

When dealing with arrays, always consider if sorting would simplify the problem. Many array problems have O(n) solutions using hash maps or two-pointer technique.

🎯 Interview Tip

Hard problems often combine multiple techniques. Break the problem into sub-problems.

⚠️ Watch Out

Off-by-one errors are the most common mistake. Double-check your loop bounds and array indices.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: July 13, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

I was asked this exact problem at my Google interview. The interviewer wanted me to optimize space complexity.

@InterviewProJul 13

Try solving this without using extra space first. It's a great exercise for understanding the underlying pattern.

@CodeNinjaJul 6

❓

Frequently Asked Questions

What is the most efficient way to solve array problems?

Most array problems can be solved efficiently using techniques like two-pointer approach, sliding window, or hash maps. The key is identifying whether the array is sorted (enabling binary search) or if tracking seen elements (using hash maps) can help achieve O(n) time complexity.

When is the two-pointer technique most effective?

Two pointers work best on sorted arrays or when searching for pairs/triplets that satisfy a condition. Common patterns include: moving pointers inward from both ends (like in two-sum variants), fast/slow pointers for cycle detection, or left/right pointers for partitioning.

How do I approach hard algorithm problems?

Hard problems often require: 1) Breaking down into subproblems, 2) Combining multiple advanced techniques, 3) Careful optimization of brute force. Start with a working solution (even O(n²) or worse), then optimize. Draw examples, identify patterns, and think about what makes this problem unique.

How should I practice algorithm problems effectively?

Focus on understanding patterns rather than memorizing solutions. After solving a problem, review optimal solutions and understand the intuition. Group similar problems to recognize patterns. Practice explaining your approach out loud. Review problems after a few days to test retention.

What is the optimal approach for "Trapping Rain Water"?

For this hard-level Array problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether two pointers techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?