101 Logo
onenoughtone

Code Implementation

Rain Water Collector Implementation

Below is the implementation of the rain water collector:

solution.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
/**
 * Calculate how much rainwater can be trapped between buildings.
 * Dynamic Programming approach.
 * 
 * @param {number[]} heights - Array of building heights
 * @return {number} - Total amount of trapped water
 */
function trapDP(heights) {
  const n = heights.length;
  if (n <= 2) return 0;
  
  // Precompute maximum heights to the left and right
  const leftMax = new Array(n);
  const rightMax = new Array(n);
  
  // Initialize leftMax and rightMax
  leftMax[0] = heights[0];
  rightMax[n - 1] = heights[n - 1];
  
  // Fill leftMax array
  for (let i = 1; i < n; i++) {
    leftMax[i] = Math.max(leftMax[i - 1], heights[i]);
  }
  
  // Fill rightMax array
  for (let i = n - 2; i >= 0; i--) {
    rightMax[i] = Math.max(rightMax[i + 1], heights[i]);
  }
  
  // Calculate trapped water
  let totalWater = 0;
  for (let i = 0; i < n; i++) {
    totalWater += Math.min(leftMax[i], rightMax[i]) - heights[i];
  }
  
  return totalWater;
}
 
/**
 * Calculate how much rainwater can be trapped between buildings.
 * Two Pointers approach.
 * 
 * @param {number[]} heights - Array of building heights
 * @return {number} - Total amount of trapped water
 */
function trapTwoPointers(heights) {
  const n = heights.length;
  if (n <= 2) return 0;
  
  let left = 0;
  let right = n - 1;
  let leftMax = heights[left];
  let rightMax = heights[right];
  let totalWater = 0;
  
  while (left < right) {
    if (leftMax < rightMax) {
      left++;
      leftMax = Math.max(leftMax, heights[left]);
      totalWater += leftMax - heights[left];
    } else {
      right--;
      rightMax = Math.max(rightMax, heights[right]);
      totalWater += rightMax - heights[right];
    }
  }
  
  return totalWater;
}
 
/**
 * Calculate how much rainwater can be trapped between buildings.
 * Stack-Based approach.
 * 
 * @param {number[]} heights - Array of building heights
 * @return {number} - Total amount of trapped water
 */
function trapStack(heights) {
  const n = heights.length;
  if (n <= 2) return 0;
  
  const stack = [];
  let totalWater = 0;
  
  for (let i = 0; i < n; i++) {
    // While the current building is taller than the building at the top of the stack
    while (stack.length > 0 && heights[i] > heights[stack[stack.length - 1]]) {
      const top = stack.pop();
      
      // If the stack is empty, there's no left boundary
      if (stack.length === 0) break;
      
      // Calculate the width of the water trap
      const width = i - stack[stack.length - 1] - 1;
      
      // Calculate the height of the water trap
      const height = Math.min(heights[i], heights[stack[stack.length - 1]]) - heights[top];
      
      // Add the volume of water trapped
      totalWater += width * height;
    }
    
    // Push the current index onto the stack
    stack.push(i);
  }
  
  return totalWater;
}
 
// Test cases
const heights1 = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1];
console.log(trapDP(heights1));  // 6
console.log(trapTwoPointers(heights1));  // 6
console.log(trapStack(heights1));  // 6
 
const heights2 = [4, 2, 0, 3, 2, 5];
console.log(trapDP(heights2));  // 9
console.log(trapTwoPointers(heights2));  // 9
console.log(trapStack(heights2));  // 9

Step-by-Step Explanation

Let's break down the implementation:

  1. Understand the Problem: First, understand that we need to calculate how much rainwater can be trapped between buildings of varying heights.
  2. Identify Key Insight: Recognize that for each position, the amount of water trapped depends on the minimum of the maximum heights to its left and right.
  3. Implement Dynamic Programming Solution: Precompute the maximum heights to the left and right of each position, then calculate the trapped water.
  4. Implement Two Pointers Solution: Use two pointers to scan the array from both ends, keeping track of the maximum heights seen so far.
  5. Implement Stack-Based Solution: Use a stack to keep track of indices of buildings that can potentially trap water.
PreviousNext
ProblemSolutionCode
101 Logo
onenoughtone