FastPrep
Problem · Array

Flowerbed Capacity Queries

Learn this problem
● MediumLinkedIn logoLinkedInFULLTIMEPHONE SCREEN

Problem statement

You are given a binary array flowerbed, where 1 means a plot already contains a flower and 0 means it is empty. The initial flowerbed is valid: no two occupied plots are adjacent.

You are also given an integer array queries. For each queries[i], determine whether at least that many additional flowers can be planted without placing flowers in adjacent plots.

Every query is independent. Evaluate each query against the same unchanged initial flowerbed; flowers considered for one query do not remain planted for another query.

Return a boolean array answer where answer[i] is true exactly when queries[i] additional flowers can be planted. Preprocess the flowerbed once so that each query is answered in O(1) time.

Function

flowerbedCapacityQueries(flowerbed: int[], queries: int[]) → boolean[]

Examples

Example 1

flowerbed = [1,0,0,0,1]queries = [0,1,2]return = [true,true,false]

The flowerbed has capacity for exactly 1 additional flower, at index 2. Therefore requests for 0 and 1 flowers succeed, while the request for 2 flowers fails.

Example 2

flowerbed = [0,0,0,0,0]queries = [1,3,4]return = [true,true,false]

Flowers can be placed at indices 0, 2, and 4, so the maximum additional capacity is 3.

Example 3

flowerbed = [0]queries = [0,1,2]return = [true,true,false]

The only plot can hold one flower. The independent queries compare 0, 1, and 2 with that capacity.

Constraints

  • 1 <= flowerbed.length <= 2 * 10^4
  • flowerbed[i] is either 0 or 1.
  • The initial flowerbed contains no adjacent occupied plots.
  • 1 <= queries.length <= 2 * 10^4
  • 0 <= queries[i] <= flowerbed.length
  • Queries are independent and do not mutate flowerbed.

More LinkedIn problems

drafts saved locally
public boolean[] flowerbedCapacityQueries(int[] flowerbed, int[] queries) {
    // write your code here
}
flowerbed[1,0,0,0,1]
queries[0,1,2]
expected[true,true,false]
checking account