Rainwater Harvesting Problem in Java

#1

I am unable to clear testcase 6,7 and 8. It says my code is too slow for these test cases.
This is my code:

import java.util.*;
public class Main {
public static void main(String args[]) {

	Scanner scn = new Scanner(System.in);
	int n = scn.nextInt();
	int[] arr = new int[n];
	for(int i =0;i<n;i++){
		arr[i]=scn.nextInt();
	}
	int water_total = 0;
	for(int i = 1;i<n-1;i++){
		int lmax = maxleftarray(arr,i-1);
		int rmax = maxrightarray(arr,i+1);
		if(lmax>rmax && rmax-arr[i]>=0){
			int water_in_this_block = rmax-arr[i];
			water_total = water_total + water_in_this_block;
		}else if(rmax>lmax && lmax-arr[i]>=0){
			int water_in_this_block = lmax-arr[i];
			water_total = water_total + water_in_this_block;
		}else if(rmax==lmax && lmax-arr[i]>=0){
			int water_in_this_block = lmax-arr[i];
			water_total = water_total + water_in_this_block;
		}
		
	}
	System.out.print(water_total);
	
}

public static int maxleftarray(int[] arr,int hi){
int lmax = arr[0];
for(int i = 0;i<=hi;i++){
if(arr[i]>lmax){
lmax = arr[i];
}
}
return lmax;
}

	public static int maxrightarray(int[] arr,int lo){
		int rmax = arr[lo];
		for(int i = lo;i<=arr.length-1;i++){
			if(arr[i]>rmax){
				rmax = arr[i];
			}
		}
		return rmax;
	}

}

How can i optimize my code to clear all the test cases?

#2

@Raunak-Agrawal-1537545869717573,
There are multiple solutions to this question.

Naive Solution

A Simple Solution is to traverse every array element and find the highest bars on left and right sides. Take the smaller of two heights. The difference between the smaller height and height of the current element is the amount of water that can be stored in this array element. Time complexity of this solution is O(n^2).

Better Approach

An element of an array can store water if there are higher bars on left and right. We can find the amount of water to be stored in every element by finding the heights of bars on the left and right sides. The idea is to compute the amount of water that can be stored in every element of the array. For example, consider the array {3, 0, 0, 2, 0, 4}, we can store two units of water at indexes 1 and 2, and one unit of water at index 2.

Pre-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.

Best Approach

Use the two pointer approach. Loop from index 0 to the end of the given array. If a wall greater than or equal to the previous wall is encountered then make note of the index of that wall in a var called prev index. Keep adding previous wall’s height minus the current (ith) wall to the variable water. Have a temporary variable that stores the same value as water. If no wall greater than or equal to the previous wall is found then quit. If prev index < size of the input array then subtract the temp variable from water, and loop from end of the input array to prev_index and find a wall greater than or equal to the previous wall (in this case, the last wall from backwards).

#3

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.