# Peaks in Array
**Difficulty:** HARD
[External](https://leetcode.com/problems/peaks-in-array)
Canonical: https://scaleengineer.com/dsa/problems/peaks-in-array
**Data structures:** Array, Binary Indexed Tree, Segment Tree
**Companies:** [Siemens](https://scaleengineer.com/companies/siemens)
---
## 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.

**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 <= 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`

# Approaches
## Brute Force Iteration
This approach directly simulates the process described in the problem. For each query of type 1, it iterates through the specified subarray to count the peaks. For each query of type 2, it updates the element in the array. This method is straightforward but inefficient.
**Time:** O(Q * N), where Q is the number of queries and N is the length of `nums`. For each type 1 query, we might iterate up to O(N) elements. In the worst-case scenario where most queries are of type 1, the total time complexity becomes prohibitive. · **Space:** O(K), where K is the number of type 1 queries. This space is used to store the results. If the output array is not considered, the auxiliary space complexity is O(1).
**Pros:** Simple to understand and implement.; Requires minimal extra space.
**Cons:** Highly inefficient for large inputs, as it re-computes the peak count for every type 1 query.; This approach will likely result in a 'Time Limit Exceeded' (TLE) error on platforms with strict time limits.
### Explanation
The brute-force approach tackles the problem in the most direct way possible. For a type 1 query `[1, l, r]`, we simply loop through the subarray from index `l` to `r`. According to the problem's definition, a peak cannot be the first or last element of a subarray, so our check for peaks only needs to run from index `l+1` to `r-1`. For each index `i` in this range, we check if `nums[i]` is greater than its immediate neighbors, `nums[i-1]` and `nums[i+1]`. If it is, we count it as a peak. For a type 2 query `[2, index, val]`, we perform a simple update on the `nums` array at the given index with the new value. While this method is easy to understand and implement, its performance degrades significantly as the size of the array and the number of queries increase, especially when type 1 queries cover large ranges.

```java
class Solution {
    public java.util.List<Integer> countPeaks(int[] nums, int[][] queries) {
        java.util.List<Integer> result = new java.util.ArrayList<>();
        for (int[] query : queries) {
            if (query[0] == 1) {
                int l = query[1];
                int r = query[2];
                int count = 0;
                // A peak must have a previous and next element, so we check from l+1 to r-1.
                for (int i = l + 1; i <= r - 1; i++) {
                    if (nums[i] > nums[i - 1] && nums[i] > nums[i + 1]) {
                        count++;
                    }
                }
                result.add(count);
            } else { // query[0] == 2
                int index = query[1];
                int val = query[2];
                nums[index] = val;
            }
        }
        return result;
    }
}
```
### Algorithm
- Initialize an empty list `answer` to store results for type 1 queries.
- Iterate through each `query` in the `queries` array.
- If the query is of type 1, `[1, l, r]`:
  - Initialize a counter `peak_count` to 0.
  - Iterate with an index `i` from `l + 1` to `r - 1`.
  - Inside the loop, check if `nums[i]` is a peak by comparing it with its neighbors: `nums[i] > nums[i-1]` and `nums[i] > nums[i+1]`.
  - If it is a peak, increment `peak_count`.
  - After the loop, add `peak_count` to the `answer` list.
- If the query is of type 2, `[2, index, val]`:
  - Directly update the array: `nums[index] = val`.
- After processing all queries, return the `answer` list.

## Fenwick Tree (Binary Indexed Tree)
This approach uses a Fenwick Tree (also known as a Binary Indexed Tree or BIT) to achieve much better performance. The core idea is to maintain an auxiliary data structure that can provide the count of peaks in a given range and can be updated efficiently. We first determine the initial peaks in the array and build a Fenwick Tree based on them. A type 1 query becomes a range sum query on the BIT, and a type 2 update only requires updating a few points in the BIT.
**Time:** O(N log N + Q log N). The initial build of the Fenwick Tree takes O(N log N). Each of the Q queries, whether type 1 (range sum) or type 2 (point update), takes O(log N) time. · **Space:** O(N) to store the `nums` array and the Fenwick Tree.
**Pros:** Highly efficient, with logarithmic time complexity for both query and update operations.; Scales well for large inputs and a high number of queries.
**Cons:** More complex to implement compared to the brute-force approach.; Requires understanding of advanced data structures like Fenwick Trees or Segment Trees.
### Explanation
To optimize the process, we can use a data structure that supports fast range sum queries and point updates. A Fenwick Tree is an excellent choice for this.

**Initialization:**
We create a Fenwick Tree of size `N`. We iterate through the initial `nums` array from index 1 to `N-2` and for each index `i` that is a peak, we perform an update operation on our Fenwick Tree: `bit.update(i, 1)`. This pre-computation phase builds the BIT in `O(N log N)` time.

**Type 1 Query `[1, l, r]`:**
The number of peaks in the subarray `nums[l..r]` is the sum of peaks at indices from `l+1` to `r-1`. With the Fenwick Tree, this range sum can be computed in `O(log N)` time using two prefix sum queries: `bit.query(r-1) - bit.query(l)`. We must handle the edge case where `l+1 > r-1`, for which the count is 0.

**Type 2 Query `[2, index, val]`:**
When `nums[index]` is updated, the peak status can change only for `index` itself and its immediate neighbors, `index-1` and `index+1`. We must check these three indices (if they are within the valid range `[1, N-2]`). For each of these indices, we first check if it was a peak before the update. If it was, we remove its contribution from the Fenwick Tree by updating its value by -1. Then, we update `nums[index]` to `val`. Finally, we re-check if these same three indices are peaks with the new array values. If an index becomes a peak, we add its contribution back by updating its value by +1 in the Fenwick Tree. Since this involves a constant number of checks and BIT updates, a type 2 query is also handled in `O(log N)` time.

```java
class FenwickTree {
    private int[] bit;
    private int size;

    public FenwickTree(int n) {
        this.size = n;
        this.bit = new int[n + 1];
    }

    public void update(int index, int delta) {
        index++; // 1-based index for BIT
        while (index <= size) {
            bit[index] += delta;
            index += index & -index;
        }
    }

    public int query(int index) {
        if (index < 0) return 0;
        index++; // 1-based index for BIT
        int sum = 0;
        while (index > 0) {
            sum += bit[index];
            index -= index & -index;
        }
        return sum;
    }
}

class Solution {
    private boolean isPeak(int[] nums, int i, int n) {
        if (i <= 0 || i >= n - 1) {
            return false;
        }
        return nums[i] > nums[i - 1] && nums[i] > nums[i + 1];
    }

    public java.util.List<Integer> countPeaks(int[] nums, int[][] queries) {
        int n = nums.length;
        FenwickTree ft = new FenwickTree(n);
        for (int i = 1; i < n - 1; i++) {
            if (isPeak(nums, i, n)) {
                ft.update(i, 1);
            }
        }

        java.util.List<Integer> result = new java.util.ArrayList<>();
        for (int[] q : queries) {
            if (q[0] == 1) {
                int l = q[1];
                int r = q[2];
                if (r - l < 2) {
                    result.add(0);
                } else {
                    // Query sum for range [l+1, r-1]
                    int count = ft.query(r - 1) - ft.query(l);
                    result.add(count);
                }
            } else {
                int index = q[1];
                int val = q[2];

                java.util.Set<Integer> affectedIndices = new java.util.HashSet<>();
                for (int i = index - 1; i <= index + 1; i++) {
                    if (i > 0 && i < n - 1) {
                        affectedIndices.add(i);
                    }
                }

                for (int i : affectedIndices) {
                    if (isPeak(nums, i, n)) {
                        ft.update(i, -1);
                    }
                }

                nums[index] = val;

                for (int i : affectedIndices) {
                    if (isPeak(nums, i, n)) {
                        ft.update(i, 1);
                    }
                }
            }
        }
        return result;
    }
}
```
### Algorithm
- Define a helper function `isPeak(nums, i, n)` that returns `true` if `nums[i]` is a peak, considering array boundaries.
- **Initialization**:
  - Create a Fenwick Tree (BIT) data structure of size `N`.
  - Iterate from `i = 1` to `N-2`. If `isPeak(nums, i, N)` is true, update the BIT at index `i` by 1: `bit.update(i, 1)`.
- **Processing Queries**:
  - Initialize an empty list `answer`.
  - For each `query` in `queries`:
    - If it's a type 1 query `[1, l, r]`:
      - If `r - l < 2`, no peaks are possible, so add 0 to `answer`.
      - Otherwise, the number of peaks is the sum in the range `[l+1, r-1]`. This is computed using the BIT as `bit.query(r-1) - bit.query(l)`. Add this count to `answer`.
    - If it's a type 2 query `[2, index, val]`:
      - Identify the indices whose peak status could change: `index-1`, `index`, and `index+1`.
      - For each of these potentially affected indices `i` (within `[1, N-2]`):
        - Check if `i` was a peak *before* the update. If yes, decrement the count in the BIT: `bit.update(i, -1)`.
      - Perform the update: `nums[index] = val`.
      - For the same affected indices `i`:
        - Check if `i` is a peak *after* the update. If yes, increment the count in the BIT: `bit.update(i, 1)`.
- Return the `answer` list.

# Solutions
### Java

```java
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 ); } } }
```

### CPP

```cpp
class BinaryIndexedTree { private: int n ; vector < int > c ; public: BinaryIndexedTree ( int n ) : n ( n ) , c ( n + 1 ) {} void update ( int x , int delta ) { for (; x <= n ; x += x & - x ) { c [ x ] += delta ; } } int query ( int x ) { int s = 0 ; for (; x > 0 ; x -= x & - x ) { s += c [ x ]; } return s ; } }; class Solution { public: vector < int > countOfPeaks ( vector < int >& nums , vector < vector < int >>& queries ) { int n = nums . size (); BinaryIndexedTree tree ( n - 1 ); auto update = [ & ]( int i , int val ) { if ( i <= 0 || i >= n - 1 ) { return ; } if ( nums [ i - 1 ] < nums [ i ] && nums [ i ] > nums [ i + 1 ]) { tree . update ( i , val ); } }; for ( int i = 1 ; i < n - 1 ; ++ i ) { update ( i , 1 ); } vector < int > ans ; for ( auto & q : queries ) { if ( q [ 0 ] == 1 ) { int l = q [ 1 ] + 1 , r = q [ 2 ] - 1 ; ans . push_back ( 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 ; } };
```

### Python

```python
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
```