Skip to main content
Talentd

Minimum Operations to Achieve At Least K Peaks - Solution & Explanation

HardArrayDynamic Programming4 min read
Practice this problem

Problem Statement

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:

  • The previous neighbor of i is nums[i - 1] if i > 0, otherwise nums[n - 1].
  • The next neighbor of i is nums[i + 1] if i < n - 1, otherwise nums[0].

You are allowed to perform the following operation any number of times:

  • Choose any index 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:

  • To achieve at least k = 1 peak, we can increase nums[2] = 2 to 3.
  • After this operation, nums[2] = 3 is strictly greater than its neighbors nums[0] = 2 and nums[1] = 1.
  • Therefore, the minimum number of operations required is 1.

Example 2:

Input: nums = [4,5,3,6], k = 2

Output: 0

Explanation:

  • The array already contains at least k = 2 peaks with zero operations.
  • Index 1: nums[1] = 5 is strictly greater than its neighbors nums[0] = 4 and nums[2] = 3.
  • Index 3: nums[3] = 6 is strictly greater than its neighbors nums[2] = 3 and nums[0] = 4.
  • Therefore, the minimum number of operations required is 0.

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] <= 105
  • 0 <= k <= n​​​​​​​

Approach Overview

Problem 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

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Peak SelectionO(2^n)O(1)Conceptual understanding of peak constraints or very small arrays
Dynamic Programming with Peak PlacementO(n*k)O(n*k)General solution for large arrays where peak positions must be optimized
Space Optimized DPO(n*k)O(k)Memory constrained environments or production implementations

Video Solution

Super Hard DP DSA Question - LeetCode Weekly Contest 496 - Q4 - (3892) Explained By Kumar K sir • Kumar K [Amazon] • 615 views views

Watch 4 more video solutions →

Frequently Asked Questions

Is Minimum Operations to Achieve At Least K Peaks easy or hard?
The problem is classified as Hard because it requires modeling peak placement as a constrained optimization problem. You must combine cost calculation with dynamic programming while enforcing the non-adjacent peak rule. Designing the correct DP state and transitions is the main challenge.
Minimum Operations to Achieve At Least K Peaks Python/Java solution
Most implementations compute the peak adjustment cost for each index, then apply dynamic programming to track the minimum cost for building up to k peaks. Python typically uses lists for DP arrays, while Java implementations rely on 2D arrays or rolling buffers. Both follow the same O(n*k) time logic.
How to solve Minimum Operations to Achieve At Least K Peaks in O(n*k)?
Compute the cost of converting each index into a peak by ensuring it is greater than its neighbors. Use a DP state dp[i][j] representing the minimum cost to process the first i elements with j peaks. When selecting index i as a peak, transition from i-2 to avoid adjacent peaks. Iterating through the array while updating these states produces an O(n*k) solution.
What is the best approach for Minimum Operations to Achieve At Least K Peaks?
The most effective method uses dynamic programming. Track the minimum cost to form j peaks while scanning the array and ensure peaks are never adjacent. Each potential peak requires computing the cost to make nums[i] greater than both neighbors. This solution runs in O(n*k) time and can be optimized to O(k) space.
Is Minimum Operations to Achieve At Least K Peaks asked at Google/Amazon/Meta?
Dynamic programming problems involving peaks, local maxima, and array modification costs frequently appear in interviews at companies like Google, Amazon, and Meta. Variants often require selecting positions under adjacency constraints or minimizing modification cost. This problem tests DP state design and careful transition logic.
What data structure is used in Minimum Operations to Achieve At Least K Peaks?
The core structure is a dynamic programming table or rolling array storing the minimum cost for each number of peaks. The algorithm also relies on simple array traversal and constant-time neighbor comparisons. No complex structures like heaps or trees are required.
What is the time complexity of Minimum Operations to Achieve At Least K Peaks?
The optimal dynamic programming solution runs in O(n*k) time, where n is the array length and k is the required number of peaks. Each position evaluates whether to form a peak or skip it while updating DP states. Space complexity ranges from O(n*k) for a full table to O(k) with rolling arrays.

Ready to solve this problem?

Practice Minimum Operations to Achieve At Least K Peaks with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays