Off-by-one on range boundaries
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Break down a hard problem into reliable checkpoints, edge-case handling, and complexity trade-offs.
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 summary: 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: The first and the last element of an array or a subarray cannot be a peak.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Array · Segment Tree
[3,1,4,2,5] [[2,3,4],[1,0,4]]
[4,1,4,2,1,5] [[2,2,4],[1,0,2],[1,0,4]]
Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #3187: Peaks in Array
class BinaryIndexedTree {
private int n;
private int[] c;
public BinaryIndexedTree(int n) {
this.n = n;
this.c = new int[n + 1];
}
public void update(int x, int delta) {
for (; x <= n; x += x & -x) {
c[x] += delta;
}
}
public int query(int x) {
int s = 0;
for (; x > 0; x -= x & -x) {
s += c[x];
}
return s;
}
}
class Solution {
private BinaryIndexedTree tree;
private int[] nums;
public List<Integer> countOfPeaks(int[] nums, int[][] queries) {
int n = nums.length;
this.nums = nums;
tree = new BinaryIndexedTree(n - 1);
for (int i = 1; i < n - 1; ++i) {
update(i, 1);
}
List<Integer> ans = new ArrayList<>();
for (var q : queries) {
if (q[0] == 1) {
int l = q[1] + 1, r = q[2] - 1;
ans.add(l > r ? 0 : tree.query(r) - tree.query(l - 1));
} else {
int idx = q[1], val = q[2];
for (int i = idx - 1; i <= idx + 1; ++i) {
update(i, -1);
}
nums[idx] = val;
for (int i = idx - 1; i <= idx + 1; ++i) {
update(i, 1);
}
}
}
return ans;
}
private void update(int i, int val) {
if (i <= 0 || i >= nums.length - 1) {
return;
}
if (nums[i - 1] < nums[i] && nums[i] > nums[i + 1]) {
tree.update(i, val);
}
}
}
// Accepted solution for LeetCode #3187: Peaks in Array
type BinaryIndexedTree struct {
n int
c []int
}
func NewBinaryIndexedTree(n int) *BinaryIndexedTree {
return &BinaryIndexedTree{n: n, c: make([]int, n+1)}
}
func (bit *BinaryIndexedTree) update(x, delta int) {
for ; x <= bit.n; x += x & -x {
bit.c[x] += delta
}
}
func (bit *BinaryIndexedTree) query(x int) int {
s := 0
for ; x > 0; x -= x & -x {
s += bit.c[x]
}
return s
}
func countOfPeaks(nums []int, queries [][]int) (ans []int) {
n := len(nums)
tree := NewBinaryIndexedTree(n - 1)
update := func(i, val int) {
if i <= 0 || i >= n-1 {
return
}
if nums[i-1] < nums[i] && nums[i] > nums[i+1] {
tree.update(i, val)
}
}
for i := 1; i < n-1; i++ {
update(i, 1)
}
for _, q := range queries {
if q[0] == 1 {
l, r := q[1]+1, q[2]-1
t := 0
if l <= r {
t = tree.query(r) - tree.query(l-1)
}
ans = append(ans, t)
} else {
idx, val := q[1], q[2]
for i := idx - 1; i <= idx+1; i++ {
update(i, -1)
}
nums[idx] = val
for i := idx - 1; i <= idx+1; i++ {
update(i, 1)
}
}
}
return
}
# Accepted solution for LeetCode #3187: Peaks in Array
class BinaryIndexedTree:
__slots__ = "n", "c"
def __init__(self, n: int):
self.n = n
self.c = [0] * (n + 1)
def update(self, x: int, delta: int) -> None:
while x <= self.n:
self.c[x] += delta
x += x & -x
def query(self, x: int) -> int:
s = 0
while x:
s += self.c[x]
x -= x & -x
return s
class Solution:
def countOfPeaks(self, nums: List[int], queries: List[List[int]]) -> List[int]:
def update(i: int, val: int):
if i <= 0 or i >= n - 1:
return
if nums[i - 1] < nums[i] and nums[i] > nums[i + 1]:
tree.update(i, val)
n = len(nums)
tree = BinaryIndexedTree(n - 1)
for i in range(1, n - 1):
update(i, 1)
ans = []
for q in queries:
if q[0] == 1:
l, r = q[1] + 1, q[2] - 1
ans.append(0 if l > r else tree.query(r) - tree.query(l - 1))
else:
idx, val = q[1:]
for i in range(idx - 1, idx + 2):
update(i, -1)
nums[idx] = val
for i in range(idx - 1, idx + 2):
update(i, 1)
return ans
// Accepted solution for LeetCode #3187: Peaks in Array
impl Solution {
pub fn count_of_peaks(mut nums: Vec<i32>, queries: Vec<Vec<i32>>) -> Vec<i32> {
struct BinaryIndexedTree {
n: usize,
c: Vec<i32>,
}
impl BinaryIndexedTree {
fn new(n: usize) -> Self {
Self { n, c: vec![0; n + 1] }
}
fn update(&mut self, mut x: usize, delta: i32) {
while x <= self.n {
self.c[x] += delta;
x += x & (!x + 1);
}
}
fn query(&self, mut x: usize) -> i32 {
let mut s = 0;
while x > 0 {
s += self.c[x];
x &= x - 1;
}
s
}
}
let n = nums.len();
let mut tree = BinaryIndexedTree::new(n - 1);
let mut update = |i: usize, val: i32, nums: &Vec<i32>, tree: &mut BinaryIndexedTree| {
if i == 0 || i >= n - 1 {
return;
}
if nums[i - 1] < nums[i] && nums[i] > nums[i + 1] {
tree.update(i, val);
}
};
for i in 1..n - 1 {
update(i, 1, &nums, &mut tree);
}
let mut ans = Vec::new();
for q in queries {
if q[0] == 1 {
let l = (q[1] + 1).max(1) as usize;
let r = (q[2] - 1).max(0) as usize;
if l > r {
ans.push(0);
} else {
ans.push(tree.query(r) - tree.query(l - 1));
}
} else {
let idx = q[1] as usize;
let val = q[2];
let left = if idx > 0 { idx - 1 } else { 0 };
let right = usize::min(idx + 1, n - 1);
for i in left..=right {
update(i, -1, &nums, &mut tree);
}
nums[idx] = val;
for i in left..=right {
update(i, 1, &nums, &mut tree);
}
}
}
ans
}
}
// Accepted solution for LeetCode #3187: Peaks in Array
class BinaryIndexedTree {
private n: number;
private c: number[];
constructor(n: number) {
this.n = n;
this.c = Array(n + 1).fill(0);
}
update(x: number, delta: number): void {
for (; x <= this.n; x += x & -x) {
this.c[x] += delta;
}
}
query(x: number): number {
let s = 0;
for (; x > 0; x -= x & -x) {
s += this.c[x];
}
return s;
}
}
function countOfPeaks(nums: number[], queries: number[][]): number[] {
const n = nums.length;
const tree = new BinaryIndexedTree(n - 1);
const update = (i: number, val: number): void => {
if (i <= 0 || i >= n - 1) {
return;
}
if (nums[i - 1] < nums[i] && nums[i] > nums[i + 1]) {
tree.update(i, val);
}
};
for (let i = 1; i < n - 1; ++i) {
update(i, 1);
}
const ans: number[] = [];
for (const q of queries) {
if (q[0] === 1) {
const [l, r] = [q[1] + 1, q[2] - 1];
ans.push(l > r ? 0 : tree.query(r) - tree.query(l - 1));
} else {
const [idx, val] = [q[1], q[2]];
for (let i = idx - 1; i <= idx + 1; ++i) {
update(i, -1);
}
nums[idx] = val;
for (let i = idx - 1; i <= idx + 1; ++i) {
update(i, 1);
}
}
}
return ans;
}
Use this to step through a reusable interview workflow for this problem.
For each of q queries, scan the entire range to compute the aggregate (sum, min, max). Each range scan takes up to O(n) for a full-array query. With q queries: O(n × q) total. Point updates are O(1) but queries dominate.
Building the tree is O(n). Each query or update traverses O(log n) nodes (tree height). For q queries: O(n + q log n) total. Space is O(4n) ≈ O(n) for the tree array. Lazy propagation adds O(1) per node for deferred updates.
Review these before coding to avoid predictable interview regressions.
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.