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] <= 105The key challenge in #3187 Peaks in Array is efficiently identifying and maintaining peak elements (elements greater than their immediate neighbors) while handling updates or range queries. A naive approach that recalculates peaks after every change would be too slow for large inputs.
A more efficient strategy is to maintain a separate structure that tracks whether each index forms a peak. When an update occurs, only the affected indices (typically the updated position and its neighbors) need to be re-evaluated. To quickly answer queries about how many peaks exist in a range, you can store these peak indicators in a Binary Indexed Tree (Fenwick Tree) or a Segment Tree.
These data structures allow fast prefix or range aggregation while supporting updates in O(log n) time. The overall approach reduces repeated scanning of the array and ensures queries and updates remain efficient even for large datasets.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Binary Indexed Tree | O(log n) per update/query | O(n) |
| Segment Tree | O(log n) per update/query | O(n) |
take U forward
Use these hints if you're stuck. Try solving on your own first.
Let <code>p[i]</code> be whether <code>nums[i]</code> is a peak in the original array. Namely <code>p[i] = nums[i] > nums[i - 1] && nums[i] > nums[i + 1]</code>.
Updating <code>nums[i]</code>, only affects <code>p[i]</code>, <code>p[i - 1]</code> and <code>p[i + 1]</code>. We can recalculate the 3 values in constant time.
The answer for <code>[l<sub>i</sub>, r<sub>i</sub>]</code> is <code>p[l<sub>i</sub> + 1] + p[l<sub>i</sub> + 2] + … + p[r<sub>i</sub> - 1]</code> (note that <code>l<sub>i</sub></code> and <code>r<sub>i</sub></code> are not included).
Use some data structures (i.e. segment tree or binary indexed tree) to maintain the subarray sum efficiently.
Watch expert explanations and walkthroughs
Jot down your thoughts, approach, and key learnings
Problems involving peak detection with dynamic updates and range queries are common in top tech interviews. Variants that require Segment Trees or Fenwick Trees are frequently used to test advanced data structure knowledge.
Binary Indexed Trees and Segment Trees are commonly used for this problem. They allow efficient updates and range queries, which is essential when peak values must be counted dynamically after modifications.
The optimal approach maintains peak indicators in a Binary Indexed Tree or Segment Tree. Whenever an element changes, only nearby indices are rechecked for peak conditions, allowing queries and updates to run in logarithmic time.
A brute-force solution would scan the entire array to recompute peaks after every update or query, resulting in O(n) per operation. With many operations, this becomes too slow, making logarithmic data structures necessary.