# Mud Walls

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

1 2 3 4 5 6 7 8 9 10 11 12 |
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[0],…stickPositions[n-1]]: an array of integers

stickHeights[stickHeights[0],…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**

1 2 3 4 5 6 7 8 9 |
3 1 3 7 3 4 3 3 |

**Sample Output**

1 2 |
5 |

**Explanation**

1 2 3 4 5 6 |
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**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 |
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)); } } |