aboutsummaryrefslogtreecommitdiff
path: root/trapping_rain_water.c
blob: 594efc17de092685c9ecd0a49106421703781ae8 (plain)
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
// 42. Trapping Rain Water
#include "leetcode.h"

/*
 * 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.
 */

int trap(int *height, int heightSize) {
  int *left = (int *)malloc(heightSize * sizeof(int));
  int *right = (int *)malloc(heightSize * sizeof(int));
  left[0] = height[0];
  right[heightSize - 1] = height[heightSize - 1];
  for (int i = 1; i < heightSize; i++)
    left[i] = height[i] > left[i - 1] ? height[i] : left[i - 1];
  for (int i = heightSize - 2; i >= 0; i--)
    right[i] = height[i] > right[i + 1] ? height[i] : right[i + 1];
  int ans = 0;
  for (int i = 0; i < heightSize; i++)
    ans += (fmin(left[i], right[i]) - height[i]);
  free(left), free(right);
  return ans;
}

int main() {
  int h1[] = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1}, h2[] = {4, 2, 0, 3, 2, 5};
  printf("%d\n", trap(h1, ARRAY_SIZE(h1))); // expect: 6
  printf("%d\n", trap(h2, ARRAY_SIZE(h2))); // expect: 9
}