Code Pumpkin

Trapping Rain Water | Algorithm Problem

October 29, 2017
Posted by Pumpkin
Subscribe

In this article, we are going to solve the trapping water problem also known as Raees's Liquor Tank 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/liquor 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 

Trapped Rain Water


Other Test Cases
 

Case 1 :

Input = [3, 0, 3]

Output = 3

Case 2 :

Input = [0, 4, 5, 1]

Output = 0

Case 3 :

Input = [ 1, 4, 2, 5, 0, 6, 2, 3, 4]

Output = 2 + 5 + 2 + 1
               = 10


when will rain water be trapped on any Bar?

For water to get accumulated on bar B, there should be higher sized bars present on left and right side of that bar B. (i.e. bars with height greater than the hight of bar B)

Trapping Rain Water Cases


How much rain water will be trapped on each bar?

Trapping Rain Water At Each Index

So for example, 
       water trapped at index 5 = min(2,3) – 1 = 1
                                        index 6 = min(2,3) – 0 = 2
                                        index 7 = min(2,3) – 1 = 1


Solution Approaches

Using above facts, we can think of two approaches to solve this problem:

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(n2) 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.

Trapping Rain Water left and right computation

3. Now at any point of the bar the maximum water that can be trapped will be minimum of left height and right height minus the height of the bar.

Amount of water stored on the top of the bar i  = (maximum of left(i) and right(i))  – arr(i)

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 ( A0 — 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);
    }
}

That's all for this topic. If you guys have any suggestions or queries, feel free drop a comment. We would be happy to add that in our post. You can also contribute your articles by creating contributor account here

Happy Learning 🙂

You can also check the other articles on sorting and searching such as selection sortbinary searchfibonacci searchbubble sort etc.  You will also like to enhance your knowledge by going through our other articles on different algorithms and data structures.


Further Reading For interview Preparation

  1. Program To Find Unique Array Element
  2. Program To Check Whether A Number Is Prime Or Not
  3. Program To Check If A Given Number Is Power Of Two Or Not?
  4. Program To Find Number Of Set Bits In The Binary Number
  5. Sudoku Solver
  6. N Queen Problem
  7. Graph Search – Breadth First Search
  8. Graph Search – Depth First Search
  9. interface VS abstract class
  10. Access Modifiers (public, private, protected and default scope)
  11. HashMap vs Hashtable Vs SynchronizedMap Vs ConcurrentHashMap
  12. CountDownLatch Vs CyclicBarrier

Tags: , , , ,


Comments and Queries

If you want someone to read your code, please put the code inside <pre><code> and </code></pre> tags. For example:
<pre><code class="java"> 
String foo = "bar";
</code></pre>
For more information on supported HTML tags in disqus comment, click here.

Total Post : 80
Subscribe
Contribute Your Articles

Interview Experiences

Related Books

Like Us On Facebook

Alexa Page Rank