Trapping Rain Water in Ruby: Mastering Algorithms

Solutions for Common Algorithm Questions in Ruby

The Trapping Rain Water problem is a prominent challenge in the realm of algorithms and has been a staple in many coding interviews. It presents a scenario where given an array of integers representing elevations, the task is to determine how much rainwater can be trapped between the elevations after a downpour. In this article, we’ll delve into the problem and discuss a comprehensive approach to solving it using Ruby.

Problem Statement

Imagine you have an elevation map where the width of each bar is 1 unit. The height of each bar represents the elevation at that point. Now, after a heavy rain, water would accumulate between these bars. The question is — how much water can be trapped?

Consider the elevation map represented by the following array: [0,1,0,2,1,0,1,3,2,1,2,1]. If you plot this on a graph, it will form a series of peaks and valleys. Water will accumulate in the valleys between the peaks. In this example, the total trapped rainwater is 6 units.

Visualizing the Problem

visualizing the Trapping Rain Water problem in plaintext is an excellent way to understand it. Let’s take the example array: [0,1,0,2,1,0,1,3,2,1,2,1].

To visualize:

Height:    0   1   0   2   1   0   1   3   2   1   2   1
---------------------------------------------------------
Elevation: .   |   .   |   |   .   |   |   |   |   |   |
           .   |   .   |   |   .   |   |   |   |   |   |
           .   .   .   |   |   .   |   |   |   |   |   |
           .   .   .   |   .   .   |   |   |   |   |   |
           .   .   .   .   .   .   .   |   |   |   |   .
Water:     .   .   .   W   W   W   W   .   W   W   W   .

In the visualization above:

• . represents empty space.
• | represents an elevation block.
• W represents trapped water.

The trapped water can be seen in the spaces between the elevation blocks. In this example, the total trapped rainwater is represented by 6 W characters, which means 6 units of trapped water.