FastPrepMaximum Separation of Two Frogs on Adjacent Blocks

Maximum Separation of Two Frogs on Adjacent Blocks

Marshall Wace logoMarshall Wace● MediumFULLTIMEOA

Problem statement

A row has N blocks with heights blocks[0] through blocks[N - 1]. Two frogs start together on one block that you may choose.

A frog may jump to an adjacent block only if the new block is at least as high as the current block. Either frog may stay still, and each may make any number of allowed jumps.

If the final positions are J <= K, their distance is defined as K - J + 1, the number of blocks in that inclusive range. Choose the best shared starting block and return the greatest possible distance.

Function

solution(blocks: int[]) → int

Examples

Example 1

blocks = [2,6,8,5]return = 3

Start both frogs at index 0. One stays; the other reaches index 2 but cannot descend to index 3. The inclusive distance is 3.

Example 2

blocks = [1,5,5,2,6]return = 4

Start at index 3. One frog reaches index 1 through the equal-height blocks at indices 2 and 1; the other reaches index 4. The distance is 4 - 1 + 1 = 4.

Example 3

blocks = [1,1]return = 2

Start at either block. One frog stays and the other jumps to its equal-height neighbour.

Constraints

  • 2 <= blocks.length <= 200000.
  • 1 <= blocks[i] <= 10^9.

More Marshall Wace problems

See Marshall Wace hiring insights
Saved
public int solution(int[] blocks) {
    // Write your solution here.
}
blocks[2,6,8,5]
expected3
Checking account…