Given an array of n non-negative integers arr[] representing an elevation map where the width of each bar is 1, find how much water it can trap following rain.
Examples
Input: arr[] = {3, 0, 1, 0, 4, 0, 2}
Output: 10
Explanation: The expected rainwater to be trapped is shown in the above image.
Input: arr[] = {3, 0, 2, 0, 4}
Output: 7
Explanation: We trap 0 + 3 + 1 + 3 + 0 = 7 units.
Input: arr[] = {1, 2, 3, 4}
Output: 0
Explanation : We cannot trap water as there is no height bound on both sides
Input: arr[] = {2, 1, 5, 3, 1, 0, 4}
Output: 9
Explanation : We trap 0 + 1 + 0 + 1 + 3 + 4 + 0 = 9 units of water. Table of Content
- Observations:
- Brute Force – O(n2) Time and O(1) Space:
- Computing prefix and suffix max for every index – O(n) Time and O(n) Space
- Best Approach – Using Two Pointers – O(n) Time and O(1) Space:
- Using Stack – O(n) Time and O(n) Space:
Observations: The problem’s fundamental idea runs like this:
- Should taller bars on the left and the right, an element of the array can hold water.
- By determining the heights of the higher bars on the left and right sides, one can ascertain the water to be kept in every position.
- The water kept overall is the summation of the water kept in every index.
- Without limits on both sides, no water can be filled.
Brute force O(n2) time and O(1) Place: Space
Go across every element in the array to locate the highest bars on both sides. Consider the lesser of the two heights. The quantity of water this array element can store defines the difference between the smaller height and the height of the current element.
C++
#include <bits/stdc++.h>
using namespace std;
// Function to return the maximum water that can be stored
int maxWater(vector<int>& arr)
{
int res = 0;
// For every element of the array
for (int i = 1; i < arr.size() - 1; i++) {
// Find the maximum element on its left
int left = arr[i];
for (int j = 0; j < i; j++)
left = max(left, arr[j]);
// Find the maximum element on its right
int right = arr[i];
for (int j = i + 1; j < arr.size(); j++)
right = max(right, arr[j]);
// Update the maximum water
res += (min(left, right) - arr[i]);
}
return res;
}
// Driver code
int main()
{
vector<int> arr = { 2, 1, 5, 3, 1, 0, 4 };
cout << maxWater(arr);
return 0;
}C
#include <stdio.h>
// Function to return the maximum water that can be stored
int maxWater(int arr[], int n) {
int res = 0;
// For every element of the array
for (int i = 1; i < n - 1; i++) {
// Find the maximum element on its left
int left = arr[i];
for (int j = 0; j < i; j++)
if (arr[j] > left)
left = arr[j];
// Find the maximum element on its right
int right = arr[i];
for (int j = i + 1; j < n; j++)
if (arr[j] > right)
right = arr[j];
// Update the maximum water
res += (left < right ? left : right) - arr[i];
}
return res;
}
// Driver code
int main() {
int arr[] = { 2, 1, 5, 3, 1, 0, 4 };
int n = sizeof(arr) / sizeof(arr[0]);
printf("%d", maxWater(arr, n));
return 0;
}Java
import java.util.*;
// Function to return the maximum water that can be stored
class GfG {
static int maxWater(int[] arr) {
int res = 0;
// For every element of the array
for (int i = 1; i < arr.length - 1; i++) {
// Find the maximum element on its left
int left = arr[i];
for (int j = 0; j < i; j++)
left = Math.max(left, arr[j]);
// Find the maximum element on its right
int right = arr[i];
for (int j = i + 1; j < arr.length; j++)
right = Math.max(right, arr[j]);
// Update the maximum water
res += Math.min(left, right) - arr[i];
}
return res;
}
// Driver code
public static void main(String[] args) {
int[] arr = { 2, 1, 5, 3, 1, 0, 4 };
System.out.println(maxWater(arr));
}
}Python
# Function to return the maximum water that can be stored
def maxWater(arr):
res = 0
# For every element of the array
for i in range(1, len(arr) - 1):
# Find the maximum element on its left
left = arr[i]
for j in range(i):
left = max(left, arr[j])
# Find the maximum element on its right
right = arr[i]
for j in range(i + 1, len(arr)):
right = max(right, arr[j])
# Update the maximum water
res += (min(left, right) - arr[i])
return res
# Driver code
if __name__ == "__main__":
arr = [2, 1, 5, 3, 1, 0, 4]
print(maxWater(arr))C#
using System;
class GfG {
// Function to return the maximum water that can be stored
static int maxWater(int[] arr) {
int res = 0;
// For every element of the array
for (int i = 1; i < arr.Length - 1; i++) {
// Find the maximum element on its left
int left = arr[i];
for (int j = 0; j < i; j++)
left = Math.Max(left, arr[j]);
// Find the maximum element on its right
int right = arr[i];
for (int j = i + 1; j < arr.Length; j++)
right = Math.Max(right, arr[j]);
// Update the maximum water
res += Math.Min(left, right) - arr[i];
}
return res;
}
// Driver code
static void Main() {
int[] arr = { 2, 1, 5, 3, 1, 0, 4 };
Console.WriteLine(maxWater(arr));
}
}JavaScript
// Function to return the maximum water that can be stored
function maxWater(arr) {
let res = 0;
// For every element of the array
for (let i = 1; i < arr.length - 1; i++) {
// Find the maximum element on its left
let left = arr[i];
for (let j = 0; j < i; j++)
left = Math.max(left, arr[j]);
// Find the maximum element on its right
let right = arr[i];
for (let j = i + 1; j < arr.length; j++)
right = Math.max(right, arr[j]);
// Update the maximum water
res += Math.min(left, right) - arr[i];
}
return res;
}
// Driver code
let arr = [2, 1, 5, 3, 1, 0, 4];
console.log(maxWater(arr));Output
9