Leetcode 42: Trapping Rain Water

1. Problem Statement (Simple Explanation):

You’re given an array height of length n:

Each height[i] is a non-negative integer representing a bar’s height.
The width of each bar is 1.

Imagine this array as an elevation map. You must compute how many units of water can be trapped between the bars after raining.

2. Examples:

Example 1:

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]

Visualization shows 6 units of trapped water.

Output: 6

Example 2:

Input: height = [4,2,0,3,2,5]

Trapped water:

Between 4 and 3: 2 units above index 1, 4 units above index 2 (total 6).
Between 3 and 5: 1 unit above index 4, 2 units above index 3 (total 3).
Total: 6 + 3 = 9.

Output: 9

3. Intuition:

At any position i, the water height is:

water_at_i = min(max_left[i], max_right[i]) - height[i]

where:

max_left[i] = max height on the left of i including i.
max_right[i] = max height on the right of i including i.

Water can only be trapped where both sides have taller bars than the current height.

Brute force would compute max_left and max_right for each i in O(n²).
We can do it in O(n) time, O(1) extra space with the two-pointer technique.

4. Approach – Two Pointers (O(n) Time, O(1) Space):

Key Idea:

Use two pointers:

left starting at 0
right starting at n-1

Maintain:

leftMax = highest bar seen so far from the left
rightMax = highest bar seen so far from the right

At each step:

Compare height[left] and height[right]:

If height[left] < height[right]:

Then leftMax is the limiting factor for left side.
If height[left] >= leftMax, update leftMax.
Else water trapped at left = leftMax - height[left].
Move left++.

Else:

Symmetric logic for right using rightMax.
Move right--.

Why this works:

If height[left] < height[right], then for any i at left, the right side is guaranteed to have a bar >= height[right] ≥ height[left], so the water level is determined by leftMax.
Similarly for the other side.

Algorithm (Step-by-Step):

Initialize:

left = 0
right = n - 1
leftMax = 0
rightMax = 0
water = 0

While left < right:

If height[left] < height[right]:

If height[left] >= leftMax:

leftMax = height[left]

Else:

water += leftMax - height[left]

left++

Else:

If height[right] >= rightMax:

rightMax = height[right]

Else:

water += rightMax - height[right]

right--

Return water.

Pseudo-code:

Complexity:

Time: O(n) (each index visited at most once).
Space: O(1) extra.

5. Java code:

6. C code:

7. C++ code:

8. Python code:

9. JavaScript code:

Comments

Leetcode 1: Two Sum

Leetcode Link: https://leetcode.com/problems/two-sum/ 1. Problem Statement (Simple Explanation) You are given: An array of integers nums An integer target You need to return the indices of two numbers in the array such that: Conditions: Each input has exactly one solution . You cannot use the same element twice . You can return the answer in any order . 2. Examples Example 1 Input: nums = [2, 7, 11, 15], target = 9 Output: [0, 1] Explanation: nums[0]+nums[1]=2+7=9 So we return [0, 1]. Example 2 Input: ...

Leetcode 3: Longest Substring Without Repeating Characters

Leetcode Link 1. Problem Statement (Simple Explanation) You are given a string s. You need to find the length of the longest substring of s that does not contain any repeated characters. A substring is a contiguous sequence of characters in the string. You must return an integer length, not the substring itself. 2. Examples Example 1 Input: s = "abcabcbb" Output: 3 Explanation: Some substrings without repeating characters: "abc", "bca", "cab"The longest length is 3. Example 2 Input: s = "bbbbb" Output: 1 Explanation: All substrings that are valid are just "b". The longest length is 1. Example 3 Input: s = "pwwkew" Output: 3 Explanation: Possible substrings without repetition: "pw", "wke", "kew". "wke" or "kew" have length 3. "pwke" is not valid because it’s not contiguous in the original string (p and k are separated by ww). Constraints...

Leetcode 2: Add Two Numbers

Leetcode Link: https://leetcode.com/problems/add-two-numbers/ 1. Problem Statement (Simple Explanation) You are given two non-empty linked lists , l1 and l2, that represent two non-negative integers. Each node contains a single digit . The digits are stored in reverse order (i.e., the 1’s digit is at the head). You need to add the two numbers and return the sum as a linked list , also in reverse order. You can assume: There are no leading zeros , except when the number itself is 0. 2. Examples Example 1 Input: l1 = [2,4,3] l2 = [5,6,4] Interpreting linked lists as numbers (reverse order): l1 represents 342 l2 represents 465 Output: [7,0,8] Explanation: ...

codesprint with rishav

Search This Blog