FastPrep
Problem · Array

Fountain Safety

Learn this problem
● MediumGoogle logoGoogleONSITE INTERVIEW
See Google hiring insights

Problem statement

Imagine fountains pumping water only if they are above the surface. You are given an integer array terrain of length N, where terrain[i] is the height at position i. You are also given an integer array fountains of length K, where each value is the position of a fountain. The fountain positions are sorted in ascending order.

For each fountain, water may flow to the left and to the right across consecutive positions whose terrain height is strictly lower than that fountain's height. The water stops before any position whose height is greater than or equal to the fountain's height, and it cannot pass through that position.

Return a bit mask of length N as an integer array. Set answer[i] = 1 if position i is watered by at least one fountain, and answer[i] = 0 otherwise. The fountain's own position is not marked by that fountain.

Function

getWateredPositions(terrain: int[], fountains: int[]) → int[]

Examples

Example 1

terrain = [2, 1, 3, 2, 1, 1]fountains = [0, 3]return = [0, 1, 0, 0, 1, 1]

Fountain 0 has height 2. It waters position 1 to its right because terrain[1] = 1, then stops before position 2 because terrain[2] = 3. There is nothing to its left. Fountain 3 has height 2. It waters positions 4 and 5. Therefore the watered positions are 1, 4, and 5.

Example 2

terrain = [1, 2, 1]fountains = [1]return = [1, 0, 1]

The fountain at position 1 has height 2, so it waters both neighboring positions of height 1. The fountain's own position remains 0.

Example 3

terrain = [3, 1, 3, 1, 2]fountains = [0, 2]return = [0, 1, 0, 1, 1]

Fountain 0 waters position 1 and stops before the equal-height position 2. Fountain 2 waters position 1 to the left and positions 3 and 4 to the right.

Constraints

  • 1 <= terrain.length <= 10^5
  • 0 <= fountains.length <= terrain.length
  • -10^9 <= terrain[i] <= 10^9
  • Every fountain position is in [0, terrain.length - 1], and fountains is strictly increasing.

More Google problems

drafts saved locally
public int[] getWateredPositions(int[] terrain, int[] fountains) {
  // write your code here
}
terrain[2, 1, 3, 2, 1, 1]
fountains[0, 3]
expected[0, 1, 0, 0, 1, 1]
checking account