Arrays - Trapping Rainwater - Brute Force Solution

Question: Given an array of integers representing an elevation map (bar chart) where width of each bar is one, return how much rain water can be trapped in empty space.

input [0,1,0,2,1,0,3,1,0,1,2]
output 8

Constraints need to ask because solution may change according to given constraints

Question: Sides of graph can be count as wall?
Answer: No

Question: Will there be negative integers?
Answer: No

Question: What will be output for empty array?
Answer: 0

Question: What will be output when only 1 value in array?
Answer: 0

Question: What will be output when input array like [3,4,3]?
Answer: 0, no empty space to store water because walls cannot be used and water also fells from right side.

Note: Max water can go to the mark is minimum height of bar between 2 bars and if there is a small bar present in between it will reduce the water quantity as shown in above image with black color.

Solution Thinking trick: Try to break problem as much as we can, so let's divide the from finding total water for given array to finding water capacity for each integer one by one and we can reach to this formula.

* formula: currentWater = maxSideValue - currentHeight
* currentWater - water present at integer which we want to calculate
* maxSideValue = maxValue of respective side either left or right
* currentHeight - Height of currentWater

Solution using JAVA language.

Brute Force algorithm - In brute force solution, we try to check each and every possible combination through array and polynomial time complexity.

public class TrappingRainwaterBruteForce {
    public static void main(String[] args) {
        int[] input = new int[]{0,1,0,2,1,0,3,1,0,1,2};
        int totalRainwaterCollected = TrappingRainwaterBruteForce.getTrappedRainwater(input);
        System.out.println("Total Trapped water is: "+totalRainwaterCollected);
    }

    public static int getTrappedRainwater(int[] arr) {
        int totalWater = 0;
        int length = arr.length;
        for (int i = 0; i < length; i++) {
            int currentHeight = arr[i];
            int maxLeft = findMax(arr, 0, i);
            int maxRight = findMax(arr, i, length - 1);
            int minHeight = Math.min(maxLeft, maxRight);
            int currentWater = minHeight - currentHeight;
            if (currentWater > 0) {
                totalWater += currentWater;
            }
        }
        return totalWater;
    }

    public static int findMax(int[] arr, int startIndex, int endIndex) {
        int max = 0;
        for (int i = startIndex; i <= endIndex; i++) {
            if(arr[i] > max){
                max = arr[i];
            }
        }
        return max;
    }
}                           

Output: 8                   

Time Complexity: O(N^2)

Space Complexity: O(1)

Optimal solution click here.

Note: Find question at Leetcode