Collect Sticks for a Bird's Nest
Duolingo● MediumNEW GRADOAProblem statement
You are helping a bird build its nest. You are given an integer array forest containing positive integers and zeros, and an index bird representing the bird's initial position.
Each positive value forest[i] is a stick whose length equals that value. Each zero is an empty position. The starting position is guaranteed to be empty.
The bird follows this process:
- Fly to the right until reaching the first remaining stick, take that stick, and return to
bird. - Fly to the left until reaching the first remaining stick, take that stick, and return to
bird. - Continue alternating right and left until the total length of collected sticks is at least
100.
Return the original zero-based indices of the collected sticks in the order in which the bird finds them.
Function
collectNestSticks(forest: int[], bird: int) → int[]Examples
Example 1
forest = [25,0,50,0,0,0,0,15,0,0,45]bird = 4return = [7,2,10]The first stick to the right is at index 7 with length 15. The first stick to the left is at index 2 with length 50. Moving right again finds index 10 with length 45. The collected total is 110, so the process stops.
Constraints
forest[bird] = 0.- Every value in
forestis a non-negative integer; every positive value is a stick length. - The sum of all stick lengths is at least
100. - Before the collected total reaches
100, the next required direction always contains a remaining stick. - A solution with time complexity no worse than
O(forest.length^2)fits the source's execution limit.