Trapping Rain Water

You are given an array of non-negative integers representing the heights of blocks. Your task is to compute the maximum amount of water that can be trapped between the blocks after it rains.

For example, given the array [0,1,0,2,1,0,1,3,2,1,2,1], the maximum trapped water is 6 units.

The solution should have a time complexity of \(O(n)\) and an auxiliary space complexity of \(O(1)\). Use a two-pointer technique where you maintain two pointers from both ends of the array, while keeping track of the maximum height seen so far from both sides. At every step, update the trapped water with the difference between the current maximum and the current height.

inputFormat

The first line contains an integer \(n\) (the number of elements in the array). The second line contains \(n\) space-separated non-negative integers representing the heights of the blocks.

outputFormat

Output a single integer representing the maximum amount of water that can be trapped.

12
0 1 0 2 1 0 1 3 2 1 2 1

6