LeetCode 3187 - Peaks in Array
The problem asks us to process two kinds of operations on an integer array: 1. Query how many peaks exist inside a subarray. 2. Update a single element in the array. A peak is defined as an element that is strictly greater than both its immediate neighbors.
Difficulty: 🔴 Hard
Topics: Array, Binary Indexed Tree, Segment Tree
Solution
Problem Understanding
The problem asks us to process two kinds of operations on an integer array:
- Query how many peaks exist inside a subarray.
- Update a single element in the array.
A peak is defined as an element that is strictly greater than both its immediate neighbors.
Formally, an index i is a peak if:
$nums[i] > nums[i-1] \text{ and } nums[i] > nums[i+1]$
However, there is an important restriction: the first and last elements of an array or subarray can never be peaks because they do not have two neighbors inside that range.
For a query [1, li, ri], we must count how many valid peak positions exist inside the subarray nums[li..ri].
For a query [2, index, val], we modify the array so that:
$nums[index] = val$
The constraints are large:
nums.length <= 10^5queries.length <= 10^5
These limits immediately tell us that recomputing peaks for every query from scratch will be too slow. We need an efficient data structure that supports:
- Fast range queries
- Fast point updates
The critical observation is that whether an index is a peak depends only on itself and its immediate neighbors. When one value changes, only a few nearby indices can change their peak status.
Several edge cases are important:
-
A subarray of length smaller than 3 can never contain a peak.
-
The endpoints of a queried subarray are never counted as peaks.
-
Updating one element may affect the peak status of:
-
index - 1 -
index -
index + 1 -
Multiple adjacent equal values are not peaks because the definition requires strictly greater values.
Approaches
Brute Force Approach
The most direct solution is to process each query independently.
For a type 1 query [1, li, ri], we iterate through every index from li + 1 to ri - 1 and check whether the current element is greater than both neighbors.
For a type 2 query [2, index, val], we simply update the array value.
This approach is correct because every query explicitly checks the peak condition directly from the array. However, it is too slow.
In the worst case:
- Each range query scans
O(n)elements. - There can be
10^5queries.
This leads to O(n * q) complexity, which can reach 10^10 operations.
Optimal Approach
The key insight is that peak status can be represented as a binary array.
Define:
peak[i] = 1if indexiis a peakpeak[i] = 0otherwise
Then a range query becomes a range sum query.
For query [1, li, ri], we only count peaks strictly inside the range:
- Valid positions are from
li + 1tori - 1
So we need:
$\sum_{i=li+1}^{ri-1} peak[i]$
A Binary Indexed Tree, also called a Fenwick Tree, efficiently supports:
- Point updates in
O(log n) - Prefix/range sum queries in
O(log n)
When updating nums[index], only nearby positions can change peak status:
index - 1indexindex + 1
We recompute only those positions and update the Fenwick Tree accordingly.
This gives an efficient solution for large constraints.
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(n × q) | O(1) | Scans every query range directly |
| Optimal | O((n + q) log n) | O(n) | Uses Fenwick Tree for dynamic peak counting |
Algorithm Walkthrough
- Create a helper function
is_peak(i).
This function determines whether index i is currently a peak. An index can only be a peak if:
1 <= i <= n - 2nums[i] > nums[i - 1]nums[i] > nums[i + 1]
Boundary indices are automatically excluded. 2. Build an array representing peak status.
For every valid index:
- Store
1if it is a peak - Store
0otherwise
This transforms the problem into dynamic range sum queries. 3. Build a Fenwick Tree.
The Fenwick Tree stores the peak indicators.
If peak[i] = 1, we add 1 at position i.
If peak[i] = 0, nothing is added.
This allows fast prefix sums. 4. Process type 1 queries.
For query [1, li, ri]:
- Peaks cannot occur at the endpoints
- So only indices in
[li + 1, ri - 1]matter
If the interval length is less than 3, the answer is 0.
Otherwise:
- Query the Fenwick Tree for the sum in that range
- Process type 2 queries.
For query [2, index, val]:
-
Before updating, record the old peak status for:
-
index - 1 -
index -
index + 1 -
Update
nums[index] -
Recompute the peak status for those same positions
-
If a position's peak value changed:
-
Update the Fenwick Tree with the difference
- Continue processing all queries.
Every operation now runs in logarithmic time.
Why it works
The algorithm works because the Fenwick Tree always stores the exact number of peaks at every index.
A range query simply sums those indicators over the valid internal portion of the subarray.
An update only affects nearby indices because the peak condition depends only on adjacent values. By recomputing exactly those affected positions, the data structure always remains consistent with the current array.
Python Solution
from typing import List
class FenwickTree:
def __init__(self, size: int):
self.size = size
self.tree = [0] * (size + 1)
def update(self, index: int, delta: int) -> None:
index += 1
while index <= self.size:
self.tree[index] += delta
index += index & -index
def query(self, index: int) -> int:
index += 1
result = 0
while index > 0:
result += self.tree[index]
index -= index & -index
return result
def range_query(self, left: int, right: int) -> int:
if left > right:
return 0
return self.query(right) - self.query(left - 1)
class Solution:
def countOfPeaks(self, nums: List[int], queries: List[List[int]]) -> List[int]:
n = len(nums)
def is_peak(index: int) -> int:
if index <= 0 or index >= n - 1:
return 0
return int(
nums[index] > nums[index - 1]
and nums[index] > nums[index + 1]
)
fenwick = FenwickTree(n)
peak = [0] * n
for i in range(1, n - 1):
peak[i] = is_peak(i)
if peak[i]:
fenwick.update(i, 1)
answers = []
for query in queries:
if query[0] == 1:
left = query[1]
right = query[2]
if right - left + 1 < 3:
answers.append(0)
else:
answers.append(
fenwick.range_query(left + 1, right - 1)
)
else:
index = query[1]
value = query[2]
affected = [index - 1, index, index + 1]
old_values = {}
for pos in affected:
if 0 <= pos < n:
old_values[pos] = peak[pos]
nums[index] = value
for pos in affected:
if 0 <= pos < n:
new_peak = is_peak(pos)
if new_peak != peak[pos]:
fenwick.update(pos, new_peak - peak[pos])
peak[pos] = new_peak
return answers
The implementation begins with a Fenwick Tree class. The tree supports prefix sum operations and point updates in logarithmic time.
The is_peak helper encapsulates the peak definition. Returning integers instead of booleans simplifies Fenwick Tree updates.
The initialization step computes the peak status for every valid position and inserts those values into the Fenwick Tree.
For range queries, the implementation carefully excludes the endpoints because they cannot be peaks within the queried subarray.
For updates, only the neighboring positions are reconsidered. This is the most important optimization in the solution. Recomputing the entire array after each update would be far too expensive.
Go Solution
package main
type FenwickTree struct {
tree []int
size int
}
func NewFenwickTree(size int) *FenwickTree {
return &FenwickTree{
tree: make([]int, size+1),
size: size,
}
}
func (f *FenwickTree) Update(index int, delta int) {
index++
for index <= f.size {
f.tree[index] += delta
index += index & -index
}
}
func (f *FenwickTree) Query(index int) int {
index++
result := 0
for index > 0 {
result += f.tree[index]
index -= index & -index
}
return result
}
func (f *FenwickTree) RangeQuery(left int, right int) int {
if left > right {
return 0
}
rightSum := f.Query(right)
leftSum := 0
if left > 0 {
leftSum = f.Query(left - 1)
}
return rightSum - leftSum
}
func countOfPeaks(nums []int, queries [][]int) []int {
n := len(nums)
isPeak := func(index int) int {
if index <= 0 || index >= n-1 {
return 0
}
if nums[index] > nums[index-1] &&
nums[index] > nums[index+1] {
return 1
}
return 0
}
fenwick := NewFenwickTree(n)
peak := make([]int, n)
for i := 1; i < n-1; i++ {
peak[i] = isPeak(i)
if peak[i] == 1 {
fenwick.Update(i, 1)
}
}
result := []int{}
for _, query := range queries {
if query[0] == 1 {
left := query[1]
right := query[2]
if right-left+1 < 3 {
result = append(result, 0)
} else {
result = append(
result,
fenwick.RangeQuery(left+1, right-1),
)
}
} else {
index := query[1]
value := query[2]
affected := []int{index - 1, index, index + 1}
nums[index] = value
for _, pos := range affected {
if pos >= 0 && pos < n {
newPeak := isPeak(pos)
if newPeak != peak[pos] {
fenwick.Update(pos, newPeak-peak[pos])
peak[pos] = newPeak
}
}
}
}
}
return result
}
The Go implementation closely mirrors the Python version.
Slices are used for both the Fenwick Tree storage and the peak array. Go does not have Python's dynamic dictionaries, so the update logic directly recomputes affected positions after the assignment.
Integer overflow is not a concern because the maximum number of peaks is at most n, which fits comfortably inside Go's int type under the given constraints.
Worked Examples
Example 1
Input:
nums = [3,1,4,2,5]
queries = [[2,3,4],[1,0,4]]
Initial peak evaluation:
| Index | Value | Peak? |
|---|---|---|
| 0 | 3 | No |
| 1 | 1 | No |
| 2 | 4 | Yes |
| 3 | 2 | No |
| 4 | 5 | No |
Initial peak array:
[0,0,1,0,0]
Fenwick Tree stores one peak at index 2.
Query 1
[2,3,4]
Update:
nums[3] = 4
New array:
[3,1,4,4,5]
Affected positions:
- 2
- 3
- 4
Recompute:
| Index | Value | Peak? |
|---|---|---|
| 2 | 4 | No |
| 3 | 4 | No |
| 4 | 5 | No |
Updated peak array:
[0,0,0,0,0]
Fenwick Tree removes the peak at index 2.
Query 2
[1,0,4]
Valid internal range:
[1,3]
Fenwick range sum:
0
Answer:
[0]
Worked Example 2
Input:
nums = [4,1,4,2,1,5]
queries = [[2,2,4],[1,0,2],[1,0,4]]
Initial peaks:
| Index | Value | Peak? |
|---|---|---|
| 1 | 1 | No |
| 2 | 4 | Yes |
| 3 | 2 | No |
| 4 | 1 | No |
Peak array:
[0,0,1,0,0,0]
Query 1
[2,2,4]
Value already equals 4.
No peak changes occur.
Query 2
[1,0,2]
Internal range:
[1,1]
Index 1 is not a peak.
Answer:
0
Query 3
[1,0,4]
Internal range:
[1,3]
Only index 2 is a peak.
Answer:
1
Final output:
[0,1]
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O((n + q) log n) | Fenwick Tree operations are logarithmic |
| Space | O(n) | Fenwick Tree and peak array each store O(n) elements |
The initialization step computes all peaks once in linear time.
Each query performs only a constant number of Fenwick Tree operations, and each Fenwick Tree update or query costs O(log n).
Because updates only affect three nearby positions, the update operation remains efficient even for the largest constraints.
Test Cases
from typing import List
class Solution:
def countOfPeaks(self, nums: List[int], queries: List[List[int]]) -> List[int]:
class FenwickTree:
def __init__(self, size: int):
self.size = size
self.tree = [0] * (size + 1)
def update(self, index: int, delta: int):
index += 1
while index <= self.size:
self.tree[index] += delta
index += index & -index
def query(self, index: int):
index += 1
result = 0
while index > 0:
result += self.tree[index]
index -= index & -index
return result
def range_query(self, left: int, right: int):
if left > right:
return 0
return self.query(right) - self.query(left - 1)
n = len(nums)
def is_peak(i: int):
if i <= 0 or i >= n - 1:
return 0
return int(nums[i] > nums[i - 1] and nums[i] > nums[i + 1])
fenwick = FenwickTree(n)
peak = [0] * n
for i in range(1, n - 1):
peak[i] = is_peak(i)
if peak[i]:
fenwick.update(i, 1)
answer = []
for q in queries:
if q[0] == 1:
l, r = q[1], q[2]
if r - l + 1 < 3:
answer.append(0)
else:
answer.append(fenwick.range_query(l + 1, r - 1))
else:
idx, val = q[1], q[2]
nums[idx] = val
for pos in [idx - 1, idx, idx + 1]:
if 0 <= pos < n:
new_peak = is_peak(pos)
if new_peak != peak[pos]:
fenwick.update(pos, new_peak - peak[pos])
peak[pos] = new_peak
return answer
sol = Solution()
# Provided example 1
assert sol.countOfPeaks(
[3,1,4,2,5],
[[2,3,4],[1,0,4]]
) == [0]
# Provided example 2
assert sol.countOfPeaks(
[4,1,4,2,1,5],
[[2,2,4],[1,0,2],[1,0,4]]
) == [0,1]
# No peaks anywhere
assert sol.countOfPeaks(
[1,2,3,4,5],
[[1,0,4]]
) == [0]
# Single peak in middle
assert sol.countOfPeaks(
[1,5,1],
[[1,0,2]]
) == [1]
# Query length less than 3
assert sol.countOfPeaks(
[1,3,1],
[[1,0,1],[1,1,2]]
) == [0,0]
# Multiple peaks
assert sol.countOfPeaks(
[1,5,1,5,1],
[[1,0,4]]
) == [2]
# Update destroys a peak
assert sol.countOfPeaks(
[1,5,1],
[[2,1,1],[1,0,2]]
) == [0]
# Update creates a peak
assert sol.countOfPeaks(
[1,2,1],
[[2,1,5],[1,0,2]]
) == [1]
# Equal adjacent values are not peaks
assert sol.countOfPeaks(
[1,3,3,1],
[[1,0,3]]
) == [0]
# Edge indices never count as peaks
assert sol.countOfPeaks(
[10,1,10],
[[1,0,2]]
) == [0]
| Test | Why |
|---|---|
| Provided example 1 | Validates update removing a peak |
| Provided example 2 | Validates mixed updates and queries |
| Strictly increasing array | Ensures no false peaks |
[1,5,1] |
Simplest valid peak |
| Query length less than 3 | Ensures endpoint rules handled correctly |
| Multiple peaks | Confirms range summation works |
| Peak destruction update | Validates Fenwick decrement logic |
| Peak creation update | Validates Fenwick increment logic |
| Equal adjacent values | Confirms strict comparison |
| Boundary peak check | Ensures endpoints never counted |
Edge Cases
One important edge case occurs when the queried subarray has fewer than three elements. A peak requires both a left and right neighbor, so no valid peak can exist. A naive implementation might accidentally count an endpoint as a peak. This solution explicitly checks the subarray length and immediately returns 0.
Another tricky case involves updates near the boundaries of the array. If index = 0 or index = n - 1, then index - 1 or index + 1 may go out of bounds. The implementation carefully validates every affected position before recomputing peak status.
Equal neighboring values are another common source of bugs. The definition requires strictly greater values. For example, in [1,3,3,1], neither 3 qualifies as a peak. The helper function uses strict > comparisons, ensuring duplicates are handled correctly.
A subtle issue appears when an update changes multiple nearby peaks simultaneously. For example, changing one value may destroy one peak while creating another. Because the implementation recomputes all affected positions independently and updates the Fenwick Tree using differences, the data structure always remains synchronized with the array state.