Talentd
For employersSign in
JobsInternshipsPracticeResume toolsCompaniesArticles
For employers
FleetCode
Make and follow sheets.Sign in

Peaks in Array solution and explanation

HardArrayBinary Indexed TreeSegment Tree7 min read28.5% acceptanceUpdated 9 Apr 2026
Asked atSiemens
Practise Peaks in Array
18:06
3187. Peaks in Array | Segment Tree | Range Sum | 2 Line Change in Template | Fenwick TreeAryan Mittal · 18:06 · 3K viewsWatch on YouTube
7 more videos on this problem
  1. 3187. Peaks in Array | Segment Tree | Range Sum | 2 Line Change in Template | Fenwick TreeAryan Mittal · 18:06 · 3K views
  2. 3187. Peaks in Array | Weekly Leetcode 402codingMohan · 24:07 · 736 views
  3. Leetcode | Weekly Contest 402 | B | C | D | 3185 | 3186 | 3187 | Editorial | Peaks in array SolutionPretest Passed · 43:35 · 481 views
  4. 3187. Peaks in Array (Leetcode Hard)Programming Live with Larry · 23:39 · 318 views
  5. LeetCode 3187 | Peaks in Array | Weekly Contest 402 | #leetcodecontest #weeklycontest #programmingAlgo Horizon · 27:01 · 258 views
  6. 【每日一题】LeetCode 3187. Peaks in ArrayHuifeng Guan · 10:41 · 187 views
  7. 3187. Peaks in Array (Segment Tree Approach) Leetcode Weekly contest 402X AlphA - Hard Algorithms · 19:04 · 65 views
  8. LeetCode 3187. Peaks in Array with Efficient Solution in TypeScript & JavaScriptRuslan Tsykaliak · 15:12 · 22 views

The 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

Approach overview

Problem Overview: You are given an integer array and multiple queries. A position i is a peak if nums[i] > nums[i-1] and nums[i] > nums[i+1]. Queries either ask for the number of peaks in a subarray or update a value in the array. After updates, peak positions can change, so the structure must support fast range queries and local updates.

Approach 1: Naive Scan (O(n) per query, O(1) space)

For each query asking for the number of peaks in a range [l, r], iterate through indices l+1 to r-1 and check whether each index forms a peak. Updates simply modify the array value directly. This approach uses straightforward iteration over the array and recomputes peaks every time a query is processed. Time complexity becomes O(n * q) in the worst case because each query may scan most of the array.

Approach 2: Precomputation + Binary Indexed Tree (O((n + q) log n) time, O(n) space)

Create a helper array peak[i] where peak[i] = 1 if index i is a peak, otherwise 0. Build a Binary Indexed Tree over this array so you can quickly compute prefix sums. A range query for peaks in [l, r] becomes a sum query over [l+1, r-1]. When an update modifies nums[i], only indices i-1, i, and i+1 can change peak status. Recalculate those positions and update the Fenwick tree accordingly. Each update and query runs in O(log n) time.

Approach 3: Segment Tree (O((n + q) log n) time, O(n) space)

A Segment Tree can also store the number of peaks within each segment. Build the tree using the precomputed peak array. Range queries return the count of peaks in [l+1, r-1]. Updates propagate changes when peak indicators at nearby indices change. This approach provides the same asymptotic complexity as the Fenwick tree but is more flexible if additional range information needs to be stored.

Recommended for interviews: The Binary Indexed Tree solution is typically expected. The brute-force scan demonstrates understanding of the peak definition, but interviewers usually want the optimized solution with O(log n) updates and queries. Recognizing that only three indices can change peak status after an update is the key insight that enables the efficient design.

Approach 1: Naive Approach

The naive approach involves iterating through the subarray specified in the query to count the number of peaks. For each type 1 query, check all elements from l to r and determine if each is a peak by checking its neighbors. For type 2 queries, simply update the element and proceed with the next query.

def processQueries(nums, queries):
    results = []
    for query in queries:
        if query[0] == 1:
            l, r = query[1], query[2]
            peak_count = 0
            for j in range(l + 1, r):
                if nums[j] > nums[j - 1] and nums[j] > nums[j + 1]:
                    peak_count += 1
            results.append(peak_count)
        elif query[0] == 2:
            nums[query[1]] = query[2]
    return results

# Example usage:
nums = [3, 1, 4, 2, 5]
queries = [[2, 3, 4], [1, 0, 4]]
result = processQueries(nums, queries)
print(result)
import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<Integer> processQueries(int[] nums, int[][] queries) {
        List<Integer> results = new ArrayList<>();

        for (int[] query : queries) {
            if (query[0] == 1) {
                int l = query[1], r = query[2];
                int peakCount = 0;
                for (int j = l + 1; j < r; ++j) {
                    if (nums[j] > nums[j - 1] && nums[j] > nums[j + 1]) {
                        peakCount++;
                    }
                }
                results.add(peakCount);
            } else if (query[0] == 2) {
                nums[query[1]] = query[2];
            }
        }

        return results;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] nums = {3, 1, 4, 2, 5};
        int[][] queries = {{2, 3, 4}, {1, 0, 4}};
        List<Integer> result = sol.processQueries(nums, queries);
        for (int res : result) {
            System.out.println(res);
        }
    }
}
#include <iostream>
#include <vector>
using namespace std;

vector<int> processQueries(vector<int>& nums, vector<vector<int>>& queries) {
    vector<int> results;
    for (const auto& query : queries) {
        if (query[0] == 1) {
            int l = query[1], r = query[2];
            int peakCount = 0;
            for (int j = l + 1; j < r; ++j) {
                if (nums[j] > nums[j - 1] && nums[j] > nums[j + 1]) {
                    peakCount++;
                }
            }
            results.push_back(peakCount);
        } else if (query[0] == 2) {
            nums[query[1]] = query[2];
        }
    }
    return results;
}

int main() {
    vector<int> nums = {3, 1, 4, 2, 5};
    vector<vector<int>> queries = {{2, 3, 4}, {1, 0, 4}};

    vector<int> result = processQueries(nums, queries);
    for (int res : result) {
        cout << res << "\n";
    }

    return 0;
}
function processQueries(nums, queries) {
    const results = [];
    queries.forEach((query) => {
        if (query[0] === 1) {
            const [_, l, r] = query;
            let peakCount = 0;
            for (let j = l + 1; j < r; ++j) {
                if (nums[j] > nums[j - 1] && nums[j] > nums[j + 1]) {
                    peakCount++;
                }
            }
            results.push(peakCount);
        } else if (query[0] === 2) {
            nums[query[1]] = query[2];
        }
    });
    return results;
}

// Example usage:
const nums = [3, 1, 4, 2, 5];
const queries = [[2, 3, 4], [1, 0, 4]];
const result = processQueries(nums, queries);
console.log(result);
#include <stdio.h>
#include <stdlib.h>

int* processQueries(int* nums, int numsSize, int** queries, int queriesSize, int* returnSize) {
    *returnSize = 0;
    int* results = (int*)malloc(queriesSize * sizeof(int));
    
    for (int i = 0; i < queriesSize; ++i) {
        int type = queries[i][0];
        if (type == 1) {
            int l = queries[i][1];
            int r = queries[i][2];
            int peakCount = 0;
            for (int j = l + 1; j < r; ++j) {
                if (nums[j] > nums[j - 1] && nums[j] > nums[j + 1]) {
                    peakCount++;
                }
            }
            results[(*returnSize)++] = peakCount;
        } else if (type == 2) {
            int index = queries[i][1];
            int value = queries[i][2];
            nums[index] = value;
        }
    }

    return results;
}

int main() {
    // Example usage
    int nums[] = {3, 1, 4, 2, 5};
    int numsSize = 5;

    int q1[] = {2, 3, 4};
    int q2[] = {1, 0, 4};
    int* queries[] = {q1, q2};
    int queriesSize = 2;

    int returnSize;
    int* result = processQueries(nums, numsSize, queries, queriesSize, &returnSize);

    for (int i = 0; i < returnSize; ++i) {
        printf("%d\n", result[i]);
    }

    free(result);

    return 0;
}
using System;
using System.Collections.Generic;

public class Solution {
    public List<int> ProcessQueries(int[] nums, int[][] queries) {
        List<int> results = new List<int>();

        foreach (var query in queries) {
            if (query[0] == 1) {
                int l = query[1], r = query[2];
                int peakCount = 0;
                for (int j = l + 1; j < r; ++j) {
                    if (nums[j] > nums[j - 1] && nums[j] > nums[j + 1]) {
                        peakCount++;
                    }
                }
                results.Add(peakCount);
            } else if (query[0] == 2) {
                nums[query[1]] = query[2];
            }
        }

        return results;
    }

    public static void Main() {
        int[] nums = {3, 1, 4, 2, 5};
        int[][] queries = new int[][] {
            new int[] {2, 3, 4},
            new int[] {1, 0, 4}
        };

        Solution sol = new Solution();
        List<int> result = sol.ProcessQueries(nums, queries);
        result.ForEach(Console.WriteLine);
    }
}

This Python solution iterates through each query, processing peak counts for subarrays specified in type 1 queries and altering the elements as specified in type 2 queries. A straightforward list is used for results.

Complexity

Time Complexity: O(Q * (r-l)) where Q is the number of queries and (r-l) is the length of the subarray to check for peaks.
Space Complexity: O(1) with possible space for result list.

Try this approach in the editor

Approach 2: Efficient Approach with Precomputation

In this approach, the main idea is to maintain a set or list of current peak indices. We update this list whenever an element changes in a type 2 query. For type 1 queries, we simply count the peaks that fall within the queried range. This requires precomputing the peak indices and adjusting the list dynamically.

def processQueries(nums, queries):
    results = []
    peaks = [0] * len(nums)

    # Precompute peaks
    for i in range(1, len(nums) - 1):
        if nums[i] > nums[i - 1] and nums[i] > nums[i + 1]:
            peaks[i] = 1

    for query in queries:
        if query[0] == 1:
            l, r = query[1], query[2]
            peak_count = sum(peaks[l + 1:r])
            results.append(peak_count)
        elif query[0] == 2:
            index, value = query[1], query[2]
            nums[index] = value
            for i in range(index - 1, index + 2):
                if 0 < i < len(nums) - 1:
                    peaks[i] = int(nums[i] > nums[i - 1] and nums[i] > nums[i + 1])

    return results

# Example usage
nums = [3, 1, 4, 2, 5]
queries = [[2, 3, 4], [1, 0, 4]]
result = processQueries(nums, queries)
print(result)
import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<Integer> processQueries(int[] nums, int[][] queries) {
        List<Integer> results = new ArrayList<>();
        boolean[] peaks = new boolean[nums.length];

        // Precompute initial peaks
        for (int i = 1; i < nums.length - 1; i++) {
            if (nums[i] > nums[i - 1] && nums[i] > nums[i + 1]) {
                peaks[i] = true;
            }
        }

        for (int[] query : queries) {
            if (query[0] == 1) {
                int l = query[1], r = query[2];
                int peakCount = 0;
                for (int j = l + 1; j < r; j++) {
                    if (peaks[j]) peakCount++;
                }
                results.add(peakCount);
            } else if (query[0] == 2) {
                int index = query[1], value = query[2];
                nums[index] = value;

                for (int i = index - 1; i <= index + 1; i++) {
                    if (i > 0 && i < nums.length - 1) {
                        peaks[i] = (nums[i] > nums[i - 1] && nums[i] > nums[i + 1]);
                    }
                }
            }
        }

        return results;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] nums = {3, 1, 4, 2, 5};
        int[][] queries = {{2, 3, 4}, {1, 0, 4}};
        List<Integer> result = sol.processQueries(nums, queries);
        for (int res : result) {
            System.out.println(res);
        }
    }
}
#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    vector<int> processQueries(vector<int>& nums, vector<vector<int>>& queries) {
        vector<int> results;
        vector<int> peaks(nums.size(), 0);

        // Precompute initial peaks
        for (int i = 1; i < nums.size() - 1; ++i) {
            if (nums[i] > nums[i - 1] && nums[i] > nums[i + 1]) {
                peaks[i] = 1;
            }
        }

        for (auto& query : queries) {
            if (query[0] == 1) {
                int l = query[1], r = query[2], peakCount = 0;
                for (int j = l + 1; j < r; ++j) {
                    peakCount += peaks[j];
                }
                results.push_back(peakCount);
            } else if (query[0] == 2) {
                int index = query[1], value = query[2];
                nums[index] = value;

                for (int i = index - 1; i <= index + 1; ++i) {
                    if (i > 0 && i < nums.size() - 1) {
                        peaks[i] = (nums[i] > nums[i - 1] && nums[i] > nums[i + 1]);
                    }
                }
            }
        }

        return results;
    }
};

int main() {
    Solution sol;
    vector<int> nums = {3, 1, 4, 2, 5};
    vector<vector<int>> queries = {{2, 3, 4}, {1, 0, 4}};
    vector<int> result = sol.processQueries(nums, queries);
    for (int res : result) {
        cout << res << endl;
    }
    return 0;
}
function processQueries(nums, queries) {
    const results = [];
    const peaks = new Array(nums.length).fill(0);

    // Precompute peaks
    for (let i = 1; i < nums.length - 1; i++) {
        if (nums[i] > nums[i - 1] && nums[i] > nums[i + 1]) {
            peaks[i] = 1;
        }
    }

    queries.forEach(query => {
        if (query[0] === 1) {
            const [_, l, r] = query;
            const peakCount = peaks.slice(l + 1, r).reduce((a, b) => a + b, 0);
            results.push(peakCount);
        } else if (query[0] === 2) {
            const [_, index, value] = query;
            nums[index] = value;
            for (let i = index - 1; i <= index + 1; i++) {
                if (i > 0 && i < nums.length - 1) {
                    peaks[i] = (nums[i] > nums[i - 1] && nums[i] > nums[i + 1]) ? 1 : 0;
                }
            }
        }
    });

    return results;
}

// Example usage
const nums = [3, 1, 4, 2, 5];
const queries = [[2, 3, 4], [1, 0, 4]];
const result = processQueries(nums, queries);
console.log(result);
#include <stdio.h>
#include <stdlib.h>

#define MAX_NUMS 100000

int* processQueries(int* nums, int numsSize, int** queries, int queriesSize, int* returnSize) {
    *returnSize = 0;
    int* results = (int*)malloc(queriesSize * sizeof(int));
    int* peaks = (int*)calloc(numsSize, sizeof(int));

    // Precompute peaks
    for (int j = 1; j < numsSize - 1; ++j) {
        if (nums[j] > nums[j - 1] && nums[j] > nums[j + 1]) {
            peaks[j] = 1;
        }
    }

    for (int i = 0; i < queriesSize; ++i) {
        int type = queries[i][0];
        if (type == 1) {
            int l = queries[i][1];
            int r = queries[i][2];
            int peakCount = 0;
            for (int j = l + 1; j < r; ++j) {
                peakCount += peaks[j];
            }
            results[(*returnSize)++] = peakCount;
        } else if (type == 2) {
            int index = queries[i][1];
            int value = queries[i][2];
            // Update potential peaks
            for (int j = index - 1; j <= index + 1; ++j) {
                if (j > 0 && j < numsSize - 1) {
                    peaks[j] = (nums[j] > nums[j - 1] && nums[j] > nums[j + 1]);
                }
            }
            nums[index] = value;
            // Recheck for peak
            for (int j = index - 1; j <= index + 1; ++j) {
                if (j > 0 && j < numsSize - 1) {
                    peaks[j] = (nums[j] > nums[j - 1] && nums[j] > nums[j + 1]);
                }
            }
        }
    }

    free(peaks);
    return results;
}

int main() {
    int nums[] = {3, 1, 4, 2, 5};
    int numsSize = 5;

    int q1[] = {2, 3, 4};
    int q2[] = {1, 0, 4};
    int* queries[] = {q1, q2};
    int queriesSize = 2;

    int returnSize;
    int* result = processQueries(nums, numsSize, queries, queriesSize, &returnSize);

    for (int i = 0; i < returnSize; ++i) {
        printf("%d\n", result[i]);
    }

    free(result);

    return 0;
}
using System;
using System.Collections.Generic;

public class Solution {
    public List<int> ProcessQueries(int[] nums, int[][] queries) {
        List<int> results = new List<int>();
        int[] peaks = new int[nums.Length];

        for (int i = 1; i < nums.Length - 1; i++) {
            if (nums[i] > nums[i - 1] && nums[i] > nums[i + 1]) {
                peaks[i] = 1;
            }
        }

        foreach (var query in queries) {
            if (query[0] == 1) {
                int l = query[1], r = query[2];
                int peakCount = 0;
                for (int i = l + 1; i < r; i++) {
                    peakCount += peaks[i];
                }
                results.Add(peakCount);
            } else if (query[0] == 2) {
                int index = query[1], value = query[2];
                nums[index] = value;

                for (int i = index - 1; i <= index + 1; i++) {
                    if (i > 0 && i < nums.Length - 1) {
                        peaks[i] = (nums[i] > nums[i - 1] && nums[i] > nums[i + 1]) ? 1 : 0;
                    }
                }
            }
        }

        return results;
    }

    public static void Main() {
        var sol = new Solution();
        int[] nums = {3, 1, 4, 2, 5};
        int[][] queries = new int[][] {
            new int[] {2, 3, 4},
            new int[] {1, 0, 4}
        };

        List<int> result = sol.ProcessQueries(nums, queries);
        foreach (int res in result) {
            Console.WriteLine(res);
        }
    }
}

This Python solution employs an array to track peak status, optimizing count queries by summing precomputed boolean values. Changes are dynamically updated, allowing efficient peak verification for type 1 queries.

Complexity

Time Complexity: O(n + Q) for the initial peak checks and each query operation.
Space Complexity: O(n) due to the extra array for peak tracking.

Try this approach in the editor

Approach 3: 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 1s in the interval [l + 1, r - 1]. We can use a binary indexed tree to maintain the number of 1s in the interval [1, n - 1].

For operation 1, i.e., updating nums[idx] to val, it will only affect the values at positions idx - 1, idx, and idx + 1, so we only need to update these three positions. Specifically, we can first remove the peak elements at these three positions, then update the value of nums[idx], and finally add back the peak elements at these three positions.

The time complexity is O((n + q) times log n), and the space complexity is O(n). Here, n and q are the lengths of the array nums and the query array queries, respectively.

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;
}
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
}
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
    }
}
Try this approach in the editor

Complexity comparison

ApproachComplexity
Naive Approach

Time Complexity: O(Q * (r-l)) where Q is the number of queries and (r-l) is the length of the subarray to check for peaks.
Space Complexity: O(1) with possible space for result list.

Efficient Approach with Precomputation

Time Complexity: O(n + Q) for the initial peak checks and each query operation.
Space Complexity: O(n) due to the extra array for peak tracking.

Binary Indexed Tree–

Complexity analysis

ApproachTimeSpaceWhen to Use
Naive ScanO(n) per queryO(1)Small arrays or when the number of queries is very low
Precomputation + Binary Indexed TreeO((n + q) log n)O(n)Best general solution for dynamic updates and frequent range queries
Segment TreeO((n + q) log n)O(n)Useful when the problem expands to more complex range information

Frequently asked questions

Is Peaks in Array easy or hard?

Peaks in Array is classified as a Hard problem because it combines local peak detection with dynamic updates and range queries. Solving it efficiently requires understanding Fenwick Trees or Segment Trees and carefully updating affected indices.

Peaks in Array Python/Java solution

Most implementations build a peak indicator array and maintain it with a Fenwick Tree. Python, Java, C++, and other languages implement the same logic: detect peaks, update neighboring indices after modifications, and query prefix sums for peak counts.

How to solve Peaks in Array in O(n)?

Only the preprocessing step runs in O(n) by scanning the array once to mark peak positions. After that, a Fenwick Tree or Segment Tree is used to handle queries and updates in O(log n). Pure O(n) overall is not possible when dynamic updates and multiple queries are involved.

What is the best approach for Peaks in Array?

The most efficient approach uses a Binary Indexed Tree (Fenwick Tree) to store whether each index is a peak. Range queries become prefix sum queries, and updates only affect indices i-1, i, and i+1. This allows both updates and peak count queries to run in O(log n) time with O(n) extra space.

Is Peaks in Array asked at Google/Amazon/Meta?

Problems involving dynamic range queries and updates using Fenwick Trees or Segment Trees are common in interviews at companies like Google, Amazon, and Meta. Variants that track peaks, valleys, or other local properties frequently appear in advanced coding rounds.

What data structure is used in Peaks in Array?

Binary Indexed Tree (Fenwick Tree) and Segment Tree are the primary data structures. They allow efficient prefix or range sum queries while supporting point updates when the peak status of an index changes.

What is the time complexity of Peaks in Array?

The optimal solution runs in O((n + q) log n) time using a Binary Indexed Tree or Segment Tree. Each query and update takes O(log n), while the initial peak array construction takes O(n). The brute force solution can degrade to O(n * q).

Comments

Now write it yourselfClose this page and solve Peaks in Array in the editor, without looking.
Practise Peaks in Array