You are given a circular integer array nums of length n.
An index i is a peak if its value is strictly greater than its neighbors:
i is nums[i - 1] if i > 0, otherwise nums[n - 1].i is nums[i + 1] if i < n - 1, otherwise nums[0].You are allowed to perform the following operation any number of times:
i and increase nums[i] by 1.Return an integer denoting the minimum number of operations required to make the array contain at least k peaks. If it is impossible, return -1.
Example 1:
Input: nums = [2,1,2], k = 1
Output: 1
Explanation:
k = 1 peak, we can increase nums[2] = 2 to 3.nums[2] = 3 is strictly greater than its neighbors nums[0] = 2 and nums[1] = 1.Example 2:
Input: nums = [4,5,3,6], k = 2
Output: 0
Explanation:
k = 2 peaks with zero operations.nums[1] = 5 is strictly greater than its neighbors nums[0] = 4 and nums[2] = 3.nums[3] = 6 is strictly greater than its neighbors nums[2] = 3 and nums[0] = 4.Example 3:
Input: nums = [3,7,3], k = 2
Output: -1
Explanation:
It is impossible to have at least k = 2 peaks in this array. Therefore, the answer is -1.
Constraints:
2 <= n == nums.length <= 5000-105 <= nums[i] <= 1050 <= k <= nProblem Overview: You receive an array and must perform operations so that the array contains at least k peaks. An index i is a peak when nums[i] > nums[i-1] and nums[i] > nums[i+1]. Each operation modifies array values, and the goal is to achieve at least k valid peaks with the minimum total cost.
Approach 1: Brute Force Peak Selection (Exponential)
Enumerate all subsets of indices that could serve as peaks. For every candidate set of size k, verify the non‑adjacency constraint and compute the cost required to raise each chosen index above its neighbors. The cost for index i is max(0, max(nums[i-1], nums[i+1]) - nums[i] + 1). Track the minimum cost among all valid selections. This approach demonstrates the peak condition clearly but runs in O(2^n) time with O(1) extra space, which becomes infeasible once n grows.
Approach 2: Dynamic Programming with Peak Placement (O(n*k))
Model the problem as choosing positions for peaks while avoiding adjacent placements. Define dp[i][j] as the minimum cost to process the first i elements and create j peaks where the i-th index is considered as a candidate. At each index you either skip it or turn it into a peak. When selecting i as a peak, compute the adjustment cost needed to make nums[i] greater than both neighbors. Because peaks cannot be adjacent, the transition comes from i-2. This structured choice turns the combinatorial search into a predictable table fill using dynamic programming. Time complexity is O(n*k) and space complexity is O(n*k).
Approach 3: Space-Optimized DP (O(n*k) time, O(k) space)
The DP only depends on earlier rows (i-1 and i-2). Compress the table into rolling arrays that track the minimum cost for each peak count. Precompute the cost of turning each index into a peak, then update states while iterating through the array. This reduces memory usage while preserving the same recurrence. The logic still relies on careful index transitions typical in array and dynamic programming problems. Time complexity remains O(n*k) with O(k) space.
Recommended for interviews: The dynamic programming formulation is what interviewers usually expect. Starting with the brute force explanation shows you understand the peak constraints and cost calculation. Transitioning to the O(n*k) DP demonstrates the key insight: peak positions cannot be adjacent, so each decision only depends on earlier valid states.
Solutions for this problem are being prepared.
Try solving it yourself| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Peak Selection | O(2^n) | O(1) | Conceptual understanding of peak constraints or very small arrays |
| Dynamic Programming with Peak Placement | O(n*k) | O(n*k) | General solution for large arrays where peak positions must be optimized |
| Space Optimized DP | O(n*k) | O(k) | Memory constrained environments or production implementations |
Practice Minimum Operations to Achieve At Least K Peaks with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor