Peaks in Array II - Solution & Explanation

HardArray Divide and Conquer Segment Tree5 min read

Practice this problem

Problem Statement

You are given an integer array nums of length n and a 2D integer array queries.

A subarray nums[i..j] is called a peak subarray if:

Its length is at least 3.
There exists an index k such that i < k < j and:
- nums[k] > nums[k - 1]
- nums[k] > nums[k + 1]

You have to process queries of two types:

[1, l_i, r_i]: Calculate the number of peak subarrays fully contained within nums[l_i..r_i].
[2, index_i, val_i]: Update nums[index_i] to val_i. This update applies to all subsequent queries.

Return an array answer, where answer[i] is the answer to the i^th query of type 1 in the order they appear.

Example 1:

Input: nums = [1,3,2,4], queries = [[1,0,3],[2,1,1],[1,0,3]]

Output: [2,0]

Explanation:

Query [1, 0, 3]:
- [1, 3, 2]: choose k = 1. Then nums[k] = 3, nums[k - 1] = 1, and nums[k + 1] = 2. Since 3 > 1 and 3 > 2, this is a peak subarray.
- [1, 3, 2, 4]: choose k = 1. Then nums[k] = 3, nums[k - 1] = 1, and nums[k + 1] = 2. Since 3 > 1 and 3 > 2, this is a peak subarray.
Query [2, 1, 1]: Update nums[1] to 1. The array becomes [1, 1, 2, 4].
Query [1, 0, 3]: There are no peak subarrays now.
Thus, answer = [2, 0].

Example 2:

Input: nums = [9,8,9,8], queries = [[1,1,3],[2,2,1],[1,0,2]]

Output: [1,0]

Explanation:

Query [1, 1, 3]:
- nums[1..3] = [8, 9, 8]: choose k = 2. Then nums[k] = 9, nums[k - 1] = 8, and nums[k + 1] = 8. Since 9 > 8 and 9 > 8, this is a peak subarray.
Query [2, 2, 1]: Update nums[2] to 1. The array becomes [9, 8, 1, 8].
Query [1, 0, 2]: There are no peak subarrays.
Thus, answer = [1, 0].

Example 3:

Input: nums = [3,6,2,7,1], queries = [[1,1,3],[2,3,0],[1,0,4]]

Output: [0,3]

Explanation:

Query [1, 1, 3]: The only subarray of length at least 3 is [6, 2, 7]. Its only possible peak index is k = 2, but nums[2] = 2 is less than both nums[1] = 6 and nums[3] = 7, so it is not a peak subarray.
Query [2, 3, 0]: Update nums[3] to 0. The array becomes [3, 6, 2, 0, 1].
Query [1, 0, 4]:
- [3, 6, 2]: choose k = 1. Then nums[k] = 6, nums[k - 1] = 3, and nums[k + 1] = 2. Since 6 > 3 and 6 > 2, this is a peak subarray.
- [3, 6, 2, 0]: choose k = 1. Then nums[k] = 6, nums[k - 1] = 3, and nums[k + 1] = 2. Since 6 > 3 and 6 > 2, this is a peak subarray.
- [3, 6, 2, 0, 1]: choose k = 1. Then nums[k] = 6, nums[k - 1] = 3, and nums[k + 1] = 2. Since 6 > 3 and 6 > 2, this is a peak subarray.
Thus, answer = [0, 3].

Constraints:

3 <= n == nums.length <= 10⁵
0 <= nums[i] <= 10⁵
1 <= queries.length <= 10⁵
queries[i] = [1, l_i, r_i] or queries[i] = [2, index_i, val_i]
0 <= l_i < r_i <= n - 1
0 <= index_i <= n - 1
0 <= val_i <= 10⁵

Approach Overview

Problem Overview: You are given an array of integers and a series of queries. Each query either updates an element at a specific index or asks for the number of peaks (elements strictly greater than both neighbors) within a subarray. The challenge is to handle both operations efficiently—especially when the array is large and queries are numerous.

Approach 1: Brute Force (O(n) per query)

For each query, directly scan the subarray or the entire array to count peaks. For an update, modify the value and then re-evaluate the peak status of the affected index and its two neighbors by checking local comparisons. This approach uses no extra data structures beyond the array itself and has O(1) space but O(n) time per query—making it impractical for large inputs or many queries.

Approach 2: Segment Tree (O(log n) per query)

Maintain a boolean array isPeak[i] that indicates whether index i is currently a peak. Build a segment tree over this boolean array where each node stores the count of true values in its segment. For an update at index idx, recalculate isPeak[idx], isPeak[idx-1], and isPeak[idx+1] because only these can change when nums[idx] changes—then update those positions in the segment tree using point updates (O(log n)). For a range query [l, r], perform a standard range sum query on the segment tree to get the number of peaks in O(log n). This reduces total time complexity to O((n + q) log n) for q queries.

Approach 3: Binary Indexed Tree / Fenwick Tree (O(log n) per query)

An alternative to the segment tree is a Fenwick tree (BIT) that also supports point updates and prefix sum queries. The key insight is that you only need to update at most three indices per update operation—the same logic as the segment tree approach. BITs are simpler to implement and use less memory than segment trees, but they require careful handling when computing range sums (using prefix sums). Both achieve O(log n) per operation.

Recommended for interviews: Interviewers expect you to recognize that brute force is insufficient for large inputs and that you need a data structure that supports fast point updates and range queries—typically a segment tree or Fenwick tree. Start by explaining the brute force to show you understand the problem, then transition to the segment tree solution, emphasizing how you maintain peak status locally and use lazy propagation if needed (though not required here). This demonstrates both algorithmic depth and practical coding skill.

Solutions for this problem are being prepared.

Try solving it yourself