Skip to content

Instantly share code, notes, and snippets.

@vivekpanchal
Created March 20, 2020 09:03
Show Gist options
  • Save vivekpanchal/67aaf8772502a33d4c5c781cf0aa5741 to your computer and use it in GitHub Desktop.
Save vivekpanchal/67aaf8772502a33d4c5c781cf0aa5741 to your computer and use it in GitHub Desktop.
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class Main {
public static void main(String[] args) {
int[] case1 = {2, 0, 2};
int[] case2 = {3, 0, 0, 2, 0, 4};
int[] case3 = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
int[] case4 = {1, 4, 1, 2, 5, 1, 2, 3, 1};
int[] case5 = {5, 0, 4, 0, 3, 0, 2}; //9 output
System.out.println("water that's filled will be == " + calculateTheVolumeWaterCanReside(case1, case1.length));
System.out.println("water that's filled will be == " + calculateTheVolumeWaterCanReside(case2, case2.length));
System.out.println("water that's filled will be == " + calculateTheVolumeWaterCanReside(case3, case3.length));
System.out.println("water that's filled will be == " + calculateTheVolumeWaterCanReside(case4, case4.length));
System.out.println("water that's filled will be == " + calculateTheVolumeWaterCanReside(case5, case5.length));
}
public static int calculateTheVolumeWaterCanReside(int[] arr, int n) {
System.out.println("got array " + Arrays.toString(arr));
int size = n - 1;//size for the loop
int water = 0;//water stored
// Let the previous wall height will be
int prev = arr[0];
// To store previous wall's index
int prev_index = 0;
//* Have a temporary variable that stores the same value as water.
int temp = 0;
for (int i = 1; i <= size; i++) {
// System.out.println("*****************************************************************************************");
// System.out.println("at index " + i + " current element is " + arr[i]);
// System.out.println("current previous wall index = " + prev_index + " current previous wall height = " + prev);
// If the current wall is taller than
// the previous wall then make current
// wall as the previous wall and its
// index as previous wall's index
// for the subsequent loops
if (arr[i] >= prev) {
// System.out.println("current index greater than equal to previous wall index ");
prev = arr[i];
prev_index = i;
// System.out.println("now changing the previous wall index =" + prev_index + "and previous wall height = " + prev);
// Because larger or same height wall is found
temp = 0;
} else {
//* Keep adding the previous wall’s height minus the current (ith) wall to the variable water.
water += prev - arr[i];
// System.out.println("adding the value for wall height - current wall to water = " + water);
// Store the same value in temp as well
// If we don't find any larger wall then
// we will subtract temp from water
temp += prev - arr[i];
}
}
if (prev_index < size) {
water -= temp;
// System.out.println("No larger wall found so water have excess water so we remove it " + water);
prev = arr[size];
// System.out.println("previous wall should be assigned to the last element" + prev);
// System.out.println("looping through the end of array till the previous wall index which could have largest wall from left ");
// Loop from the end of array up to the 'previous index' which was our previous wall height
for (int i = size; i >= prev_index; i--) {
// Right end wall should be smaller than prev index wall
if (arr[i] >= prev) {
prev = arr[i];
// System.out.println("current array index is greater than equal to previous wall height so assigning it to be the new previous wall height \n new previous wall height is = " + prev);
} else {
water += prev - arr[i];
// System.out.println("keep adding the previous wall height - current index to the water " + water);
}
}
}
return water;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment