Peaks in Array II - Video Solutions
Leetcode Weekly Contest 514 | Q4 - Peaks in Array II | 4017 | Segment Tree + Sorted Multiset
Peaks in Array II - Video Solution
Watch 3 video solutions for Peaks in Array II, a hard level problem involving Array, Divide and Conquer, Segment Tree. This walkthrough by DSA with Kumar K has 934 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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
ksuch thati < k < jand:nums[k] > nums[k - 1]nums[k] > nums[k + 1]
You have to process queries of two types:
[1, li, ri]: Calculate the number of peak subarrays fully contained withinnums[li..ri].[2, indexi, vali]: Updatenums[indexi]tovali. This update applies to all subsequent queries.
Return an array answer, where answer[i] is the answer to the ith 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]: choosek = 1. Thennums[k] = 3,nums[k - 1] = 1, andnums[k + 1] = 2. Since3 > 1and3 > 2, this is a peak subarray.[1, 3, 2, 4]: choosek = 1. Thennums[k] = 3,nums[k - 1] = 1, andnums[k + 1] = 2. Since3 > 1and3 > 2, this is a peak subarray.
- Query
[2, 1, 1]: Updatenums[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]: choosek = 2. Thennums[k] = 9,nums[k - 1] = 8, andnums[k + 1] = 8. Since9 > 8and9 > 8, this is a peak subarray.
- Query
[2, 2, 1]: Updatenums[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 isk = 2, butnums[2] = 2is less than bothnums[1] = 6andnums[3] = 7, so it is not a peak subarray. - Query
[2, 3, 0]: Updatenums[3]to 0. The array becomes[3, 6, 2, 0, 1]. - Query
[1, 0, 4]:[3, 6, 2]: choosek = 1. Thennums[k] = 6,nums[k - 1] = 3, andnums[k + 1] = 2. Since6 > 3and6 > 2, this is a peak subarray.[3, 6, 2, 0]: choosek = 1. Thennums[k] = 6,nums[k - 1] = 3, andnums[k + 1] = 2. Since6 > 3and6 > 2, this is a peak subarray.[3, 6, 2, 0, 1]: choosek = 1. Thennums[k] = 6,nums[k - 1] = 3, andnums[k + 1] = 2. Since6 > 3and6 > 2, this is a peak subarray.
- Thus,
answer = [0, 3].
Constraints:
3 <= n == nums.length <= 1050 <= nums[i] <= 1051 <= queries.length <= 105queries[i] = [1, li, ri]orqueries[i] = [2, indexi, vali]0 <= li < ri <= n - 10 <= indexi <= n - 10 <= vali <= 105
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.