Java Challenge - Capturing Rainwater

This community-built FAQ covers the “Capturing Rainwater” code challenge in Java. You can find that challenge here, or pick any challenge you like from our list.

Top Discussions on the Java challenge Capturing Rainwater

There are currently no frequently asked questions or top answers associated with this challenge – that’s where you come in! You can contribute to this section by offering your own questions, answers, or clarifications on this challenge. Ask a question or post a solution by clicking reply (reply) below.

If you’ve had an “aha” moment about the concepts, formatting, syntax, or anything else with this challenge, consider sharing those insights! Teaching others and answering their questions is one of the best ways to learn and stay sharp.

Join the Discussion. Help a fellow learner on their journey.

Ask or answer a question about this exercise by clicking reply (reply) below!
You can also find further discussion and get answers to your questions over in Language Help.

Agree with a comment or answer? Like (like) to up-vote the contribution!

Need broader help or resources? Head to Language Help and Tips and Resources. If you are wanting feedback or inspiration for a project, check out Projects.

Looking for motivation to keep learning? Join our wider discussions in Community

Learn more about how to use this guide.

Found a bug? Report it online, or post in Bug Reporting

Have a question about your account or billing? Reach out to our customer support team!

None of the above? Find out where to ask other questions here!

public static int capturingRainwater(int heights) {
int leftIndex = 0;
int rightIndex = heights.length - 1;
int leftHighest = 0;
int rightHighest = 0;
int waterSum = 0;
while (leftIndex < rightIndex) {
if (heights[leftIndex] < heights[rightIndex]) {
if (leftHighest < heights[leftIndex]) {
leftHighest = heights[leftIndex];
leftIndex++;
} else {
waterSum += leftHighest - heights[leftIndex];
leftIndex++;
}
} else {
if (rightHighest < heights[rightIndex]) {
rightHighest = heights[rightIndex];
rightIndex–;
} else {
waterSum += rightHighest - heights[rightIndex];
rightIndex–;
}
}
}
return waterSum;
}

My code is largely the same as the code in the other posts ion this topic,
except that I made helper function for finding the index of a max (looking either from the left or from the right of a given index) and a helper function for finding the volume between two indices.
Unfortunately, my code is long.

my code
public class CapturingRainwater {
  public static void main(String[] args) {
    int[] heights = new int[] {4, 2, 1, 3, 0, 1, 2};
    printArray(heights);
    System.out.println(capturingRainwater(heights));
  }

  public static void printArray(int[] array) {
    int length = array.length;
    if (length < 1) { System.out.print("[]"); }
    System.out.print("[");
    for (int i = 0; i < length - 1; i++) {
      System.out.print(array[i] + ", ");
    }
    System.out.print(array[length - 1]);
    System.out.println("]");
  }

  public static int getIndexOfMax(int[] array, int start) {
    int length = array.length;
    if (start >= length) {
      return start;
    }
    int maxIndex = start;
    int max = array[start];
    for (int i = start; i < length; i++) {
      if (array[i] > max) {
        max = array[i];
        maxIndex = i;
      }
    }
    return maxIndex;
  }
  public static int getIndexOfMax(int[] array) {
    return getIndexOfMax(array, 0);
  }

  public static int getIndexOfMaxBeforeIndex(int[] array, int index) {
    int length = array.length;
    if (index < 0) {
      return index;
    }
    else if (index >= length) {
      index = length - 1;
    }
    int max = array[index];
    for (int j = index; j >= 0; j--) {
      if (array[j] > max) {
        max = array[j];
        index = j;
      }
    }
    return index;
  }
  
  public static int getVolumeBetween(int[] height, int a, int b) { 
    // a is starting index, b is ending index, must use a < b
    if (a == b) {
      return 0;
    }
    int level = height[a];
    if (height[b] < height[a]) {
      level = height[b];
    }
    int totalVolume = 0;
    for (int i = a + 1; i < b; i++) {
      int elevation = height[i];
      if (elevation < level) {
        totalVolume += (level - elevation);
      }
    }
    return totalVolume;
  }

  public static int capturingRainwater(int[] heights) {
    int length = heights.length;
    if (length <= 2) {
      return 0;
    }
    int indexOfMax = getIndexOfMax(heights);
    int rainwater = 0;
    // right side of indexOfMax
    int a = indexOfMax;
    int b = getIndexOfMax(heights, a + 1);
    while(b < length) { 
      rainwater += getVolumeBetween(heights, a, b);
      a = b;
      b = getIndexOfMax(heights, a + 1);
    }
    // left side of indexOfMax
    b = indexOfMax;
    a = getIndexOfMaxBeforeIndex(heights, b - 1);
    while (a >= 0) {
      rainwater += getVolumeBetween(heights, a, b);
      b = a;
      a = getIndexOfMaxBeforeIndex(heights, b - 1);
    }

    return rainwater;
  }
}

Had a little different solution, might not be the most efficient but
it does give you a little picture of the solution as a bonus.

public class CapturingRainwater {
public static void main(String args) {
int heights = new int {4, 2, 1, 3, 0, 1, 2};
System.out.println(capturingRainwater(heights));
}

  public static int capturingRainwater(int[] heights) {

   // find max height
   int max = 0;
   for(int i=0; i<heights.length; i++)
   {
     if (heights[i] > max) max = heights[i];
   }
   System.out.println("max="+max);

   char chart[][] = new char[heights.length][max];
   // Fill chart with heights
   final char BLOCK = 'B';
   for(int i=0; i<heights.length; i++)
   {
      for(int h=0; h<heights[i];h++)
      {
        chart[i][h]=BLOCK;
      }
   }

   final char WATER = 'W';
   // fill chart with water = 1;
   
   int waterBlocks=0;
  for(int h=0; h<max;h++)
  {
        int left  = -1;
        int right = -1;
     for(int i=0; i<heights.length; i++)
     {
  
        if (chart[i][h] == BLOCK)
        {
           if (left==-1) { left = i;}
           else if (right == -1) 
           {  
             right = i;
             for(int w =left+1; w < right;w++)
             {

                chart[w][h]=WATER;
                waterBlocks++;
             }
           // reset search for barriers
           left=right;
           right=-1;
           } 
        }
      }
   }

 for(int h=max-1; h>=0;h--)
  {
     for(int i=0; i<heights.length; i++)
     {
             System.out.print(chart[i][h]);          
      }
        System.out.println();
   }
  return waterBlocks;
  }
}
1 Like

My approach and solution doesn’t make use of the naive/brute approach(i.e several nested for/loops traversing the array. Instead It uses the pre-calculated approach where left tallest bars and right tallest bars are stored in a left[i] and right[i] array. It’s efficient in terms of time complexity 0(N) as it only traverses the array one time. Space complexity: two extra arrays are needed of size N.
However even though code runs SUCCESSFULLY on the site and in my IDE, it only passes 4/5 test cases on codeAcademy’s code challenge engine. I added some sanity checks (i.e null array, array size less than 3, etc) , and it still can’t pass 5/5 test cases. I’m not sure what could be the problem.

Can someone from CodeAcademy help out or point out what the problem the test case it fails to pass could be? It’s seems to be a black box to me as it does not indicate why 4/5 passes and not the 5th test case. My code is posted below. I’d appreciate some feedback thanks.

public static int capturingRainwater(int heights) {
// Write your code here
// size of array
int n = heights.length;
if(heights == null ) return 0;
if(n < 1) return 0;
if(n < 3) return 0;
// Initialize var to store water
int water = 0;
// left array
int left = new int[n];
// right array
int right = new int[n];
//fill left array with pre-calculated tallest values
left[0] = heights[0];
for(int i=1; i < n; i++) {
left[i] = Math.max(left[i-1],heights[i]);
}
//fill right array with pre-calculated tallest values
right[n-1] = heights[n-1];
for(int i=n-2; i >= 0; i–) {
right[i] = Math.max(right[i+1],heights[i]);
}
// traverse array store water
for(int i=0; i < n; i++) {
water += Math.min(left[i],right[i] - heights[i]);
}
return water;
}
}

Your code didn’t produce the correct result for [3, 1, 4]

Hi Jan, Thanks for your reply and feedback. I will look and test the code with input [3,1,4] when I get a chance.
I appreciate the feedback on which test case my code fails.

Regards,

Leon

Hello Jan,
I added a check for when the height array only has 3 elements. I tested the array with elements [3,1,4] and the code now returns a value of 2 for total units of rainwater collected. (which is correct). However test cases still passes 4/5.
Below is the check code I added for when the heights array being passed has 3 elements. In this case [3,1,4]

public class CapturingRainwater {
public static void main(String args) {
int heights = new int {4, 2, 1, 3, 0, 1, 2};
// int heights = new int {3, 1, 4};
System.out.println(capturingRainwater(heights));
}
public static int capturingRainwater(int heights) {
// Write your code here
// size of array
int n = heights.length;
// Initialize var to store water
int water = 0;
// left array
int left = new int[n];
// right array
int right = new int[n];

if(heights == null ) return 0;
if(n < 1) return 0; 
if(n < 3) return 0;

// Check done when array has only 3 elements.
if(n == 3) {
  // Left corner value
  left[0] = heights[0];
    
  // Right corner value
  right[2] = heights[2];
  
  int MiddleVal = heights[1];
  int MinVal = Math.min(left[0],right[2]);
  water = water + (MinVal - MiddleVal);
  return water;
}

//fill left array with pre-calculated tallest values
left[0] = heights[0];
for(int i=1; i < n; i++) {
left[i] = Math.max(left[i-1],heights[i]);
}

//fill right array with pre-calculated tallest values
right[n-1] = heights[n-1];
for(int i=n-2; i >= 0; i--) {
  right[i] = Math.max(right[i+1],heights[i]);
}

// traverse array and store water
for(int i=0; i < n; i++) {
water += Math.min(left[i],right[i] - heights[i]);
}
return water;
}
}

I’d appreciate it if you looked at the lines below the // Check done when array has only 3 elements comment line.
That is the check I just put in if an array has only 3 elements.

Thanks

Leon