1756. Exactly K Apart Picks
A gardener stands beside a row of flower beds, each with a score given by nums (scores can be negative when a bed is full of weeds). The gardener must choose exactly k beds to plant in, and no two chosen beds may be neighbours, meaning their indices must not differ by exactly 1. Return the largest possible sum of the scores of the chosen beds as a long. Because k never exceeds (n + 1) / 2, a valid choice always exists. A table over positions and picks is too slow for large inputs; the intended solution uses a heap and a linked list and runs in O((n + k) log n) time with O(n) space. Here n is at most 10^5.
Example 1
- Input:
- nums = [4,1,9,2,6], k = 2
- Output:
- 15
- Explanation:
The best two non-adjacent picks are 9 (index 2) and 6 (index 4), giving 15.
Example 2
- Input:
- nums = [5,-3,5,-3,5], k = 3
- Output:
- 15
- Explanation:
Exactly three picks force indices 0, 2 and 4, so the sum is 15.
Constraints
1 ≤ n = nums.length ≤ 105; 1 ≤ k ≤ (n + 1) / 2 (integer division); -109 ≤ nums[i] ≤ 109.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 5,200 msC++ 1,300 msJava 2,600 msJavaScript 2,600 msTypeScript 2,600 ms
Expected complexity
- Time
- O((n + k) log n)
- Space
- O(n)