In this article, we are going to solve the trapping water problem. This kind of problems are asked very frequently in interviews and online programming challenges.

Problem Statement

We need to find the maximum volume of water that can be stored in between buildings or bars as shown in the below image. Assume that width of each bar is 1. 

In other words, Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

int arr[]  = {0, 1, 0, 2, 1, 0, 1,  3, 2, 1, 2, 1};

Answer : 6 Unit 

Approach 1 (Naive Approach)

1. Traverse every array element
2. For each element,
   – Find the highest bars on left and right sides.
   – Take the smaller of two heights.
   – The difference between smaller height and height of current element is the amount of water that can be stored in this array element.
3. Time complexity of this solution is O(n²) as
   – we are traversing each element i.e. n times +
   – for each element we are searching left and right bar with max hight i.e. again n times.

This is not very efficient solution for the given problem.

Approach 2

We can to prre-compute highest bar on left and right of every bar in O(n) time. Then use these pre-computed values to find the amount of water in every array element. This solution is O(n) and more efficient than the previous one.

We will implement the second solution:

Algorithm:

1. First compute highest bar on the left of every bar in O(n)
     –  by getting maximum between height of current bar and height of the previous tallest bar. Store this maximum value at the current index of left array.

2. Similarly compute highest bar on the right of every bar in  O(n) and store it in right array.

Here is the graphical representation of above two steps.

4. Keep adding the value for each bar.

Yeah… We solved it. 

Below is the Java code for the same.  This code input as below:

• First line of input contains a single integer N which is number of bars.
• Second line of input contains N non-negative integers ( A₀ — A_(n-1) ) which are height of each bar.

and it will print the output as number of unit we can hold between these bars.

package com.pumpkin.basic

import java.io.BufferedReader;
import java.io.InputStreamReader;

class TestClass {
	public static void main(String args[]) throws Exception {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String[] str = br.readLine().split(" ");
        int[] arr = new int[n];
        for(int i=0; i<n; i++)
        {
            arr[i] = Integer.parseInt(str[i]);
        }
        int[] left = new int[n];
        int[] right = new int[n];
        
        left[0] = arr[0];
        for(int i=1; i<n; i++)
        {
            left[i] = Math.max(left[i-1],arr[i]);
        }
        
        right[n-1] = arr[n-1];
        for(int i=n-2; i>=0; i--)
        {
            right[i] = Math.max(right[i+1],arr[i]);
        }
        
        int total = 0;
        for(int i=0; i<n; i++)
        {
            total += Math.min(left[i],right[i]) - arr[i];
        }
        System.out.println(total);
    }
}

You can also check the other articles on sorting and searching such as selection sort, binary search, fibonacci search, bubble sort etc.  You will also like to enhance your knowledge by going through our other articles on different algorithms and data structures.