Dada una array de N enteros no negativos arr[] que representan un mapa de elevación donde el ancho de cada barra es 1 , calcule cuánta agua puede atrapar después de llover.
Ejemplos :
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to return the maximum
// water that can be stored
int maxWater(int arr[], int n)
{
// To store the maximum water
// that can be stored
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++)
left = max(left, arr[j]);
// Find the maximum element on its right
int right = arr[i];
for (int j = i + 1; j < n; j++)
right = max(right, arr[j]);
// Update the maximum water
res = res + (min(left, right) - arr[i]);
}
return res;
}
// Driver code
int main()
{
int arr[] = { 0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << maxWater(arr, n);
return 0;
}
C
// C code to implement the approach
#include <stdio.h>
// Creating MACRO for finding the maximum number
#define max(x, y) (((x) > (y)) ? (x) : (y))
// Creating MACRO for finding the minimum number
#define min(x, y) (((x) < (y)) ? (x) : (y))
// Function to return the maximum
// water that can be stored
int maxWater(int arr[], int n)
{
// To store the maximum water
int res = 0;
// For every element of the array
for (int i = 0; i < n; 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 left
int right = arr[i];
for (int j = i + 1; j < n; j++) {
right = max(right, arr[j]);
}
// Update the result (maximum water)
res = res + (min(left, right) - arr[i]);
}
// Return the maximum water
return res;
}
// Driver code
int main()
{
int arr[] = { 0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1 };
int n = sizeof(arr) / sizeof(arr[0]);
printf("%d", maxWater(arr, n));
return 0;
}
// This code is contributed by amnindersingh1414.
Java
// Java code to implement of the approach
class GFG {
// Function to return the maximum
// water that can be stored
public static int maxWater(int[] arr, int n)
{
// To store the maximum water
// that can be stored
int res = 0;
// For every element of the array
// except first and last element
for (int i = 1; i < n - 1; i++) {
// Find maximum element on its left
int left = arr[i];
for (int j = 0; j < i; j++) {
left = Math.max(left, arr[j]);
}
// Find maximum element on its right
int right = arr[i];
for (int j = i + 1; j < n; j++) {
right = Math.max(right, arr[j]);
}
// Update maximum water value
res += Math.min(left, right) - arr[i];
}
return res;
}
// Driver code
public static void main(String[] args)
{
int[] arr = { 0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1 };
int n = arr.length;
System.out.print(maxWater(arr, n));
}
}
// This code is contributed by Debidutta Rath
Python3
# Python3 implementation of the approach # Function to return the maximum # water that can be stored def maxWater(arr, n): # To store the maximum water # that can be stored res = 0 # For every element of the array for i in range(1, n - 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, n): right = max(right, arr[j]) # Update the maximum water res = res + (min(left, right) - arr[i]) return res # Driver code if __name__ == "__main__": arr = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1] n = len(arr) print(maxWater(arr, n)) # This code is contributed by AnkitRai01
C#
// C# implementation of the approach
using System;
class GFG {
// Function to return the maximum
// water that can be stored
public static int maxWater(int[] arr, int n)
{
// To store the maximum water
// that can be stored
int res = 0;
// For every element of the array
// except first and last element
for (int i = 1; i < n - 1; i++) {
// Find maximum element on its left
int left = arr[i];
for (int j = 0; j < i; j++) {
left = Math.Max(left, arr[j]);
}
// Find maximum element on its right
int right = arr[i];
for (int j = i + 1; j < n; j++) {
right = Math.Max(right, arr[j]);
}
// Update maximum water value
res += Math.Min(left, right) - arr[i];
}
return res;
}
// Driver code
public static void Main(String[] args)
{
int[] arr = { 0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1 };
int n = arr.Length;
Console.Write(maxWater(arr, n));
}
}
// This code is contributed by shivanisinghss2110
Javascript
<script>
// Javascript implementation of the approach
// Function to return the maximum
// water that can be stored
function maxWater(arr, n)
{
// To store the maximum water
// that can be stored
let res = 0;
// For every element of the array
// except first and last element
for(let i = 1; i < n - 1; i++)
{
// Find maximum element on its left
let left = arr[i];
for(let j = 0; j < i; j++)
{
left = Math.max(left, arr[j]);
}
// Find maximum element on its right
let right = arr[i];
for(let j = i + 1; j < n; j++)
{
right = Math.max(right, arr[j]);
}
// Update maximum water value
res += Math.min(left, right) - arr[i];
}
return res;
}
let arr = [ 0, 1, 0, 2, 1, 0,
1, 3, 2, 1, 2, 1 ];
let n = arr.length;
document.write(maxWater(arr,n));
</script>
C++
// C++ program to find maximum amount of water that can
// be trapped within given set of bars.
#include <bits/stdc++.h>
using namespace std;
int findWater(int arr[], int n)
{
// left[i] contains height of tallest bar to the
// left of i'th bar including itself
int left[n];
// Right [i] contains height of tallest bar to
// the right of ith bar including itself
int right[n];
// Initialize result
int water = 0;
// Fill left array
left[0] = arr[0];
for (int i = 1; i < n; i++)
left[i] = max(left[i - 1], arr[i]);
// Fill right array
right[n - 1] = arr[n - 1];
for (int i = n - 2; i >= 0; i--)
right[i] = max(right[i + 1], arr[i]);
// Calculate the accumulated water element by element
// consider the amount of water on i'th bar, the
// amount of water accumulated on this particular
// bar will be equal to min(left[i], right[i]) - arr[i]
// .
for (int i = 1; i < n - 1; i++) {
int var = min(left[i - 1], right[i + 1]);
if (var > arr[i]) {
water += var - arr[i];
}
}
return water;
}
// Driver program
int main()
{
int arr[] = { 0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << findWater(arr, n);
return 0;
}
C
// Implementation in C of the above approach
// Importing the required header files
#include <stdio.h>
// Creating MACRO for finding the maximum number
#define max(x, y) (((x) > (y)) ? (x) : (y))
// Creating MACRO for finding the minimum number
#define min(x, y) (((x) < (y)) ? (x) : (y))
// Function to return the maximum
// water that can be stored
int findWater(int arr[], int n)
{
// left[i] contains height of tallest bar to the
// left of i'th bar including itself
int left[n];
// Right [i] contains height of tallest bar to the
// right of ith bar including itself
int right[n];
// Initialize result
int water = 0;
// Fill left array
left[0] = arr[0];
for (int i = 1; i < n; i++) {
left[i] = max(left[i - 1], arr[i]);
}
// Fill right array
right[n - 1] = arr[n - 1];
for (int i = n - 2; i >= 0; i--) {
right[i] = max(right[i + 1], arr[i]);
}
// Calculate the accumulated water element by element
// consider the amount of water on i'th bar, the
// amount of water accumulated on this particular
// bar will be equal to min(left[i], right[i]) - arr[i]
// .
for (int i = 1; i < n - 1; i++) {
int var = min(left[i - 1], right[i + 1]);
if (var > arr[i]) {
water += var - arr[i];
}
}
return water;
}
// Driver program
int main()
{
int arr[] = { 0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1 };
int n = sizeof(arr) / sizeof(arr[0]);
printf("%d", findWater(arr, n));
return 0;
}
// This code is contributed by amnindersingh1414.
Java
// Java program to find maximum amount of water that can
// be trapped within given set of bars.
class Test {
static int arr[]
= new int[] { 0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1 };
// Method for maximum amount of water
static int findWater(int n)
{
// left[i] contains height of tallest bar to the
// left of i'th bar including itself
int left[] = new int[n];
// Right [i] contains height of tallest bar to
// the right of ith bar including itself
int right[] = new int[n];
// Initialize result
int water = 0;
// Fill left array
left[0] = arr[0];
for (int i = 1; i < n; i++)
left[i] = Math.max(left[i - 1], arr[i]);
// Fill right array
right[n - 1] = arr[n - 1];
for (int i = n - 2; i >= 0; i--)
right[i] = Math.max(right[i + 1], arr[i]);
// Calculate the accumulated water element by
// element consider the amount of water on i'th bar,
// the amount of water accumulated on this
// particular bar will be equal to min(left[i],
// right[i]) - arr[i] .
for (int i = 0; i < n; i++)
water += Math.min(left[i], right[i]) - arr[i];
return water;
}
// Driver method to test the above function
public static void main(String[] args)
{
System.out.println(findWater(arr.length));
}
}
Python3
# Python program to find maximum amount of water that can # be trapped within given set of bars. def findWater(arr, n): # left[i] contains height of tallest bar to the # left of i'th bar including itself left = [0]*n # Right [i] contains height of tallest bar to # the right of ith bar including itself right = [0]*n # Initialize result water = 0 # Fill left array left[0] = arr[0] for i in range(1, n): left[i] = max(left[i-1], arr[i]) # Fill right array right[n-1] = arr[n-1] for i in range(n-2, -1, -1): right[i] = max(right[i + 1], arr[i]) # Calculate the accumulated water element by element # consider the amount of water on i'th bar, the # amount of water accumulated on this particular # bar will be equal to min(left[i], right[i]) - arr[i] . for i in range(0, n): water += min(left[i], right[i]) - arr[i] return water # Driver program if __name__ == '__main__': arr = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1] n = len(arr) print(findWater(arr, n)) # This code is contributed by # Smitha Dinesh Semwal
C#
// C# program to find maximum amount of water that can
// be trapped within given set of bars.
using System;
class Test {
static int[] arr
= new int[] { 0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1 };
// Method for maximum amount of water
static int findWater(int n)
{
// left[i] contains height of tallest bar to the
// left of i'th bar including itself
int[] left = new int[n];
// Right [i] contains height of tallest bar to
// the right of ith bar including itself
int[] right = new int[n];
// Initialize result
int water = 0;
// Fill left array
left[0] = arr[0];
for (int i = 1; i < n; i++)
left[i] = Math.Max(left[i - 1], arr[i]);
// Fill right array
right[n - 1] = arr[n - 1];
for (int i = n - 2; i >= 0; i--)
right[i] = Math.Max(right[i + 1], arr[i]);
// Calculate the accumulated water element by
// element consider the amount of water on i'th bar,
// the amount of water accumulated on this
// particular bar will be equal to min(left[i],
// right[i]) - arr[i] .
for (int i = 0; i < n; i++)
water += Math.Min(left[i], right[i]) - arr[i];
return water;
}
// Driver method to test the above function
public static void Main()
{
Console.WriteLine(findWater(arr.Length));
}
}
// This code is contributed by vt_m.
PHP
<?php
// PHP program to find maximum
// amount of water that can
// be trapped within given set of bars.
function findWater($arr, $n)
{
// left[i] contains height of
// tallest bar to the
// left of i'th bar including
// itself
// Right [i] contains height
// of tallest bar to the right
// of ith bar including itself
// $right[$n];
// Initialize result
$water = 0;
// Fill left array
$left[0] = $arr[0];
for ($i = 1; $i < $n; $i++)
$left[$i] = max($left[$i - 1],
$arr[$i]);
// Fill right array
$right[$n - 1] = $arr[$n - 1];
for ($i = $n - 2; $i >= 0; $i--)
$right[$i] = max($right[$i + 1],
$arr[$i]);
// Calculate the accumulated
// water element by element
// consider the amount of
// water on i'th bar, the
// amount of water accumulated
// on this particular
// bar will be equal to min(left[i],
// right[i]) - arr[i] .
for ($i = 0; $i < $n; $i++)
$water += min($left[$i], $right[$i])
- $arr[$i];
return $water;
}
// Driver program
$arr = array(0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1);
$n = sizeof($arr);
echo findWater($arr, $n);
// This code is contributed by ajit
?>
Javascript
<script>
// Javascript program to find maximum amount of water that can
// be trapped within given set of bars.
let arr = [ 0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1 ];
// Method for maximum amount of water
function findWater(n)
{
// left[i] contains height of tallest bar to the
// left of i'th bar including itself
let left = new Array(n);
// Right [i] contains height of tallest bar to
// the right of ith bar including itself
let right = new Array(n);
// Initialize result
let water = 0;
// Fill left array
left[0] = arr[0];
for (let i = 1; i < n; i++)
left[i] = Math.max(left[i - 1], arr[i]);
// Fill right array
right[n - 1] = arr[n - 1];
for (let i = n - 2; i >= 0; i--)
right[i] = Math.max(right[i + 1], arr[i]);
// Calculate the accumulated water element by element
// consider the amount of water on i'th bar, the
// amount of water accumulated on this particular
// bar will be equal to min(left[i], right[i]) - arr[i] .
for (let i = 0; i < n; i++)
water += Math.min(left[i], right[i]) - arr[i];
return water;
}
// Driver method to test the above function
document.write(findWater(arr.length));
// This code is contributed by unknown2108
</script>
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to return the maximum
// water that can be stored
int maxWater(int height[], int n)
{
// Stores the indices of the bars
stack<int> st;
// Stores the final result
int ans = 0;
// Loop through the each bar
for (int i = 0; i < n; i++) {
// Remove bars from the stack
// until the condition holds
while ((!st.empty())
&& (height[st.top()] < height[i])) {
// Store the height of the top
// and pop it.
int pop_height = height[st.top()];
st.pop();
// If the stack does not have any
// bars or the popped bar
// has no left boundary
if (st.empty())
break;
// Get the distance between the
// left and right boundary of
// popped bar
int distance = i - st.top() - 1;
// Calculate the min. height
int min_height
= min(height[st.top()], height[i])
- pop_height;
ans += distance * min_height;
}
// If the stack is either empty or
// height of the current bar is less than
// or equal to the top bar of stack
st.push(i);
}
return ans;
}
// Driver code
int main()
{
int arr[] = { 0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << maxWater(arr, n);
return 0;
}
// The code is contributed by Soumitri Chattopadhyay
Java
import java.io.*;
import java.util.*;
// Java implementation of the approach
class GFG {
// Function to return the maximum
// water that can be stored
public static int maxWater(int[] height)
{
// Stores the indices of the bars
Stack<Integer> stack = new Stack<>();
// size of the array
int n = height.length;
// Stores the final result
int ans = 0;
// Loop through the each bar
for (int i = 0; i < n; i++) {
// Remove bars from the stack
// until the condition holds
while ((!stack.isEmpty())
&& (height[stack.peek()] < height[i])) {
// store the height of the top
// and pop it.
int pop_height = height[stack.peek()];
stack.pop();
// If the stack does not have any
// bars or the popped bar
// has no left boundary
if (stack.isEmpty())
break;
// Get the distance between the
// left and right boundary of
// popped bar
int distance = i - stack.peek() - 1;
// Calculate the min. height
int min_height
= Math.min(height[stack.peek()],
height[i])
- pop_height;
ans += distance * min_height;
}
// If the stack is either empty or
// height of the current bar is less than
// or equal to the top bar of stack
stack.push(i);
}
return ans;
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1 };
System.out.print(maxWater(arr));
}
}
Python3
# Python implementation of the approach # Function to return the maximum # water that can be stored def maxWater(height): # Stores the indices of the bars stack = [] # size of the array n = len(height) # Stores the final result ans = 0 # Loop through the each bar for i in range(n): # Remove bars from the stack # until the condition holds while(len(stack) != 0 and (height[stack[-1]] < height[i])): # store the height of the top # and pop it. pop_height = height[stack[-1]] stack.pop() # If the stack does not have any # bars or the popped bar # has no left boundary if(len(stack) == 0): break # Get the distance between the # left and right boundary of # popped bar distance = i - stack[-1] - 1 # Calculate the min. height min_height = min(height[stack[-1]], height[i])-pop_height ans += distance * min_height # If the stack is either empty or # height of the current bar is less than # or equal to the top bar of stack stack.append(i) return ans # Driver code if __name__ == '__main__': arr = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1] print(maxWater(arr)) # This code is contributed by rag2127
C#
using System;
using System.Collections;
using System.Collections.Generic;
// C# implementation of the approach
class GFG {
// Function to return the maximum
// water that can be stored
public static int maxWater(int[] height)
{
// Stores the indices of the bars
Stack stack = new Stack();
// size of the array
int n = height.Length;
// Stores the final result
int ans = 0;
// Loop through the each bar
for (int i = 0; i < n; i++) {
// Remove bars from the stack
// until the condition holds
while ((stack.Count != 0)
&& (height[(int)stack.Peek()]
< height[i])) {
// store the height of the top
// and pop it.
int pop_height = height[(int)stack.Peek()];
stack.Pop();
// If the stack does not have any
// bars or the popped bar
// has no left boundary
if (stack.Count == 0)
break;
// Get the distance between the
// left and right boundary of
// popped bar
int distance = i - (int)stack.Peek() - 1;
// Calculate the min. height
int min_height
= Math.Min(height[(int)stack.Peek()],
height[i])
- pop_height;
ans += distance * min_height;
}
// If the stack is either empty or
// height of the current bar is less than
// or equal to the top bar of stack
stack.Push(i);
}
return ans;
}
// Driver code
public static void Main()
{
int[] arr = { 0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1 };
Console.Write(maxWater(arr));
}
}
// This code is contributed by pratham76.
Javascript
<script>
// Python implementation of the approach
// Function to return the maximum
// water that can be stored
function maxWater(height){
// Stores the indices of the bars
let stack = []
// size of the array
let n = height.length
// Stores the final result
let ans = 0
// Loop through the each bar
for(let i=0;i<n;i++){
// Remove bars from the stack
// until the condition holds
while(stack.length != 0 && (height[stack[stack.length-1]] < height[i]) ){
// store the height of the top
// and pop it.
let pop_height = height[stack.pop()]
// If the stack does not have any
// bars or the popped bar
// has no left boundary
if(stack.length == 0)
break
// Get the distance between the
// left and right boundary of
// popped bar
let distance = i - stack[stack.length - 1] - 1
// Calculate the min. height
let min_height =Math.min(height[stack[stack.length - 1]],height[i])-pop_height
ans += distance * min_height
}
// If the stack is either empty or
// height of the current bar is less than
// or equal to the top bar of stack
stack.push(i)
}
return ans
}
// Driver code
let arr = [ 0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
document.write(maxWater(arr))
// This code is contributed by shinjanpatra
</script>
C++
// C++ program to implement the approach
#include <bits/stdc++.h>
using namespace std;
int trappedWater(vector<int>& arr)
{
int num_blocks = 0;
int n = 0;
int max_height = INT_MIN;
// Find total blocks, max height and length of array
for (auto height : arr) {
num_blocks += height;
n += 1;
max_height = max(max_height, height);
}
// Total water, left pointer and right pointer
// initialized to 0 and n - 1
int total = 0;
int left = 0;
int right = n - 1;
for (int i = 1; i <= max_height; i++) {
// Find leftmost point greater than current row (i)
while (arr[left] < i)
left += 1;
// Find rightmost point greater than current row (i)
while (arr[right] < i)
right -= 1;
// water in this row = right - left + 1
total += (right - left + 1);
}
total -= num_blocks;
return total;
}
// Driver code
int main()
{
vector<int> arr
= { 0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1 };
// Function call
cout << trappedWater(arr) << endl;
return 0;
}
// This code is contributed by shinjanpatra
Java
// Java program to determine how much amount of water can an
// elevation map store given in the form of an array of
// height of n points
import java.io.*;
class GFG {
public static int trappedWater(int arr[])
{
// To store the number of blocks
int n = arr.length;
// To store the sum of all the heights
int num_blocks = 0;
// To store the maximum height in the array
int max_height = Integer.MIN_VALUE;
// Compute the sum of all heights and the
// maximum height given in the array
for (int i = 0; i < n; i++) {
max_height = Math.max(max_height, arr[i]);
num_blocks += arr[i];
}
// To store the answer and initialise
// the left and right pointers
int total = 0, left = 0, right = n - 1;
for (int i = 1; i <= max_height; i++) {
// Compute the leftmost point greater than
// current row (i)
while (arr[left] < i) {
left++;
}
// Compute the rightmost point greater than
// current row (i)
while (arr[right] < i) {
right--;
}
// Water in this row = right - left + 1
total += (right - left + 1);
}
total -= num_blocks;
return total;
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1 };
// Function call
System.out.println(trappedWater(arr));
}
}
// this code is contributed by shruti456rawal
Python3
# Python code to implement the approach
def trappedWater(arr):
num_blocks = 0
n = 0
max_height = float('-inf')
# Find total blocks, max height and length of array
for height in arr:
num_blocks += height
n += 1
max_height = max(max_height, height)
# Total water, left pointer and right pointer
# initialized to 0 and n - 1
total = 0
left = 0
right = n - 1
for i in range(1, max_height+1):
# Find leftmost point greater than current row (i)
while arr[left] < i:
left += 1
# Find rightmost point greater than current row (i)
while arr[right] < i:
right -= 1
# Water in this row = right - left + 1
total += (right - left + 1)
total -= num_blocks
return total
# Driver code
if __name__ == "__main__":
arr = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
print(trappedWater(arr))
Javascript
<script>
function trappedWater(arr){
let num_blocks = 0
let n = 0
let max_height =Number.MIN_VALUE
// Find total blocks, max height and length of array
for(let height of arr){
num_blocks += height
n += 1
max_height = Math.max(max_height, height)
}
// Total water, left pointer and right pointer initialized to 0 and n - 1
let total = 0
let left = 0
let right = n - 1
for(let i = 1;i <= max_height; i++){
// Find leftmost point greater than current row (i)
while(arr[left] < i)
left += 1
// Find rightmost point greater than current row (i)
while(arr[right] < i)
right -= 1
// Water in this row = right - left + 1
total += (right - left + 1)
}
total -= num_blocks
return total
}
// Driver code
let arr = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
document.write(trappedWater(arr))
// This code is contributed by shinjanpatra
</script>
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
int maxWater(int arr[], int n)
{
// Indices to traverse the array
int left = 0;
int right = n-1;
// To store Left max and right max
// for two pointers left and right
int l_max = 0;
int r_max = 0;
// To store the total amount
// of rain water trapped
int result = 0;
while (left <= right)
{
// We need check for minimum of left
// and right max for each element
if(r_max <= l_max)
{
// Add the difference between
// current value and right max at index r
result += max(0, r_max-arr[right]);
// Update right max
r_max = max(r_max, arr[right]);
// Update right pointer
right -= 1;
}
else
{
// Add the difference between
// current value and left max at index l
result += max(0, l_max-arr[left]);
// Update left max
l_max = max(l_max, arr[left]);
// Update left pointer
left += 1;
}
}
return result;
}
// Driver code
int main() {
int arr[] = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
int N = sizeof(arr)/sizeof(arr[0]);
cout << maxWater(arr, N) << endl;
return 0;
}
// This code is contributed by avanitrachhadiya2155
Java
// Java implementation of the approach
import java.util.*;
class GFG {
static int maxWater(int[] arr, int n)
{
// Indices to traverse the array
int left = 0;
int right = n - 1;
// To store Left max and right max
// for two pointers left and right
int l_max = 0;
int r_max = 0;
// To store the total amount
// of rain water trapped
int result = 0;
while (left <= right) {
// We need check for minimum of left
// and right max for each element
if (r_max <= l_max) {
// Add the difference between
// current value and right max at index r
result += Math.max(0, r_max - arr[right]);
// Update right max
r_max = Math.max(r_max, arr[right]);
// Update right pointer
right -= 1;
}
else {
// Add the difference between
// current value and left max at index l
result += Math.max(0, l_max - arr[left]);
// Update left max
l_max = Math.max(l_max, arr[left]);
// Update left pointer
left += 1;
}
}
return result;
}
// Driver code
public static void main(String[] args)
{
int[] arr = { 0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1 };
int N = arr.length;
System.out.print(maxWater(arr, N));
}
}
// This code is contributed by rutvik_56.
Python3
# Python3 implementation of the approach # Function to return the maximum # water that can be stored def maxWater(arr, n): # Indices to traverse the array left = 0 right = n-1 # To store Left max and right max # for two pointers left and right l_max = 0 r_max = 0 # To store the total amount # of rain water trapped result = 0 while (left <= right): # We need check for minimum of left # and right max for each element if r_max <= l_max: # Add the difference between #current value and right max at index r result += max(0, r_max-arr[right]) # Update right max r_max = max(r_max, arr[right]) # Update right pointer right -= 1 else: # Add the difference between # current value and left max at index l result += max(0, l_max-arr[left]) # Update left max l_max = max(l_max, arr[left]) # Update left pointer left += 1 return result # Driver code if __name__ == '__main__': arr = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1] N = len(arr) print(maxWater(arr, N)) # This code is contributed by Nikhil Chatragadda
C#
// C# implementation of the approach
using System;
class GFG {
static int maxWater(int[] arr, int n)
{
// indices to traverse the array
int left = 0;
int right = n - 1;
// To store Left max and right max
// for two pointers left and right
int l_max = 0;
int r_max = 0;
// To store the total amount
// of rain water trapped
int result = 0;
while (left <= right) {
// We need check for minimum of left
// and right max for each element
if (r_max <= l_max) {
// Add the difference between
// current value and right max at index r
result += Math.Max(0, r_max - arr[right]);
// Update right max
r_max = Math.Max(r_max, arr[right]);
// Update right pointer
right -= 1;
}
else {
// Add the difference between
// current value and left max at index l
result += Math.Max(0, l_max - arr[left]);
// Update left max
l_max = Math.Max(l_max, arr[left]);
// Update left pointer
left += 1;
}
}
return result;
}
// Driver code
static void Main()
{
int[] arr = { 0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1 };
int N = arr.Length;
Console.WriteLine(maxWater(arr, N));
}
}
// This code is contributed by divyeshrabadiya07.
Javascript
<script>
// Javascript implementation of the approach
function maxWater(arr, n)
{
// indices to traverse the array
let left = 0;
let right = n - 1;
// To store Left max and right max
// for two pointers left and right
let l_max = 0;
let r_max = 0;
// To store the total amount
// of rain water trapped
let result = 0;
while (left <= right)
{
// We need check for minimum of left
// and right max for each element
if(r_max <= l_max)
{
// Add the difference between
// current value and right max at index r
result += Math.max(0, r_max - arr[right]);
// Update right max
r_max = Math.max(r_max, arr[right]);
// Update right pointer
right -= 1;
}
else
{
// Add the difference between
// current value and left max at index l
result += Math.max(0, l_max - arr[left]);
// Update left max
l_max = Math.max(l_max, arr[left]);
// Update left pointer
left += 1;
}
}
return result;
}
// Driver code
let arr = [ 0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1 ];
let N = arr.length;
document.write(maxWater(arr, N));
// This code is contributed by suresh07
</script>
C
// Implementation in C of the above approach
// Importing the required header files
#include <stdio.h> // Creating MACRO for finding the maximum number
#define max(x, y)(((x) > (y)) ? (x) : (y)) // Creating MACRO for finding the minimum number
#define min(x, y)(((x) < (y)) ? (x) : (y)) // Function to return the maximum
int maxWater(int arr[], int n)
{
// indices to traverse the array
int left = 0;
int right = n-1;
// To store Left max and right max
// for two pointers left and right
int l_max = 0;
int r_max = 0;
// To store the total amount
// of rain water trapped
int result = 0;
while (left <= right)
{
// We need check for minimum of left
// and right max for each element
if(r_max <= l_max)
{
// Add the difference between
// current value and right max at index r
result += max(0, r_max-arr[right]);
// Update right max
r_max = max(r_max, arr[right]);
// Update right pointer
right -= 1;
}
else
{
// Add the difference between
// current value and left max at index l
result += max(0, l_max-arr[left]);
// Update left max
l_max = max(l_max, arr[left]);
// Update left pointer
left += 1;
}
}
return result;
}
// driver code
int main() {
int arr[] = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
int N = sizeof(arr) / sizeof(arr[0]);
printf("%d", maxWater(arr, N));
return 0;
}
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to return the maximum
// water that can be stored
int maxWater(int arr[], int n)
{
int size = n - 1;
// Let the first element be stored as
// previous, we shall loop from index 1
int prev = arr[0];
// To store previous wall's index
int prev_index = 0;
int water = 0;
// To store the water until a larger wall
// is found, if there are no larger walls
// then delete temp value from water
int temp = 0;
for (int i = 1; i <= size; i++) {
// If the current wall is taller than
// the previous wall then make current
// wall as the previous wall and its
// index as previous wall's index
// for the subsequent loops
if (arr[i] >= prev) {
prev = arr[i];
prev_index = i;
// Because larger or same
// height wall is found
temp = 0;
}
else {
// Since current wall is shorter than
// the previous, we subtract previous
// wall's height from the current wall's
// height and add it to the water
water += prev - arr[i];
// Store the same value in temp as well
// If we dont find any larger wall then
// we will subtract temp from water
temp += prev - arr[i];
}
}
// If the last wall was larger than or equal
// to the previous wall then prev_index would
// be equal to size of the array (last element)
// If we didn't find a wall greater than or equal
// to the previous wall from the left then
// prev_index must be less than the index
// of the last element
if (prev_index < size) {
// Temp would've stored the water collected
// from previous largest wall till the end
// of array if no larger wall was found then
// it has excess water and remove that
// from water variable
water -= temp;
// We start from the end of the array,
// so previous should be assigned to
// the last element
prev = arr[size];
// Loop from the end of array up to the
// previous index which would contain
// the largest wall from the left
for (int i = size; i >= prev_index; i--) {
// Right end wall will be definitely
// smaller than the 'previous index' wall
if (arr[i] >= prev) {
prev = arr[i];
}
else {
water += prev - arr[i];
}
}
}
// Return the maximum water
return water;
}
// Driver Code
int main()
{
int arr[] = { 0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1 };
int N = sizeof(arr) / sizeof(arr[0]);
cout << maxWater(arr, N);
return 0;
}
// This code is contributed by Debidutta Rath
Java
// Java implementation of the approach
class GFG {
// Function to return the maximum
// water that can be stored
public static int maxWater(int arr[], int n)
{
int size = n - 1;
// Let the first element be stored as
// previous, we shall loop from index 1
int prev = arr[0];
// To store previous wall's index
int prev_index = 0;
int water = 0;
// To store the water until a larger wall
// is found, if there are no larger walls
// then delete temp value from water
int temp = 0;
for (int i = 1; i <= size; i++) {
// If the current wall is taller than
// the previous wall then make current
// wall as the previous wall and its
// index as previous wall's index
// for the subsequent loops
if (arr[i] >= prev) {
prev = arr[i];
prev_index = i;
// Because larger or same height wall is
// found
temp = 0;
}
else {
// Since current wall is shorter than
// the previous, we subtract previous
// wall's height from the current wall's
// height and add it to the water
water += prev - arr[i];
// Store the same value in temp as well
// If we dont find any larger wall then
// we will subtract temp from water
temp += prev - arr[i];
}
}
// If the last wall was larger than or equal
// to the previous wall then prev_index would
// be equal to size of the array (last element)
// If we didn't find a wall greater than or equal
// to the previous wall from the left then
// prev_index must be less than the index
// of the last element
if (prev_index < size) {
// Temp would've stored the water collected
// from previous largest wall till the end
// of array if no larger wall was found then
// it has excess water and remove that
// from 'water' var
water -= temp;
// We start from the end of the array, so
// previous should be assigned to the last
// element
prev = arr[size];
// Loop from the end of array up to the
// 'previous index' which would contain the
// "largest wall from the left"
for (int i = size; i >= prev_index; i--) {
// Right end wall will be definitely smaller
// than the 'previous index' wall
if (arr[i] >= prev) {
prev = arr[i];
}
else {
water += prev - arr[i];
}
}
}
// Return the maximum water
return water;
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1 };
int N = arr.length;
System.out.print(maxWater(arr, N));
}
}
Python3
# Python3 implementation of the approach # Function to return the maximum # water that can be stored def maxWater(arr, n): size = n - 1 # Let the first element be stored as # previous, we shall loop from index 1 prev = arr[0] # To store previous wall's index prev_index = 0 water = 0 # To store the water until a larger wall # is found, if there are no larger walls # then delete temp value from water temp = 0 for i in range(1, size + 1): # If the current wall is taller than # the previous wall then make current # wall as the previous wall and its # index as previous wall's index # for the subsequent loops if (arr[i] >= prev): prev = arr[i] prev_index = i # Because larger or same height wall is found temp = 0 else: # Since current wall is shorter than # the previous, we subtract previous # wall's height from the current wall's # height and add it to the water water += prev - arr[i] # Store the same value in temp as well # If we dont find any larger wall then # we will subtract temp from water temp += prev - arr[i] # If the last wall was larger than or equal # to the previous wall then prev_index would # be equal to size of the array (last element) # If we didn't find a wall greater than or equal # to the previous wall from the left then # prev_index must be less than the index # of the last element if (prev_index < size): # Temp would've stored the water collected # from previous largest wall till the end # of array if no larger wall was found then # it has excess water and remove that # from 'water' var water -= temp # We start from the end of the array, so previous # should be assigned to the last element prev = arr[size] # Loop from the end of array up to the 'previous index' # which would contain the "largest wall from the left" for i in range(size, prev_index - 1, -1): # Right end wall will be definitely smaller # than the 'previous index' wall if (arr[i] >= prev): prev = arr[i] else: water += prev - arr[i] # Return the maximum water return water # Driver code if __name__ == '__main__': arr = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1] N = len(arr) print(maxWater(arr, N)) # This code is contributed by Mohit Kumar
C#
// C# implementation of the approach
using System;
class GFG {
// Function to return the maximum
// water that can be stored
static int maxWater(int[] arr, int n)
{
int size = n - 1;
// Let the first element be stored as
// previous, we shall loop from index 1
int prev = arr[0];
// To store previous wall's index
int prev_index = 0;
int water = 0;
// To store the water until a larger wall
// is found, if there are no larger walls
// then delete temp value from water
int temp = 0;
for (int i = 1; i <= size; i++) {
// If the current wall is taller than
// the previous wall then make current
// wall as the previous wall and its
// index as previous wall's index
// for the subsequent loops
if (arr[i] >= prev) {
prev = arr[i];
prev_index = i;
// Because larger or same
// height wall is found
temp = 0;
}
else {
// Since current wall is shorter than
// the previous, we subtract previous
// wall's height from the current wall's
// height and add it to the water
water += prev - arr[i];
// Store the same value in temp as well
// If we dont find any larger wall then
// we will subtract temp from water
temp += prev - arr[i];
}
}
// If the last wall was larger than or equal
// to the previous wall then prev_index would
// be equal to size of the array (last element)
// If we didn't find a wall greater than or equal
// to the previous wall from the left then
// prev_index must be less than the index
// of the last element
if (prev_index < size) {
// Temp would've stored the water collected
// from previous largest wall till the end
// of array if no larger wall was found then
// it has excess water and remove that
// from water variable
water -= temp;
// We start from the end of the array,
// so previous should be assigned to
// the last element
prev = arr[size];
// Loop from the end of array up to the
// previous index which would contain
// the largest wall from the left
for (int i = size; i >= prev_index; i--) {
// Right end wall will be definitely
// smaller than the 'previous index' wall
if (arr[i] >= prev) {
prev = arr[i];
}
else {
water += prev - arr[i];
}
}
}
// Return the maximum water
return water;
}
// Driver code
static void Main()
{
int[] arr = { 0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1 };
int N = arr.Length;
Console.WriteLine(maxWater(arr, N));
}
}
// This code is contributed by divyesh072019
Javascript
<script>
// JavaScript implementation of the approach
// Function to return the maximum
// water that can be stored
function maxWater(arr,n)
{
let size = n - 1;
// Let the first element be stored as
// previous, we shall loop from index 1
let prev = arr[0];
// To store previous wall's index
let prev_index = 0;
let water = 0;
// To store the water until a larger wall
// is found, if there are no larger walls
// then delete temp value from water
let temp = 0;
for (let i = 1; i <= size; i++) {
// If the current wall is taller than
// the previous wall then make current
// wall as the previous wall and its
// index as previous wall's index
// for the subsequent loops
if (arr[i] >= prev) {
prev = arr[i];
prev_index = i;
// Because larger or same height wall is found
temp = 0;
}
else {
// Since current wall is shorter than
// the previous, we subtract previous
// wall's height from the current wall's
// height and add it to the water
water += prev - arr[i];
// Store the same value in temp as well
// If we dont find any larger wall then
// we will subtract temp from water
temp += prev - arr[i];
}
}
// If the last wall was larger than or equal
// to the previous wall then prev_index would
// be equal to size of the array (last element)
// If we didn't find a wall greater than or equal
// to the previous wall from the left then
// prev_index must be less than the index
// of the last element
if (prev_index < size) {
// Temp would've stored the water collected
// from previous largest wall till the end
// of array if no larger wall was found then
// it has excess water and remove that
// from 'water' var
water -= temp;
// We start from the end of the array, so previous
// should be assigned to the last element
prev = arr[size];
// Loop from the end of array up to the 'previous index'
// which would contain the "largest wall from the left"
for (let i = size; i >= prev_index; i--) {
// Right end wall will be definitely smaller
// than the 'previous index' wall
if (arr[i] >= prev) {
prev = arr[i];
}
else {
water += prev - arr[i];
}
}
}
// Return the maximum water
return water;
}
// Driver code
let arr=[ 0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1];
let N = arr.length;
document.write(maxWater(arr, N));
// This code is contributed by patel2127
</script>
C
// Implementation in C of the above approach
// Importing the required header files
#include <stdio.h> // Creating MACRO for finding the maximum number
#define max(x, y) \
(((x) > (y)) ? (x) : (y)) // Creating MACRO for finding
// the minimum number
#define min(x, y) \
(((x) < (y)) ? (x) \
: (y)) // Function to return the maximum
// water that can be stored
int maxWater(int arr[], int n)
{
int size = n - 1;
// Let the first element be stored as
// previous, we shall loop from index 1
int prev = arr[0];
// To store previous wall's index
int prev_index = 0;
int water = 0;
// To store the water until a larger wall
// is found, if there are no larger walls
// then delete temp value from water
int temp = 0;
for (int i = 1; i <= size; i++) {
// If the current wall is taller than
// the previous wall then make current
// wall as the previous wall and its
// index as previous wall's index
// for the subsequent loops
if (arr[i] >= prev) {
prev = arr[i];
prev_index = i;
// Because larger or same
// height wall is found
temp = 0;
}
else {
// Since current wall is shorter than
// the previous, we subtract previous
// wall's height from the current wall's
// height and add it to the water
water += prev - arr[i];
// Store the same value in temp as well
// If we dont find any larger wall then
// we will subtract temp from water
temp += prev - arr[i];
}
}
// If the last wall was larger than or equal
// to the previous wall then prev_index would
// be equal to size of the array (last element)
// If we didn't find a wall greater than or equal
// to the previous wall from the left then
// prev_index must be less than the index
// of the last element
if (prev_index < size) {
// Temp would've stored the water collected
// from previous largest wall till the end
// of array if no larger wall was found then
// it has excess water and remove that
// from water variable
water -= temp;
// We start from the end of the array,
// so previous should be assigned to
// the last element
prev = arr[size];
// Loop from the end of array up to the
// previous index which would contain
// the largest wall from the left
for (int i = size; i >= prev_index; i--) {
// Right end wall will be definitely
// smaller than the 'previous index' wall
if (arr[i] >= prev) {
prev = arr[i];
}
else {
water += prev - arr[i];
}
}
}
// Return the maximum water
return water;
}
// driver code
int main()
{
int arr[] = { 0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1 };
int N = sizeof(arr) / sizeof(arr[0]);
printf("%d", maxWater(arr, N));
return 0;
}
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA