#3187

Hard

auto_awesomeArray plus Binary Indexed Tree

LeetCode Problem Workspace

Peaks in Array

Determine peaks in a dynamic integer array using efficient Binary Indexed Tree updates and range queries for fast results.

array binary indexed tree segment tree

Problem Statement

You are given an integer array nums. A peak is defined as an element greater than its neighbors: nums[i] is a peak if nums[i] > nums[i-1] and nums[i] > nums[i+1].

Additionally, you receive a 2D array queries where each query either updates a value or asks for the number of peaks in a subarray. Return the result for each type-2 query while processing updates efficiently.

Examples

Example 1

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

Output: [0]

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]

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 <= 105
1 <= nums[i] <= 105
1 <= queries.length <= 105
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] <= 105

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] <= 105

Solution Approach

Identify initial peaks

Create an array p where p[i] = 1 if nums[i] is a peak, otherwise 0. This array serves as the foundation for counting peaks quickly and detecting changes after updates.

Use Binary Indexed Tree for updates

Maintain a BIT over the peak array p. For each type-1 query (update), adjust the BIT for indices i-1, i, i+1 to reflect any peak status changes. For type-2 queries, use prefix sums from the BIT to count peaks in the given range efficiently.

Handle edge cases and large inputs

Check array boundaries to prevent out-of-range errors when computing peaks. For large arrays, BIT ensures O(log n) updates and queries, avoiding O(n) recalculation of peaks for every query.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O((n + q) log n) using a BIT, where n is the array size and q is the number of queries. Space complexity is O(n) for storing peaks and BIT structure.

What Interviewers Usually Probe

The problem expects efficient peak counting under frequent updates.
Mentioning a BIT or Segment Tree is a strong signal you understand range update patterns.
Handling boundary indices correctly is often probed for robustness.

Common Pitfalls or Variants

Common pitfalls

Not updating neighboring peak indicators after a value change, leading to incorrect counts.
Forgetting to check array bounds when computing peaks, causing runtime errors.
Using naive recalculation of all peaks per query results in TLE for large inputs.

Follow-up variants

Compute valleys instead of peaks using similar BIT or Segment Tree logic.
Allow range increments for type-1 queries, requiring more advanced lazy propagation.
Count peaks modulo a number to combine peak counting with numeric constraints.

FAQ

What defines a peak in the Peaks in Array problem?

A peak is any element nums[i] that is strictly greater than its immediate neighbors: nums[i-1] and nums[i+1].

Can Segment Trees replace the Binary Indexed Tree here?

Yes, Segment Trees with point updates and range queries can also track peaks, but BIT is often simpler and faster for 1D updates.

How do I handle updates that do not change the peak?

Check the peak status before and after the update for i-1, i, and i+1; update the BIT only if the status changes.

Why are boundaries tricky in this problem?

The first and last elements have only one neighbor, so you must avoid accessing out-of-range indices when checking peaks.

Is this problem always suited for Binary Indexed Tree?

Yes, the Array plus Binary Indexed Tree pattern is ideal for dynamic peak counting under multiple updates and range queries.

terminal

Solution

Solution 1: Binary Indexed Tree

According to the problem description, for $0 < i < n - 1$, if it satisfies $nums[i - 1] < nums[i]$ and $nums[i] > nums[i + 1]$, we can consider $nums[i]$ as $1$, otherwise as $0$. Thus, for operation $1$, i.e., querying the number of peak elements in the subarray $nums[l..r]$, it is equivalent to querying the number of $1$s in the interval $[l + 1, r - 1]$. We can use a binary indexed tree to maintain the number of $1$s in the interval $[1, n - 1]$.

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

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

Continue Practicing

#3161 block placement queries #3072 distribute elements into two arrays ii #3380 maximum area rectangle with point constraints i