Watch 8 video solutions for Peaks in Array, a hard level problem involving Array, Binary Indexed Tree, Segment Tree. This walkthrough by Aryan Mittal has 3,269 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |