Peaks in Array

Problem

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.

Examples

Example 1

1
2
3
4
5
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

1
2
3
4
5
6
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 <= 10^5
1 <= nums[i] <= 10^5
1 <= queries.length <= 10^5
queries[i][0] == 1 or queries[i][0] == 2
For all i that:
queries[i][0] == 1: 0 <= queries[i][1] <= queries[i][2] <= nums.length - 1
queries[i][0] == 2: 0 <= queries[i][1] <= nums.length - 1, 1 <= queries[i][2] <= 10^5

Solution

Method 1 - Fenwick Tree (Binary Indexed Tree)

Intuition

We need to efficiently support range peak queries and point updates. A peak is an element greater than its neighbors, and only elements at positions 1..n-2 can be peaks. We can use a Binary Indexed Tree (Fenwick Tree) or Segment Tree to maintain a binary array where 1 means the position is a peak, and 0 otherwise. For updates, only the updated index and its neighbors can change peak status.

Approach

Precompute a binary array is_peak where is_peak[i] = 1 if nums[i] is a peak.
Build a Fenwick Tree (or Segment Tree) over is_peak for range sum queries.
For update queries, update nums[index] and recompute peak status for index-1, index, and index+1.
For range queries, query the sum of is_peak in [li+1, ri-1] (since endpoints can’t be peaks).

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <vector>
using namespace std;
class Fenwick {
    vector<int> bit; int n;
public:
    Fenwick(int n): bit(n+2), n(n+2) {}
    void add(int i, int x) { for (++i; i < n; i += i&-i) bit[i] += x; }
    int sum(int i) { int s = 0; for (++i; i > 0; i -= i&-i) s += bit[i]; return s; }
    int range(int l, int r) { return sum(r) - sum(l-1); }
};
class Solution {
public:
    vector<int> processQueries(vector<int>& nums, vector<vector<int>>& queries) {
        int n = nums.size();
        vector<int> is_peak(n, 0);
        auto check = [&](int i) {
            return i > 0 && i < n-1 && nums[i] > nums[i-1] && nums[i] > nums[i+1];
        };
        for (int i = 1; i < n-1; ++i) is_peak[i] = check(i);
        Fenwick bit(n);
        for (int i = 0; i < n; ++i) if (is_peak[i]) bit.add(i, 1);
        vector<int> res;
        for (auto& q : queries) {
            if (q[0] == 1) {
                int l = q[1], r = q[2];
                if (r - l < 2) res.push_back(0);
                else res.push_back(bit.range(l+1, r-1));
            } else {
                int idx = q[1], val = q[2];
                nums[idx] = val;
                for (int d = -1; d <= 1; ++d) {
                    int i = idx + d;
                    if (i > 0 && i < n-1) {
                        int was = is_peak[i];
                        int now = check(i);
                        if (was != now) { bit.add(i, now - was); is_peak[i] = now; }
                    }
                }
            }
        }
        return res;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
type Fenwick struct { bit []int }
func NewFenwick(n int) *Fenwick { return &Fenwick{make([]int, n+2)} }
func (f *Fenwick) Add(i, x int) { for i++; i < len(f.bit); i += i&-i { f.bit[i] += x } }
func (f *Fenwick) Sum(i int) int { s := 0; for i++; i > 0; i -= i&-i { s += f.bit[i] }; return s }
func (f *Fenwick) Range(l, r int) int { return f.Sum(r) - f.Sum(l-1) }
func processQueries(nums []int, queries [][]int) []int {
    n := len(nums)
    isPeak := make([]int, n)
    check := func(i int) int {
        if i > 0 && i < n-1 && nums[i] > nums[i-1] && nums[i] > nums[i+1] { return 1 }
        return 0
    }
    for i := 1; i < n-1; i++ { isPeak[i] = check(i) }
    bit := NewFenwick(n)
    for i := 0; i < n; i++ { if isPeak[i] == 1 { bit.Add(i, 1) } }
    res := []int{}
    for _, q := range queries {
        if q[0] == 1 {
            l, r := q[1], q[2]
            if r-l < 2 { res = append(res, 0) } else { res = append(res, bit.Range(l+1, r-1)) }
        } else {
            idx, val := q[1], q[2]
            nums[idx] = val
            for d := -1; d <= 1; d++ {
                i := idx + d
                if i > 0 && i < n-1 {
                    was, now := isPeak[i], check(i)
                    if was != now { bit.Add(i, now-was); isPeak[i] = now }
                }
            }
        }
    }
    return res
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
import java.util.*;
class Fenwick {
    int[] bit;
    Fenwick(int n) { bit = new int[n+2]; }
    void add(int i, int x) { for (++i; i < bit.length; i += i&-i) bit[i] += x; }
    int sum(int i) { int s = 0; for (++i; i > 0; i -= i&-i) s += bit[i]; return s; }
    int range(int l, int r) { return sum(r) - sum(l-1); }
}
class Solution {
    public List<Integer> processQueries(int[] nums, int[][] queries) {
        int n = nums.length;
        int[] isPeak = new int[n];
        java.util.function.IntPredicate check = i -> i > 0 && i < n-1 && nums[i] > nums[i-1] && nums[i] > nums[i+1];
        for (int i = 1; i < n-1; i++) isPeak[i] = check.test(i) ? 1 : 0;
        Fenwick bit = new Fenwick(n);
        for (int i = 0; i < n; i++) if (isPeak[i] == 1) bit.add(i, 1);
        List<Integer> res = new ArrayList<>();
        for (int[] q : queries) {
            if (q[0] == 1) {
                int l = q[1], r = q[2];
                if (r - l < 2) res.add(0);
                else res.add(bit.range(l+1, r-1));
            } else {
                int idx = q[1], val = q[2];
                nums[idx] = val;
                for (int d = -1; d <= 1; d++) {
                    int i = idx + d;
                    if (i > 0 && i < n-1) {
                        int was = isPeak[i], now = check.test(i) ? 1 : 0;
                        if (was != now) { bit.add(i, now - was); isPeak[i] = now; }
                    }
                }
            }
        }
        return res;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Fenwick(n: Int) {
    private val bit = IntArray(n+2)
    fun add(i: Int, x: Int) { var idx = i+1; while (idx < bit.size) { bit[idx] += x; idx += idx and -idx } }
    fun sum(i: Int): Int { var idx = i+1; var s = 0; while (idx > 0) { s += bit[idx]; idx -= idx and -idx }; return s }
    fun range(l: Int, r: Int) = sum(r) - sum(l-1)
}
class Solution {
    fun processQueries(nums: IntArray, queries: Array<IntArray>): List<Int> {
        val n = nums.size
        val isPeak = IntArray(n)
        fun check(i: Int) = i > 0 && i < n-1 && nums[i] > nums[i-1] && nums[i] > nums[i+1]
        for (i in 1 until n-1) isPeak[i] = if (check(i)) 1 else 0
        val bit = Fenwick(n)
        for (i in 0 until n) if (isPeak[i] == 1) bit.add(i, 1)
        val res = mutableListOf<Int>()
        for (q in queries) {
            if (q[0] == 1) {
                val l = q[1]; val r = q[2]
                if (r - l < 2) res.add(0)
                else res.add(bit.range(l+1, r-1))
            } else {
                val idx = q[1]; val v = q[2]
                nums[idx] = v
                for (d in -1..1) {
                    val i = idx + d
                    if (i > 0 && i < n-1) {
                        val was = isPeak[i]; val now = if (check(i)) 1 else 0
                        if (was != now) { bit.add(i, now - was); isPeak[i] = now }
                    }
                }
            }
        }
        return res
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
class Fenwick:
    def __init__(self, n):
        self.n = n+2
        self.bit = [0]*(n+2)
    def add(self, i, x):
        i += 1
        while i < self.n:
            self.bit[i] += x
            i += i & -i
    def sum(self, i):
        i += 1
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= i & -i
        return s
    def range(self, l, r):
        return self.sum(r) - self.sum(l-1)

def processQueries(nums: list[int], queries: list[list[int]]) -> list[int]:
    n = len(nums)
    is_peak = [0]*n
    def check(i):
        return i > 0 and i < n-1 and nums[i] > nums[i-1] and nums[i] > nums[i+1]
    for i in range(1, n-1):
        is_peak[i] = check(i)
    bit = Fenwick(n)
    for i in range(n):
        if is_peak[i]: bit.add(i, 1)
    res = []
    for q in queries:
        if q[0] == 1:
            l, r = q[1], q[2]
            if r - l < 2:
                res.append(0)
            else:
                res.append(bit.range(l+1, r-1))
        else:
            idx, val = q[1], q[2]
            nums[idx] = val
            for d in [-1,0,1]:
                i = idx + d
                if 0 < i < n-1:
                    was, now = is_peak[i], check(i)
                    if was != now:
                        bit.add(i, now-was)
                        is_peak[i] = now
    return res

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
struct Fenwick {
    bit: Vec<i32>, n: usize
}
impl Fenwick {
    fn new(n: usize) -> Self { Self { bit: vec![0; n+2], n: n+2 } }
    fn add(&mut self, mut i: usize, x: i32) { i += 1; while i < self.n { self.bit[i] += x; i += i & (!i+1) } }
    fn sum(&self, mut i: usize) -> i32 { i += 1; let mut s = 0; while i > 0 { s += self.bit[i]; i -= i & (!i+1) } s }
    fn range(&self, l: usize, r: usize) -> i32 { self.sum(r) - self.sum(l-1) }
}
fn process_queries(nums: &mut [i32], queries: &[Vec<i32>]) -> Vec<i32> {
    let n = nums.len();
    let mut is_peak = vec![0; n];
    let check = |i: usize, nums: &[i32]| i > 0 && i < n-1 && nums[i] > nums[i-1] && nums[i] > nums[i+1];
    for i in 1..n-1 { is_peak[i] = check(i, nums) as i32; }
    let mut bit = Fenwick::new(n);
    for i in 0..n { if is_peak[i] == 1 { bit.add(i, 1); } }
    let mut res = vec![];
    for q in queries {
        if q[0] == 1 {
            let (l, r) = (q[1] as usize, q[2] as usize);
            if r < l+2 { res.push(0); } else { res.push(bit.range(l+1, r-1)); }
        } else {
            let (idx, val) = (q[1] as usize, q[2]);
            nums[idx] = val;
            for d in [-1,0,1] {
                let i = idx as i32 + d;
                if i > 0 && (i as usize) < n-1 {
                    let i = i as usize;
                    let was = is_peak[i];
                    let now = check(i, nums) as i32;
                    if was != now { bit.add(i, now-was); is_peak[i] = now; }
                }
            }
        }
    }
    res
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Fenwick {
    bit: number[]; n: number;
    constructor(n: number) { this.bit = new Array(n+2).fill(0); this.n = n+2; }
    add(i: number, x: number) { for (i++; i < this.n; i += i&-i) this.bit[i] += x; }
    sum(i: number) { let s = 0; for (i++; i > 0; i -= i&-i) s += this.bit[i]; return s; }
    range(l: number, r: number) { return this.sum(r) - this.sum(l-1); }
}
function processQueries(nums: number[], queries: number[][]): number[] {
    const n = nums.length;
    const isPeak = new Array(n).fill(0);
    const check = (i: number) => i > 0 && i < n-1 && nums[i] > nums[i-1] && nums[i] > nums[i+1];
    for (let i = 1; i < n-1; i++) isPeak[i] = check(i) ? 1 : 0;
    const bit = new Fenwick(n);
    for (let i = 0; i < n; i++) if (isPeak[i]) bit.add(i, 1);
    const res: number[] = [];
    for (const q of queries) {
        if (q[0] === 1) {
            const [_, l, r] = q;
            if (r - l < 2) res.push(0);
            else res.push(bit.range(l+1, r-1));
        } else {
            const [_, idx, val] = q;
            nums[idx] = val;
            for (let d = -1; d <= 1; d++) {
                const i = idx + d;
                if (i > 0 && i < n-1) {
                    const was = isPeak[i], now = check(i) ? 1 : 0;
                    if (was !== now) { bit.add(i, now - was); isPeak[i] = now; }
                }
            }
        }
    }
    return res;
}

Complexity

⏰ Time complexity: O(Q log N) where Q is the number of queries and N is the array length
🧺 Space complexity: O(N)

Problem#

Examples#

Example 1#

Example 2#

Constraints#

Solution#

Method 1 - Fenwick Tree (Binary Indexed Tree)#

Intuition#

Approach#

Code#

Complexity#