LeetCode 3892 - Minimum Operations to Achieve At Least K Peaks
We are given a circular array nums. An index is considered a peak if its value is strictly greater than both of its neighbors. Because the array is circular, the first and last elements are adjacent. For example, the neighbors of index 0 are nums[n - 1] and nums[1].
Difficulty: 🔴 Hard
Topics: Array, Dynamic Programming
Solution
LeetCode 3892 - Minimum Operations to Achieve At Least K Peaks
Problem Understanding
We are given a circular array nums. An index is considered a peak if its value is strictly greater than both of its neighbors.
Because the array is circular, the first and last elements are adjacent. For example, the neighbors of index 0 are nums[n - 1] and nums[1].
The only operation we are allowed to perform is increasing any element by 1. We may perform this operation as many times as we want, and every increment costs one operation.
The goal is to make the array contain at least k peaks while minimizing the total number of increments performed.
A key observation is that we are never allowed to decrease values. Therefore, when we want a particular index to become a peak, the only way to achieve it is by increasing that index itself until it becomes strictly larger than both neighbors.
The constraints are:
2 <= n <= 5000-10^5 <= nums[i] <= 10^50 <= k <= n
Since n can be as large as 5000, exponential or quadratic-in-subset solutions are impossible. We need a dynamic programming solution that runs in roughly O(nk) time.
Several edge cases immediately stand out:
k = 0, the answer is always0.- In a cycle, two adjacent indices can never both be peaks.
- Therefore the maximum possible number of peaks is
floor(n / 2). - If
k > floor(n / 2), the answer is-1. - The special case
n = 2behaves differently because each index has the other index as both neighbors.
Approaches
Brute Force
A brute force solution would try every subset of indices that could become peaks.
For each subset, we would verify whether the chosen indices are pairwise non-adjacent and compute the cost required to make every chosen index a peak.
The cost for index i is easy to compute:
cost[i] =
max(0, max(leftNeighbor, rightNeighbor) + 1 - nums[i])
However, there are 2^n possible subsets. Even for moderate values of n, this becomes completely infeasible.
Key Insight
The crucial observation is that the cost of making an index a peak is completely independent of other non-adjacent chosen peaks.
For index i, define:
cost[i] =
max(0, max(nums[left], nums[right]) + 1 - nums[i])
If we pay exactly cost[i], then index i becomes a peak.
Now consider two adjacent indices. They cannot both be peaks because each would need to be strictly greater than the other.
Therefore, the problem becomes:
Select at least
kvertices of the cycle such that no two selected vertices are adjacent, and the sum of their costs is minimized.
This is a minimum-cost independent set problem on a cycle with an exact cardinality requirement.
A cycle can be handled using the standard technique:
- Case 1: first vertex is not selected.
- Case 2: first vertex is selected.
Each case reduces to a path DP.
Approach Comparison
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(2^n) | O(n) | Enumerates every possible peak set |
| Optimal | O(nk) | O(k) | Dynamic programming on a cycle |
Algorithm Walkthrough
- Handle trivial cases.
If k == 0, return 0.
If n == 2, only one peak can exist, so solve that case directly.
2. Compute the cost of turning every index into a peak.
For each index i:
cost[i] =
max(0, max(nums[left], nums[right]) + 1 - nums[i])
This is the minimum number of increments required to make i strictly larger than both neighbors.
3. Compute the maximum possible number of peaks.
In a cycle, adjacent indices cannot both be peaks.
Therefore:
maxPeaks = floor(n / 2)
If k > maxPeaks, return -1.
4. Solve a path version of the problem.
For a path, maintain two DP arrays:
dp0[j]= minimum cost after processing current position, where the current position is not selected.dp1[j]= minimum cost after processing current position, where the current position is selected.
The count j represents how many peaks have been chosen.
5. Solve cycle case A, first index not selected.
Since index 0 is excluded, the remaining indices form a path:
1 ... n-1
Run the path DP and obtain the minimum cost for every possible number of selected peaks. 6. Solve cycle case B, first index selected.
Pay cost[0].
Then indices 1 and n-1 cannot be selected.
The remaining valid path becomes:
2 ... n-2
Run the path DP on this path and add one selected peak for index 0.
7. Combine both cases.
For every achievable peak count:
answer[count] =
min(caseA[count], caseB[count])
- Return the minimum value among all counts greater than or equal to
k.
Why it works
For every index, cost[i] is exactly the minimum amount required to make that index a peak. Since only increases are allowed, no cheaper solution exists.
Any valid set of peaks must be an independent set of the cycle because adjacent peaks are impossible. Conversely, every independent set can be realized by paying the corresponding peak costs.
The DP enumerates all independent sets of every possible size while tracking minimum total cost. Splitting the cycle into the two standard cases, first vertex selected or not selected, guarantees that every valid cycle independent set is considered exactly once. Therefore the minimum cost returned by the algorithm is optimal.
Python Solution
from typing import List
class Solution:
def minOperations(self, nums: List[int], k: int) -> int:
n = len(nums)
if k == 0:
return 0
if n == 2:
if k > 1:
return -1
c0 = max(0, nums[1] + 1 - nums[0])
c1 = max(0, nums[0] + 1 - nums[1])
return min(c0, c1)
max_peaks = n // 2
if k > max_peaks:
return -1
costs = [0] * n
for i in range(n):
left = nums[(i - 1) % n]
right = nums[(i + 1) % n]
costs[i] = max(0, max(left, right) + 1 - nums[i])
INF = 10**18
def path_dp(arr: List[int]):
length = len(arr)
dp0 = [INF] * (max_peaks + 1)
dp1 = [INF] * (max_peaks + 1)
dp0[0] = 0
for w in arr:
ndp0 = [INF] * (max_peaks + 1)
ndp1 = [INF] * (max_peaks + 1)
for cnt in range(max_peaks + 1):
best_prev = min(dp0[cnt], dp1[cnt])
if best_prev < ndp0[cnt]:
ndp0[cnt] = best_prev
if cnt > 0 and dp0[cnt - 1] != INF:
ndp1[cnt] = dp0[cnt - 1] + w
dp0, dp1 = ndp0, ndp1
result = [INF] * (max_peaks + 1)
for cnt in range(max_peaks + 1):
result[cnt] = min(dp0[cnt], dp1[cnt])
return result
case_a = path_dp(costs[1:])
middle = costs[2:n - 1]
case_b_middle = path_dp(middle)
case_b = [INF] * (max_peaks + 1)
for cnt in range(max_peaks):
if case_b_middle[cnt] != INF:
case_b[cnt + 1] = costs[0] + case_b_middle[cnt]
answer = INF
for cnt in range(k, max_peaks + 1):
answer = min(answer, case_a[cnt], case_b[cnt])
return answer
The implementation first converts the original problem into a weighted independent-set problem by computing the cost of making each index a peak.
The helper function path_dp solves the path version. It uses two states to track whether the most recently processed position is selected or not selected. This prevents adjacent selections.
The cycle is then broken into two cases. In the first case, index 0 is excluded. In the second case, index 0 is forced into the solution, which automatically forbids indices 1 and n - 1.
Finally, the minimum cost among all peak counts greater than or equal to k is returned.
Go Solution
package main
func minOperations(nums []int, k int) int {
n := len(nums)
if k == 0 {
return 0
}
if n == 2 {
if k > 1 {
return -1
}
c0 := max(0, nums[1]+1-nums[0])
c1 := max(0, nums[0]+1-nums[1])
if c0 < c1 {
return c0
}
return c1
}
maxPeaks := n / 2
if k > maxPeaks {
return -1
}
costs := make([]int, n)
for i := 0; i < n; i++ {
left := nums[(i-1+n)%n]
right := nums[(i+1)%n]
need := max(left, right) + 1 - nums[i]
if need < 0 {
need = 0
}
costs[i] = need
}
const INF int64 = 1 << 60
pathDP := func(arr []int) []int64 {
dp0 := make([]int64, maxPeaks+1)
dp1 := make([]int64, maxPeaks+1)
for i := 0; i <= maxPeaks; i++ {
dp0[i] = INF
dp1[i] = INF
}
dp0[0] = 0
for _, w := range arr {
ndp0 := make([]int64, maxPeaks+1)
ndp1 := make([]int64, maxPeaks+1)
for i := 0; i <= maxPeaks; i++ {
ndp0[i] = INF
ndp1[i] = INF
}
for cnt := 0; cnt <= maxPeaks; cnt++ {
bestPrev := dp0[cnt]
if dp1[cnt] < bestPrev {
bestPrev = dp1[cnt]
}
if bestPrev < ndp0[cnt] {
ndp0[cnt] = bestPrev
}
if cnt > 0 && dp0[cnt-1] != INF {
ndp1[cnt] = dp0[cnt-1] + int64(w)
}
}
dp0 = ndp0
dp1 = ndp1
}
res := make([]int64, maxPeaks+1)
for cnt := 0; cnt <= maxPeaks; cnt++ {
if dp0[cnt] < dp1[cnt] {
res[cnt] = dp0[cnt]
} else {
res[cnt] = dp1[cnt]
}
}
return res
}
caseA := pathDP(costs[1:])
middle := costs[2 : n-1]
caseBMiddle := pathDP(middle)
caseB := make([]int64, maxPeaks+1)
for i := 0; i <= maxPeaks; i++ {
caseB[i] = INF
}
for cnt := 0; cnt < maxPeaks; cnt++ {
if caseBMiddle[cnt] != INF {
caseB[cnt+1] = int64(costs[0]) + caseBMiddle[cnt]
}
}
ans := INF
for cnt := k; cnt <= maxPeaks; cnt++ {
if caseA[cnt] < ans {
ans = caseA[cnt]
}
if caseB[cnt] < ans {
ans = caseB[cnt]
}
}
return int(ans)
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
The Go implementation mirrors the Python solution exactly. The only notable difference is the use of int64 inside the dynamic programming arrays to safely handle accumulated costs. Slices are used for rolling DP storage, keeping memory usage at O(k).
Worked Examples
Example 1
Input:
nums = [2,1,2]
k = 1
Peak costs:
| Index | Neighbors | Cost |
|---|---|---|
| 0 | 2,1 | 1 |
| 1 | 2,2 | 2 |
| 2 | 1,2 | 1 |
So:
costs = [1,2,1]
Maximum peaks:
floor(3/2) = 1
Case A, exclude index 0:
Path = [2,1]
Best cost for selecting one peak:
1
Case B, include index 0:
Cost = 1
No other indices may be selected.
Result:
min(1,1) = 1
Answer:
1
Example 2
Input:
nums = [4,5,3,6]
k = 2
Peak costs:
| Index | Cost |
|---|---|
| 0 | 3 |
| 1 | 0 |
| 2 | 4 |
| 3 | 0 |
Indices 1 and 3 are already peaks.
Selecting both yields:
0 + 0 = 0
Two non-adjacent peaks are obtained immediately.
Answer:
0
Example 3
Input:
nums = [3,7,3]
k = 2
Maximum possible peaks:
floor(3/2) = 1
Since:
k = 2 > 1
it is impossible.
Answer:
-1
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(nk) | Two path DPs, each processing up to n positions and k <= n/2 counts |
| Space | O(k) | Rolling DP arrays store only the current layer |
The dynamic programming maintains only two count arrays at any time, so memory remains linear in the number of achievable peaks. Each position updates every possible count once, producing O(nk) total work.
Test Cases
s = Solution()
assert s.minOperations([2, 1, 2], 1) == 1 # example 1
assert s.minOperations([4, 5, 3, 6], 2) == 0 # example 2
assert s.minOperations([3, 7, 3], 2) == -1 # example 3
assert s.minOperations([1, 1], 0) == 0 # k = 0
assert s.minOperations([1, 1], 1) == 1 # n = 2
assert s.minOperations([5, 1], 1) == 0 # already one peak
assert s.minOperations([1, 1, 1], 1) == 1 # single peak needed
assert s.minOperations([1, 1, 1], 2) == -1 # exceeds floor(n/2)
assert s.minOperations([10, 1, 10, 1], 2) == 0 # already two peaks
assert s.minOperations([1, 1, 1, 1], 2) == 2 # two peaks must be created
assert s.minOperations([5, 5, 5, 5, 5], 2) == 2 # uniform cycle
assert s.minOperations([100, -100, 100, -100], 2) == 0 # large value gap
assert s.minOperations([3, 3, 3, 3, 3, 3], 3) == 3 # maximum possible peaks
Test Summary
| Test | Why |
|---|---|
[2,1,2], k=1 |
Official example |
[4,5,3,6], k=2 |
Already satisfies requirement |
[3,7,3], k=2 |
Impossible because of peak limit |
k=0 |
Trivial answer case |
n=2 |
Special circular edge case |
| Uniform arrays | Requires creating peaks from scratch |
| Already alternating highs and lows | Verifies zero-cost solutions |
| Maximum peak count | Tests cardinality boundary |
| Negative values | Ensures cost formula handles all ranges |
Edge Cases
Maximum Number of Peaks Exceeded
In a cycle, adjacent vertices cannot both be peaks. Therefore the largest possible number of peaks is floor(n / 2). A common bug is attempting to run the DP even when k exceeds this limit. The implementation checks this immediately and returns -1.
Two-Element Circular Array
When n = 2, each element has the other element as both neighbors. This does not behave like a normal cycle of length at least three. The implementation handles this case separately and computes the answer directly.
Already Existing Peaks
Some indices may already be peaks. Their required cost is zero. A solution that always assumes every chosen peak requires at least one operation would overcount. The formula
max(0, max(neighbors) + 1 - nums[i])
correctly produces zero cost whenever an index is already a peak.
Multiple Optimal Peak Counts
The problem asks for at least k peaks, not exactly k. Sometimes creating additional peaks costs nothing because some indices are already peaks. The implementation therefore computes the minimum cost for every achievable peak count and returns the minimum among all counts greater than or equal to k.