A peak in an array arr is an element that is greater than its previous and next element in arr.
You are given an integer array nums and a 2D integer array queries.
You have to process queries of two types:
queries[i] = [1, li, ri], determine the count of peak elements in the subarray nums[li..ri].queries[i] = [2, indexi, vali], change nums[indexi] to vali.Return an array answer containing the results of the queries of the first type in order.
Notes:
Example 1:
Input: nums = [3,1,4,2,5], queries = [[2,3,4],[1,0,4]]
Output: [0]
Explanation:
First query: We change nums[3] to 4 and nums becomes [3,1,4,4,5].
Second query: The number of peaks in the [3,1,4,4,5] is 0.
Example 2:
Input: nums = [4,1,4,2,1,5], queries = [[2,2,4],[1,0,2],[1,0,4]]
Output: [0,1]
Explanation:
First query: nums[2] should become 4, but it is already set to 4.
Second query: The number of peaks in the [4,1,4] is 0.
Third query: The second 4 is a peak in the [4,1,4,2,1].
Constraints:
3 <= nums.length <= 1051 <= nums[i] <= 1051 <= queries.length <= 105queries[i][0] == 1 or queries[i][0] == 2i that:
queries[i][0] == 1: 0 <= queries[i][1] <= queries[i][2] <= nums.length - 1queries[i][0] == 2: 0 <= queries[i][1] <= nums.length - 1, 1 <= queries[i][2] <= 105Problem Overview: You are given an integer array and multiple queries. A position i is a peak if nums[i] > nums[i-1] and nums[i] > nums[i+1]. Queries either ask for the number of peaks in a subarray or update a value in the array. After updates, peak positions can change, so the structure must support fast range queries and local updates.
Approach 1: Naive Scan (O(n) per query, O(1) space)
For each query asking for the number of peaks in a range [l, r], iterate through indices l+1 to r-1 and check whether each index forms a peak. Updates simply modify the array value directly. This approach uses straightforward iteration over the array and recomputes peaks every time a query is processed. Time complexity becomes O(n * q) in the worst case because each query may scan most of the array.
Approach 2: Precomputation + Binary Indexed Tree (O((n + q) log n) time, O(n) space)
Create a helper array peak[i] where peak[i] = 1 if index i is a peak, otherwise 0. Build a Binary Indexed Tree over this array so you can quickly compute prefix sums. A range query for peaks in [l, r] becomes a sum query over [l+1, r-1]. When an update modifies nums[i], only indices i-1, i, and i+1 can change peak status. Recalculate those positions and update the Fenwick tree accordingly. Each update and query runs in O(log n) time.
Approach 3: Segment Tree (O((n + q) log n) time, O(n) space)
A Segment Tree can also store the number of peaks within each segment. Build the tree using the precomputed peak array. Range queries return the count of peaks in [l+1, r-1]. Updates propagate changes when peak indicators at nearby indices change. This approach provides the same asymptotic complexity as the Fenwick tree but is more flexible if additional range information needs to be stored.
Recommended for interviews: The Binary Indexed Tree solution is typically expected. The brute-force scan demonstrates understanding of the peak definition, but interviewers usually want the optimized solution with O(log n) updates and queries. Recognizing that only three indices can change peak status after an update is the key insight that enables the efficient design.
The naive approach involves iterating through the subarray specified in the query to count the number of peaks. For each type 1 query, check all elements from l to r and determine if each is a peak by checking its neighbors. For type 2 queries, simply update the element and proceed with the next query.
This C solution uses a simple for loop to scan through each query and handle them based on their type. For type 1 queries, it sequentially checks whether the middle elements of the specified range are peaks. For type 2 queries, it updates the array directly. The results from type 1 queries are stored and returned.
Time Complexity: O(Q * (r-l)) where Q is the number of queries and (r-l) is the length of the subarray to check for peaks.
Space Complexity: O(1) for in-place modification of the array.
In this approach, the main idea is to maintain a set or list of current peak indices. We update this list whenever an element changes in a type 2 query. For type 1 queries, we simply count the peaks that fall within the queried range. This requires precomputing the peak indices and adjusting the list dynamically.
This optimized C solution precomputes peaks on initialization using a flag array. Each modification in a type 2 query checks, and when necessary, updates peak status for neighboring indices. This allows quick peak tallying during type 1 queries.
Time Complexity: O(n + Q) due to initial peak precomputation and constant time operations during each query.
Space Complexity: O(n) for storing the peak status flags.
According to the problem description, for 0 < i < n - 1, if it satisfies nums[i - 1] < nums[i] and nums[i] > nums[i + 1], we can consider nums[i] as 1, otherwise as 0. Thus, for operation 1, i.e., querying the number of peak elements in the subarray nums[l..r], it is equivalent to querying the number of 1s in the interval [l + 1, r - 1]. We can use a binary indexed tree to maintain the number of 1s in the interval [1, n - 1].
For operation 1, i.e., updating nums[idx] to val, it will only affect the values at positions idx - 1, idx, and idx + 1, so we only need to update these three positions. Specifically, we can first remove the peak elements at these three positions, then update the value of nums[idx], and finally add back the peak elements at these three positions.
The time complexity is O((n + q) times log n), and the space complexity is O(n). Here, n and q are the lengths of the array nums and the query array queries, respectively.
Python
Java
C++
Go
TypeScript
Rust
JavaScript
| Approach | Complexity |
|---|---|
| Naive Approach | Time Complexity: |
| Efficient Approach with Precomputation | Time Complexity: |
| Binary Indexed Tree | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Naive Scan | O(n) per query | O(1) | Small arrays or when the number of queries is very low |
| Precomputation + Binary Indexed Tree | O((n + q) log n) | O(n) | Best general solution for dynamic updates and frequent range queries |
| Segment Tree | O((n + q) log n) | O(n) | Useful when the problem expands to more complex range information |
3187. Peaks in Array | Segment Tree | Range Sum | 2 Line Change in Template | Fenwick Tree • Aryan Mittal • 3,269 views views
Watch 7 more video solutions →Practice Peaks in Array with our built-in code editor and test cases.
Practice on FleetCode