How do you solve Peaks in Array on LeetCode?

Peaks in Array (LeetCode #3187) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n + q) time complexity and O(n) space complexity. Key insight: Updating an element only affects its immediate neighbors in terms of peak status.

What is the brute force solution for Peaks in Array?

The brute force approach for Peaks in Array is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach checks each element in the specified range to see if it is a peak. This is straightforward but inefficient for large arrays. The optimal Optimal Solution approach improves this to O(n + q).

What algorithm or data structure is used to solve Peaks in Array?

Peaks in Array uses the following concepts: Array, Binary Indexed Tree, Segment Tree. The recommended patterns to study are: Array, Dynamic Programming.

What are the interview tips for Peaks in Array?

Always clarify how updates will affect the data structure. Think about preprocessing data to speed up queries. Discuss time and space complexity openly with the interviewer.

What are common mistakes when solving Peaks in Array?

Not considering the boundaries when checking for peaks. Failing to update the peak status correctly after an update.

#3187

Peaks in Array

Hard

ArrayBinary Indexed TreeSegment TreeArrayDynamic Programming

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n + q)
Space	O(1)	O(n)

💡

Intuition

Time O(n + q)Space O(n)

The optimal solution leverages the fact that updating an element only affects its neighboring peaks. We maintain a peak status array and update it in constant time when changes occur.

⚙️

Algorithm

3 steps

1Step 1: Create a boolean array to track peaks in the original nums array.
2Step 2: For each query of type [1, l, r], count the peaks in the specified range using the peak status array.
3Step 3: For each query of type [2, index, val], update nums[index] and adjust the peak status of nums[index-1], nums[index], and nums[index+1] accordingly.

solution.py18 lines

1def count_peaks(nums, queries):
2    n = len(nums)
3    peaks = [0] * n
4    for i in range(1, n - 1):
5        peaks[i] = nums[i] > nums[i - 1] and nums[i] > nums[i + 1]
6    results = []
7    for query in queries:
8        if query[0] == 1:
9            l, r = query[1], query[2]
10            count = sum(peaks[l + 1:r])
11            results.append(count)
12        elif query[0] == 2:
13            index, val = query[1], query[2]
14            nums[index] = val
15            for i in [index - 1, index, index + 1]:
16                if 0 < i < n - 1:
17                    peaks[i] = nums[i] > nums[i - 1] and nums[i] > nums[i + 1]
18    return results

ℹ

Complexity note: The time complexity is O(n + q) where n is the length of the array and q is the number of queries. This is because we preprocess the peaks in O(n) and handle each query in O(1) for updates and O(n) for counting peaks.

1Updating an element only affects its immediate neighbors in terms of peak status.
2Precomputing peak status allows for efficient querying.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.