42. Trapped water

[zenith pulsar]

https://leetcode.com/problems/trapping-rain-water/description/

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 * 104
0 <= height[i] <= 105

;compile java

public class Solution
{
    public static int trap(int... height)
    {
        // result
        int trapped = 0;

        // array length
        final int n = height.length;

        // buffer
        final int[] buffer = new int[ n ];

        return trapped;
    }

public static void main(String[] args)
{
final int x1 = trap(new int[]{ 0,1,0,2,1,0,1,3,2,1,2,1});
System.out.println(x1 == 6);
final int x2 = trap(new int[]{
4,2,0,3,2,5});
System.out.println(x2 == 9);
}

}

[real turret]

Program Output

false
false

fd26 | 63ms | java | jdk 21.0.2 | godbolt.org

[zenith pulsar]

;compile java
||

public class trapped5 {
// O(n + n*h*4)
public static final int trap(final int... height) {
 int trapped = 0;
 final int n = height.length;
 final int[] buffer = new int[ n ];

 int max_height  = -1;
 for(int i = 0; i < n; ++i) {
  final int x = buffer[i] = height[i];
  if (x > max_height) { max_height = x; }
 }

 for(int h = 0; h < max_height; ++h) {
  int first_index = -1;
  int last_index  = -1;

  for(int i = 0; i < n; ++i) { if (buffer[i] > 0) { first_index = i; i=n+1; } }
  for(int i = n - 1; i >= 0; --i) { if (buffer[i] > 0) { last_index = i; i=-1; } }

  if (first_index == last_index) { return trapped; }

  for(int i = first_index; i <= last_index; ++i) { if (buffer[i] == 0) { ++trapped; } }

  for(int i = 0; i < n; ++i) { int x = buffer[i]; if (x > 0) { buffer[i] = (x - 1);} }
 }

 return trapped;
}

public static void main(String[] args)
{
 int x0 = trap(new int[]{0,1,0,1,0});
 System.out.println(x0 == 1);
 int x1 = trap(new int[]{0,1,0,2,1,0,1,3,2,1,2,1});
 System.out.println(x1 == 6);
 int x2 = trap(new int[]{4,2,0,3,2,5});
 System.out.println(x2 == 9);
 int x3 = trap(new int[]{0,1,0});
 System.out.println(x3 == 0);
 int x4 = trap(new int[]{0,1,0,1});
 System.out.println(x4 == 1);
}
}

||

[real turret]

Program Output

true
true
true
true
true

fd26 | 89ms | java | jdk 21.0.2 | godbolt.org

[zenith pulsar]

;compile c -O3
||

#include <stdio.h>
#include <stdlib.h>

// O(n + n*h*4)
static int trap(const int* height, const int n) {
 int trapped = 0;
 int* buffer = (int*) calloc(n, sizeof(int));

 int max_height  = -1;
 for(int i = 0; i < n; ++i) {
  const int x = buffer[i] = height[i];
  if (x > max_height) { max_height = x; }
 }

 for(int h = 0; h < max_height; ++h) {
  int first_index = -1;
  int last_index  = -1;

  for(int i = 0; i < n; ++i) { if (buffer[i] > 0) { first_index = i; i=n+1; } }
  for(int i = n - 1; i >= 0; --i) { if (buffer[i] > 0) { last_index = i; i=-1; } }

  if (first_index == last_index) { h = max_height+1;
  } else {
    for(int i = first_index; i <= last_index; ++i) { if (buffer[i] == 0) { ++trapped; } }
    for(int i = 0; i < n; ++i) { const int x = buffer[i]; if (x > 0) { buffer[i] = (x - 1);} }
  }
 }

 free(buffer);

 return trapped;
}


int main()
{
 int a0[] = {0,1,0,1,0};
 int a1[] = {0,1,0,2,1,0,1,3,2,1,2,1};
 int a2[] = {4,2,0,3,2,5};
 int a3[] = {0,1,0};
 int a4[] = {0,1,0,1};

 int x0 = trap(a0,5);
 printf("%d\n", x0 == 1);
 int x1 = trap(a1,12);
 printf("%d\n", x1 == 6);
 int x2 = trap(a2,6);
 printf("%d\n", x2 == 9);
 int x3 = trap(a3,3);
 printf("%d\n", x3 == 0);
 int x4 = trap(a4,4);
 printf("%d\n", x4 == 1);
 return 0;
}

||