Collect Branches for a Bird Nest
Learn this problem
VisaNEW GRADOAProblem statement
You are given an integer array forest and a positive integer n, the bird's zero-based starting index. A positive value forest[i] is the length of the branch at index i; 0 means that no branch is there.
The bird builds a nest at its starting position. The nest begins with total branch length 0. The starting cell is never searched or collected, even if forest[n] is positive.
Follow these rules until the collected length is at least 100:
- Search to the right first, then alternate left and right searches. Every search begins from the same original index
n. - In the chosen direction, collect the nearest remaining positive-length branch. Remove that entire branch, add its length to the nest, and return to index
n. A branch can be collected only once. - If no branch remains in the chosen direction, skip that search and switch to the other direction.
- Stop immediately after a pickup makes the total length at least
100; do not make another search.
The sum of all branch lengths outside index n is at least 100, so the nest can always be completed. Return the zero-based indices of the collected branches, in pickup order.
Function
collectBranches(forest: int[], n: int) → int[]Examples
Example 1
forest = [0,45,0,0,30,0,40]n = 3return = [4,1,6]From index 3, the right search collects index 4 for a total of 30. The left search collects index 1, raising the total to 75. The next right search collects index 6, bringing the total to 115, so the bird stops.
Example 2
forest = [20,30,50,80]n = 3return = [2,1,0]Index 3 is the starting cell, so its branch is excluded. Every right search is skipped because there are no cells to the right. The successive left pickups are indices 2, 1, and 0, with totals 50, 80, and 100.
Constraints
2 <= forest.length <= 10^5.0 <= forest[i] <= 100.1 <= n < forest.length.- The sum of
forest[i]over alli != nis at least100.