Peaks in Array
HardPrompt
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 subarraynums[li..ri].queries[i] = [2, indexi, vali], changenums[indexi]tovali.
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 <= 1051 <= nums[i] <= 1051 <= queries.length <= 105queries[i][0] == 1orqueries[i][0] == 2- For all
ithat:queries[i][0] == 1:0 <= queries[i][1] <= queries[i][2] <= nums.length - 1queries[i][0] == 2:0 <= queries[i][1] <= nums.length - 1,1 <= queries[i][2] <= 105
Approaches
2 approaches with complexity analysis and trade-offs.
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.
Algorithm
- Initialize an empty list
answerto store results for type 1 queries. - Iterate through each
queryin thequeriesarray. - If the query is of type 1,
[1, l, r]:- Initialize a counter
peak_countto 0. - Iterate with an index
ifroml + 1tor - 1. - Inside the loop, check if
nums[i]is a peak by comparing it with its neighbors:nums[i] > nums[i-1]andnums[i] > nums[i+1]. - If it is a peak, increment
peak_count. - After the loop, add
peak_countto theanswerlist.
- Initialize a counter
- If the query is of type 2,
[2, index, val]:- Directly update the array:
nums[index] = val.
- Directly update the array:
- After processing all queries, return the
answerlist.
Walkthrough
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.
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; }}Complexity
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).
Trade-offs
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.
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.
Algorithm
- Define a helper function
isPeak(nums, i, n)that returnstrueifnums[i]is a peak, considering array boundaries. - Initialization:
- Create a Fenwick Tree (BIT) data structure of size
N. - Iterate from
i = 1toN-2. IfisPeak(nums, i, N)is true, update the BIT at indexiby 1:bit.update(i, 1).
- Create a Fenwick Tree (BIT) data structure of size
- Processing Queries:
- Initialize an empty list
answer. - For each
queryinqueries:- If it's a type 1 query
[1, l, r]:- If
r - l < 2, no peaks are possible, so add 0 toanswer. - Otherwise, the number of peaks is the sum in the range
[l+1, r-1]. This is computed using the BIT asbit.query(r-1) - bit.query(l). Add this count toanswer.
- If
- If it's a type 2 query
[2, index, val]:- Identify the indices whose peak status could change:
index-1,index, andindex+1. - For each of these potentially affected indices
i(within[1, N-2]):- Check if
iwas a peak before the update. If yes, decrement the count in the BIT:bit.update(i, -1).
- Check if
- Perform the update:
nums[index] = val. - For the same affected indices
i:- Check if
iis a peak after the update. If yes, increment the count in the BIT:bit.update(i, 1).
- Check if
- Identify the indices whose peak status could change:
- If it's a type 1 query
- Initialize an empty list
- Return the
answerlist.
Walkthrough
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.
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; }}Complexity
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.
Trade-offs
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.
Solutions
Solution
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 ); } } }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 ; } };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 ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.