Given a one dimensional array of integers representing the height of cliffs of a valley, find the total amount of water that can be filled in the valley.
Diagram:
Java Program:
package com.sourabh.test;
import java.util.ArrayList;
import java.util.List;
public class ValleyWater {
class Valley
{
private int start;
private int end;
private int water;
public Valley() {
super();
}
public Valley(int start, int end) {
super();
this.start = start;
this.end = end;
}
public int getStart() {
return start;
}
public void setStart(int start) {
this.start = start;
}
public int getEnd() {
return end;
}
public void setEnd(int end) {
this.end = end;
}
public int getWater() {
return water;
}
public void setWater(int water) {
this.water = water;
}
}
public List<Valley> getValleys(int... A) {
List<Integer> maxima = new ArrayList<>();
List<Integer> minima = new ArrayList<>();
List<Valley> valleysList = new ArrayList<>();
int index = 0;
for(int i=0;i<A.length - 1;i++) {
if(A[i+1] > A[i]) {
minima.add(i);
index = i;
break;
}
if(A[i+1] < A[i]) {
maxima.add(i);
index = i;
break;
}
}
for(int i=index+1;i+1<A.length;i++) {
if(A[i+1] < A[i] && A[i] >= A[i-1]) {
maxima.add(i);
}
if(A[i+1] > A[i] && A[i] <= A[i-1]) {
minima.add(i);
}
}
for(int i = 0; i < maxima.size() - 1; i++) {
valleysList.add(new Valley(maxima.get(i), maxima.get(i+1)));
}
return valleysList;
}
public int addWater(List<Valley> valleysList, int... A) {
int totalWater = 0;
for(Valley valley : valleysList) {
int min = A[valley.getStart()] < A[valley.getEnd()] ? A[valley.getStart()] : A[valley.getEnd()];
int water = 0;
for(int i=valley.getStart(); i<=valley.getEnd(); i++) {
if(A[i] < min) {
water += min - A[i];
}
}
valley.setWater(water);
totalWater += water;
}
for(Valley valley : valleysList) {
System.out.println(valley.getWater());
}
return totalWater;
}
public int getWater(int... A) {
return addWater(getValleys(A), A);
}
}
Unit Tests:
package com.sourabh.test;
import static org.junit.Assert.*;
import java.util.List;
import com.sourabh.test.ValleyWater.Valley;
import org.junit.Assert;
import org.junit.Test;
public class ValleyWaterTests {
ValleyWater instance = new ValleyWater();
@Test
public void getValleysTest() {
int[] A = {1,2,3,1,2,1,4,6,5,4,2,3,4,1};
List<Valley> valleysList = instance.getValleys(A);
Assert.assertEquals(3, valleysList.size());
Assert.assertEquals(2,valleysList.get(0).getStart());
Assert.assertEquals(4,valleysList.get(0).getEnd());
Assert.assertEquals(4,valleysList.get(1).getStart());
Assert.assertEquals(7,valleysList.get(1).getEnd());
Assert.assertEquals(7,valleysList.get(2).getStart());
Assert.assertEquals(12,valleysList.get(2).getEnd());
}
@Test
public void getWaterTest() {
int[] A = {1,2,3,1,2,1,4,6,5,4,2,3,4,1};
int totalWater = instance.getWater(A);
Assert.assertEquals(5, totalWater);
}
}

thank u for sharing this post Meraki Firewall
ReplyDeleteMeraki Cloud