## [f]izzbuzzer

### Looking for good programming challenges?

Use the search below to find our solutions for selected questions!

# Mud Walls

Sharing is caring!

Problem Statement
A child likes to build mud walls by placing mud between sticks positioned on a number line. The gap between sticks will be referred to as a cell, and each cell will contain one segment of wall. The height of mud in a segment cannot exceed 1 unit above an adjacent stick or mud segment. Given the placement of a number of sticks and their heights, determine the maximum height segment of mud that can be built. If no mud segment can be built, return 0.

For example, there are n = 3 sticks at stickPositions = [1, 2, 4, 7] with stickHeights = [4, 5, 7, 11]. There is no space between the first two sticks, so there is no cell for mud. Between positions 2 and 4, there is one cell. Heights of the surrounding sticks are 5 and 7, so the maximum height of mud is 5 + 1 = 6. Between positions 4 and 7 there are two cells. The heights of surrounding sticks are 7 and 11. The maximum height mud segment next to the stick of height 7 is 8. The maximum height mud next to a mud segment of height 8 and a stick of height 11 is 9. Mud segment heights are 6, 8 and 9, and the maximum height is 9. In the table below, digits are in the columns of sticks and M is in the mud segments.

``````      7
7
M7
MM7
4MM7
M4MM7
2M4MM7
12M4MM7
12M4MM7
12M4MM7
12M4MM7
``````

Function Description
Complete the function maxHeight in the editor below. The function must return an integer, the maximum height mud segment that can be built.

`maxHeight` has the following parameter(s):
stickPositions[stickPositions,…stickPositions[n-1]]: an array of integers
stickHeights[stickHeights,…stickHeights[n-1]]: an array of integers

Constraints
1 ≤ n ≤ 105
1 ≤ stickPositions[i] ≤ 109 (where 0 ≤ i < n)
1 ≤ stickHeights[i] ≤ 109 (where 0 ≤ i < n)

Sample Input For Custom Testing

``````3
1
3
7
3
4
3
3
``````

Sample Output

``````5
``````

Explanation

``````    M
1M MMM
1M3MMM7
1M3MMM7
1M3MMM7
``````

Here stickPositions = [1, 3, 7] and stickHeights = [4, 3, 3]. There can be a segment of height 4 at position 2 supported by sticks of heights 4 and 3. Between positions 3 and 7, there can be a segment of height 4 at positions 4 and 6. Between them, a segment can be built of height 5 at position 5.

Solution

```public class MudWalls {

public static int maxHeight(int[] stickPositions, int[] stickHeights) {
int n = stickPositions.length;
int m = stickHeights.length;
int max = 0;

for (int i=0; i<n-1; i++) {
if (stickPositions[i]<stickPositions[i+1]-1) {
// We have a gap
int heightDiff =  Math.abs(stickHeights[i+1] - stickHeights[i]);
int gapLen = stickPositions[i+1] - stickPositions[i] - 1;
int localMax = 0;
if (gapLen > heightDiff) {
int low = Math.max(stickHeights[i+1], stickHeights[i]) + 1;
int remainingGap = gapLen - heightDiff - 1;
localMax = low + remainingGap/2;

} else {
localMax = Math.min(stickHeights[i+1], stickHeights[i]) + gapLen;
}

max = Math.max(max, localMax);
}
}

return max;
}

public static void main(String[] args) throws FileNotFoundException {
System.setIn(new FileInputStream(System.getProperty("user.home") + "/" + "in9.txt"));
//Scanner outputScanner = new Scanner(new FileInputStream(System.getProperty("user.home") + "/" + "out.txt"));

Scanner scanner = new Scanner(System.in);

int n = scanner.nextInt();
int[] stickPositions = new int[n];
for (int i = 0; i < n; i++) {
stickPositions[i] = scanner.nextInt();
}
n = scanner.nextInt();
int[] stickHeights = new int[n];
for (int i = 0; i < n; i++) {
stickHeights[i] = scanner.nextInt();
}

System.out.println(maxHeight(stickPositions, stickHeights));
}
}```