trapped_rainwater2.cpp File Reference

Implementation of the Trapped Rainwater Problem More...

#include <algorithm>
#include <cassert>
#include <cstddef>
#include <cstdint>
#include <vector>

Include dependency graph for trapped_rainwater2.cpp:

Go to the source code of this file.

Namespaces
namespace	dynamic_programming
	Dynamic Programming algorithms.

Functions
uint32_t	dynamic_programming::trappedRainwater (const std::vector< uint32_t > &heights)
	Function to calculate the trapped rainwater.
static void	test ()
	Self-test implementations.
int	main ()
	Main function.

Detailed Description

Implementation of the Trapped Rainwater Problem

This implementation calculates the total trapped rainwater using a two-pointer approach. It maintains two pointers (left and right) and tracks the maximum height seen so far from both ends (leftMax and rightMax). At each step, the algorithm decides which side to process based on which boundary is smaller, ensuring O(n) time and O(1) space complexity.

Author

kanavgoyal898

Definition in file trapped_rainwater2.cpp.

Function Documentation

main()

int main

(

void

)

Main function.

Returns

0 on exit

Definition at line 108 of file trapped_rainwater2.cpp.

           {
    test();  // run self-test implementations
    return 0;
}

test()

void test ( )

static

Self-test implementations.

Returns

void

Definition at line 69 of file trapped_rainwater2.cpp.

                   {
    std::vector<uint32_t> test_basic = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
    assert(dynamic_programming::trappedRainwater(test_basic) == 6);
 
    std::vector<uint32_t> test_peak_under_water = {3, 0, 2, 0, 4};
    assert(dynamic_programming::trappedRainwater(test_peak_under_water) == 7);
 
    std::vector<uint32_t> test_bucket = {5, 1, 5};
    assert(dynamic_programming::trappedRainwater(test_bucket) == 4);
 
    std::vector<uint32_t> test_skewed_bucket = {4, 1, 5};
    assert(dynamic_programming::trappedRainwater(test_skewed_bucket) == 3);
 
    std::vector<uint32_t> test_empty = {};
    assert(dynamic_programming::trappedRainwater(test_empty) == 0);
 
    std::vector<uint32_t> test_flat = {0, 0, 0, 0, 0};
    assert(dynamic_programming::trappedRainwater(test_flat) == 0);
 
    std::vector<uint32_t> test_no_trapped_water = {1, 1, 2, 4, 0, 0, 0};
    assert(dynamic_programming::trappedRainwater(test_no_trapped_water) == 0);
 
    std::vector<uint32_t> test_single_elevation = {5};
    assert(dynamic_programming::trappedRainwater(test_single_elevation) == 0);
 
    std::vector<uint32_t> test_two_point_elevation = {5, 1};
    assert(dynamic_programming::trappedRainwater(test_two_point_elevation) ==
           0);
 
    std::vector<uint32_t> test_large_elevation_map_difference = {5, 1, 6, 1,
                                                                 7, 1, 8};
    assert(dynamic_programming::trappedRainwater(
               test_large_elevation_map_difference) == 15);
}