## fizzbuzzer.com

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

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

Sample Output

Explanation

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