Skip to main content
Talentd

Peaks in Array - Solution & Explanation

HardArrayBinary Indexed TreeSegment Tree29 min readAsked at: Siemens
Practice this problem

Problem Statement

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.

This C solution uses a simple for loop to scan through each query and handle them based on their type. For type 1 queries, it sequentially checks whether the middle elements of the specified range are peaks. For type 2 queries, it updates the array directly. The results from type 1 queries are stored and returned.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

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) for in-place modification of the array.

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.

This optimized C solution precomputes peaks on initialization using a flag array. Each modification in a type 2 query checks, and when necessary, updates peak status for neighboring indices. This allows quick peak tallying during type 1 queries.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n + Q) due to initial peak precomputation and constant time operations during each query.
Space Complexity: O(n) for storing the peak status flags.

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.

Code

PythonJavaC++GoTypeScriptRustJavaScript

Python

Java

C++

Go

TypeScript

Rust

JavaScript

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) for in-place modification of the array.

Efficient Approach with Precomputation

Time Complexity: O(n + Q) due to initial peak precomputation and constant time operations during each query.
Space Complexity: O(n) for storing the peak status flags.

Binary Indexed Tree—

Detailed 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

Video Solution

3187. Peaks in Array | Segment Tree | Range Sum | 2 Line Change in Template | Fenwick Tree • Aryan Mittal • 3,338 views views

Watch 7 more video solutions →

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).

Ready to solve this problem?

Practice Peaks in Array with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays