Rain Water Trapped

Problem

Given an array arr[] of N non-negative integers representing height of blocks at index i as Ai where the width of each block is 1. Compute how much water can be trapped in between blocks after raining.

Problem Constraints

1 <= |arr| <= 100000

Example Input

Input 1:

A = [0, 1, 0, 2]

Input 2: 

 A = [1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]

Example Output

Output 1:

1

Output 2:

6

 Question Link

https://leetcode.com/problems/trapping-rain-water/
https://practice.geeksforgeeks.org/problems/trapping-rain-water/0 

Solution

We have to calculate the amount of water to be stored in between the blocks.

Solution 1: Brute Force

In Brute force approach, We do what it says in the question. For each element in the array, we find the maximum amount of water it can trap. we calculate the minimum of the maximum of left side and right side of the element.

Algorithm

  • Initialize res = 0;
  • Iterate the array from left to right:
    • Initialize left_max = Integer.MIN_VALUE and right_max = Integer.MIN_VALUE
    • Iterate from the current element to the beginning of the array updating:
      • left_max = Math.max(left_max, A.get(i)); 
    • Iterate from the current element to the end of the array updating:
      • right_max = Math.max(right_max,A.get(i));
    • Add Math.min(left_max,right_max) - A.get(i) to the res. 

Here is the solution looks like:

public class Solution {
    // DO NOT MODIFY THE LIST. IT IS READ ONLY
    public int trap(final List<Integer> A) {
        
        int res = 0;
        int sum = 0;
        int max = Integer.MIN_VALUE;
        int max1 = Integer.MIN_VALUE;
        
        for(int i=1;i<A.size()-1;i++){
            sum = Integer.MAX_VALUE;
            max = Integer.MIN_VALUE;
            for(int j = i-1;j>=0;j--){
                max = Math.max(max,A.get(j));
            }
            max1 = Integer.MIN_VALUE;
            for(int j=i+1;j<A.size();j++){
                max1 = Math.max(max1,A.get(j));
            }
            sum = Math.min(max,max1);
            if((sum-A.get(i))>0)
            res += sum-A.get(i);
        }
        return res;
    }
}

Complexity Analysis:

  • Time Complexity: O(n^2)
  • Space Complexity: O(1)

Solution 2: Using concept of prefix and suffix max 

In the brute force solution, At every step, we iterate to the left and to the right from the element to find the maximum value. After that, we calculate the minimum of these two and calculate the amount of water stored at each element.

Instead of iterating through the left and to right, we store the maximum value at each element in the array. First, iterate through left to right and store the maximum at that position in a leftMax array and second we iterate through right to left and store the maximum at that position in a rightMax array. This approach is similar to calculating the prefix sum of the array. In this approach, we calculate the maximum to the left and maximum to the right in O(1) time. After that, we find the minimum of the maximum of the left and right sides from that element.

Algorithm:

  • Initialize leftMax[], rightMax[], res=0; 
  • leftMax[0] = A[0]; 
  • rightMax[A.length-1] = A[A.length-1];
  • Iterate the array from left to right. 
    • leftMax[i] = Math.max( leftMax[i-1],A[i]);
  • Iterate the array from right to left. 
    • rightMax[i] = Math.max(rightMax[i+1], A[i]);
  • Iterate the array from left to right. 
    • res += Math.min(leftMax[i],rightMax[i]) - A[i]; 

Here is the solution looks like:

public class Solution {
    // DO NOT MODIFY THE LIST. IT IS READ ONLY
    public int trap(final List<Integer> A) {
        int size = A.size();
        int Left_arr[] = new int[size];
        int Right_arr[] = new int[size];
        int max=0;
        for(int i=0;i<size;i++)
        {
            if(i==0)
            Left_arr[i]=0;
            else{
                if(A.get(i-1)>max)
                {
                    max=A.get(i-1);
                    Left_arr[i]=max;
                }
                else
                {
                    Left_arr[i]=max;
                }
            }
        }
        max=0;
        for(int i=size-1;i>=0;i--)
        {
            if(i==size-1)
            Right_arr[i]=0;
            else
            {
                if(A.get(i+1)>max)
                {
                    max=A.get(i+1);
                    Right_arr[i+1]=max;
                }
                else
                {
                    Right_arr[i+1]=max;
                }
            }
        }
        int min=0,total=0,area=0;
        for(int i=0;i<size;i++)
        {
            min = Math.min(Left_arr[i],Right_arr[i]);
            area = min-A.get(i);
            if(area>=0)
            total+=area;
        }
        return total;
    }
}

Complexity Analysis:

  • Time Complexity: O(n)
  • Space Complexity: O(n) 

Solution 3: Optimal Solution Using 2 Pointers

Our task is to find the maximum to the left and maximum to the right from the element of the array. In our previous approach, to find the maximum to the left and maximum to the right is stored in an array. we have to find the solution to find the maximum in O(1) approach. 

Instead of maintaining two arrays for storing left and right maximum of each element, we maintain two variables to store the maximum till that point. Water stored at any element = Math.min(maxLeft,maxRight) - A[i].

Algorithm: 

  • Initialize left pointer to 0 and right pointer to A.size - 1.
  • Initialize leftMax = 0, rightMax = 0, res = 0.
  • while left <= right:
    •  if(A[left] < A[right]):
      • if(leftMax < A[left]):
        • leftMax = A[left]
      • else: 
        • res += leftMax - A[left]
      • left ++;
    • else: 
      • if(rightMax < A[right]):
        • rightMax = A[right]
      • else:
        • res += rightMax - A[right]
      • right --;

Here is the solution looks like:

public class Solution {
    // DO NOT MODIFY THE LIST. IT IS READ ONLY
    public int trap(final List<Integer> A) {
        int right = A.size()-1;
        int left = 0;
        int rightMax = 0;
        int leftMax = 0;
        int res = 0;
        while(left<=right){
            if(A.get(left)<A.get(right)){
                if(A.get(left)>leftMax)
                leftMax = A.get(left);
                else
                res+=leftMax-A.get(left);
                left++;
            }
            else{
                if(A.get(right)>rightMax)
                rightMax = A.get(right);
                else
                res+=rightMax - A.get(right);
                right--;
            }
        }
        return res;
    }
}

Complexity Analysis:

  • Time Complexity: O(n)
  • Space Complexity: O(1)

Comments

Post a Comment

Popular posts from this blog

Beggars Outside Temple

Problem There are   N   ( N > 0 ) beggars sitting in a row outside a temple. Each beggar initially has an empty pot. When the devotees come to the temple, they donate some amount of coins to these beggars. Each devotee gives a fixed amount of coin(according to his faith and ability) to some   K   beggars sitting next to each other. Given the amount donated by each devotee to the beggars ranging from   i   to   j   index, where   1   <=   i   <=   j   <=   N , find out the final amount of money in each beggar's pot at the end of the day, provided they don't fill their pots by any other means. Example Input: N = 5, D = [[1, 2, 10], [2, 3, 20], [2, 5, 25]] Return: [10, 55, 45, 25, 25] Explanation: => First devotee donated 10 coins to beggars ranging from 1 to 2. Final amount in each beggars pot after first devotee: [10, 10, 0, 0, 0] => Second devotee donated 20 coins to beggars ranging from 2 to...
Read more

Difference between Static Array and Dynamic Array

Image
  An array is a collection of similar types of data. Each data item present in the array is called the element of the array. The elements of the array share the same variable name but each element has a different index number. Arrays used to organize data and provide operations such as searching and sorting of data. There are two types of arrays: Static Arrays Dynamic Arrays Static Arrays Static Arrays is a collection of similar types of data stored at contiguous memory location. Store multiple item of a same type together. In Java:  char[] arr = new char[size of Array]; To access element: 0 based indexing. arr[0] - 1st element of the array. Size of arr = arr.length; last element of the array = arr[arr.length-1]; Dynamic Arrays: In dynamic array, we store the collection of similar types of element but we cannot define the size of the array. In Java dynamic array is created using ArrayList which is the implementation of List interface. When we declare the ArrayList, it creates ...
Read more