Trapping Rain Water

[jsartisan]

Info

difficulty: hard
title: Trapping Rain Water
type: question
template: javascript
tags: javascript, arrays, two-pointers

Question

Write a function trap that calculates how much rainwater can be trapped between bars in a histogram after raining.

Given an array of non-negative integers height where each element represents the elevation at that point, compute how much water it can trap.

Signature

function trap(height: number[]): number;

Example

trap([0,1,0,2,1,0,1,3,2,1,2,1]); // 6
trap([4,2,0,3,2,5]); // 9

Explanation

Each bar's trapped water is determined by the minimum of the highest bars to its left and right, minus its own height.

For example, in [0,1,0,2,1,0,1,3,2,1,2,1], at index 5 (height = 0):

• Left max = 2
• Right max = 3
• Water trapped = min(2, 3) - 0 = 2.

The total water trapped is the sum across all indices.

Constraints

• n == height.length
• 0 ≤ n ≤ 10⁵
• 0 ≤ height[i] ≤ 10⁴
• The algorithm should run in O(n) time and O(1) extra space.

Template (JavaScript)

javascript.template.md

/**
 * @param {number[]} height
 * @return {number}
 */
export function trap(height) {
  // TODO: Implement me
  return 0;
}

import { trap } from './index';

describe('trap (JS)', () => {
  it('handles empty array', () => {
    expect(trap([])).toBe(0);
  });

  it('handles single bar', () => {
    expect(trap([5])).toBe(0);
  });

  it('handles no trapped water', () => {
    expect(trap([1,2,3,4,5])).toBe(0);
  });

  it('handles simple valley', () => {
    expect(trap([2,0,2])).toBe(2);
  });

  it('handles complex case', () => {
    expect(trap([0,1,0,2,1,0,1,3,2,1,2,1])).toBe(6);
  });

  it('handles another complex case', () => {
    expect(trap([4,2,0,3,2,5])).toBe(9);
  });
});

Template (TypeScript)

typescript.template.md

export function trap(height: number[]): number {
  // TODO: Implement me
  return 0;
}

import { trap } from './index';

describe('trap (TS)', () => {
  it('returns 0 for empty array', () => {
    expect(trap([])).toBe(0);
  });

  it('returns 0 for increasing heights', () => {
    expect(trap([1,2,3,4])).toBe(0);
  });

  it('returns 2 for [2,0,2]', () => {
    expect(trap([2,0,2])).toBe(2);
  });

  it('returns 6 for classic example', () => {
    expect(trap([0,1,0,2,1,0,1,3,2,1,2,1])).toBe(6);
  });

  it('returns 9 for [4,2,0,3,2,5]', () => {
    expect(trap([4,2,0,3,2,5])).toBe(9);
  });
});

[github-actions]

#534 - Pull Request updated.