fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <iomanip>    // ← for setw
  4. using namespace std;
  5.  
  6. int trap(const vector<int>& height) {
  7.     int left = 0, right = (int)height.size() - 1;
  8.     int leftMax = 0, rightMax = 0;
  9.     int totalWater = 0;
  10.     int step = 1;
  11.  
  12.     cout << "Step | left | right | h[left] | h[right] | leftMax | rightMax | added | totalWater\n";
  13.     cout << "-------------------------------------------------------------------------------\n";
  14.  
  15.     while (left < right) {
  16.         int added = 0;
  17.         if (height[left] < height[right]) {
  18.             // Fill on the left side
  19.             if (height[left] >= leftMax) {
  20.                 leftMax = height[left];
  21.             } else {
  22.                 added = leftMax - height[left];
  23.                 totalWater += added;
  24.             }
  25.             cout << setw(4) << step++ << " | "
  26.                  << setw(4) << left   << " | "
  27.                  << setw(5) << right  << " | "
  28.                  << setw(7) << height[left]  << " | "
  29.                  << setw(8) << height[right] << " | "
  30.                  << setw(7) << leftMax      << " | "
  31.                  << setw(8) << rightMax     << " | "
  32.                  << setw(5) << added        << " | "
  33.                  << setw(10) << totalWater  << "\n";
  34.             left++;
  35.         } else {
  36.             // Fill on the right side
  37.             if (height[right] >= rightMax) {
  38.                 rightMax = height[right];
  39.             } else {
  40.                 added = rightMax - height[right];
  41.                 totalWater += added;
  42.             }
  43.             cout << setw(4) << step++ << " | "
  44.                  << setw(4) << left   << " | "
  45.                  << setw(5) << right  << " | "
  46.                  << setw(7) << height[left]  << " | "
  47.                  << setw(8) << height[right] << " | "
  48.                  << setw(7) << leftMax      << " | "
  49.                  << setw(8) << rightMax     << " | "
  50.                  << setw(5) << added        << " | "
  51.                  << setw(10) << totalWater  << "\n";
  52.             right--;
  53.         }
  54.     }
  55.  
  56.     return totalWater;
  57. }
  58.  
  59. int main() {
  60.     vector<int> height = {0,1,0,2,1,0,1,3,2,1,2,1};
  61.     int result = trap(height);
  62.     cout << "\nFinal trapped water = " << result << endl;
  63.     return 0;
  64. }
  65.  
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Step | left | right | h[left] | h[right] | leftMax | rightMax | added | totalWater
-------------------------------------------------------------------------------
   1 |    0 |    11 |       0 |        1 |       0 |        0 |     0 |          0
   2 |    1 |    11 |       1 |        1 |       0 |        1 |     0 |          0
   3 |    1 |    10 |       1 |        2 |       1 |        1 |     0 |          0
   4 |    2 |    10 |       0 |        2 |       1 |        1 |     1 |          1
   5 |    3 |    10 |       2 |        2 |       1 |        2 |     0 |          1
   6 |    3 |     9 |       2 |        1 |       1 |        2 |     1 |          2
   7 |    3 |     8 |       2 |        2 |       1 |        2 |     0 |          2
   8 |    3 |     7 |       2 |        3 |       2 |        2 |     0 |          2
   9 |    4 |     7 |       1 |        3 |       2 |        2 |     1 |          3
  10 |    5 |     7 |       0 |        3 |       2 |        2 |     2 |          5
  11 |    6 |     7 |       1 |        3 |       2 |        2 |     1 |          6

Final trapped water = 6
https://ideone.com/RjS2xx
language:
C++ (gcc 8.3)
created:
10 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!