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.
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 ); } } }Video 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.