3187. Peaks in Array
Problem Description
You are given an integer array nums
and need to identify peaks in it. A peak is an element that is strictly greater than both its previous and next elements.
You need to process a list of queries
, where each query can be one of two types:
-
Type 1 Query
[1, l, r]
: Count how many peaks exist in the subarraynums[l..r]
(inclusive). -
Type 2 Query
[2, index, val]
: Update the element at positionindex
to valueval
, i.e., setnums[index] = val
.
Important constraints:
- The first element (
nums[0]
) and last element (nums[n-1]
) of the array can never be considered peaks - Similarly, within any subarray query, the first and last elements of that subarray cannot be peaks
Your task is to return an array containing the results of all Type 1 queries in the order they appear.
Example of a peak:
If nums = [1, 3, 2, 5, 4]
, then:
nums[1] = 3
is a peak because1 < 3 > 2
nums[3] = 5
is a peak because2 < 5 > 4
The solution uses a Binary Indexed Tree (Fenwick Tree) to efficiently track which positions are peaks. When an element is updated (Type 2 query), it only affects the peak status of at most three positions: the updated position itself and its two neighbors. This allows for efficient updates and range queries.
Intuition
The key insight is to transform the peak detection problem into a binary problem. Instead of storing the actual array values, we can think of each position as either being a peak (1) or not a peak (0). This transforms our problem into:
- Type 1 queries become: "Count the number of 1s in a given range"
- Type 2 queries become: "Update a value and recalculate which positions are 1s or 0s"
For range sum queries with updates, a Binary Indexed Tree (Fenwick Tree) is a natural choice as it provides O(log n)
time complexity for both operations.
The clever observation is that when we update a single element at position idx
, it doesn't affect the entire array's peak status. A value change at position idx
can only affect the peak status of:
- Position
idx - 1
(because its right neighbor changed) - Position
idx
itself (because its value changed) - Position
idx + 1
(because its left neighbor changed)
This locality of impact makes the update operation efficient. Instead of rechecking the entire array, we only need to:
- Remove the contribution of these three positions (set them to 0 in our BIT)
- Update the actual value in the array
- Recheck these three positions to see if they're peaks and add them back if needed
For range queries [l, r]
, since the first and last elements of a subarray cannot be peaks, we actually query the range [l+1, r-1]
. The Binary Indexed Tree efficiently gives us the sum (count of peaks) in this adjusted range.
This approach elegantly combines the binary representation of peaks with the efficiency of Binary Indexed Trees to handle both query types in O(log n)
time per operation.
Learn more about Segment Tree patterns.
Solution Approach
The solution uses a Binary Indexed Tree (Fenwick Tree) to efficiently track and query peak elements in the array.
Binary Indexed Tree Implementation
The BinaryIndexedTree
class maintains an array c
of size n+1
where:
update(x, delta)
: Addsdelta
to positionx
inO(log n)
timequery(x)
: Returns the prefix sum from position 1 tox
inO(log n)
time
Main Solution Logic
-
Initialization:
- Create a BIT of size
n-1
(since first and last elements can't be peaks) - Iterate through positions
[1, n-2]
and mark each peak position with value 1 in the BIT
- Create a BIT of size
-
Helper Function
update(i, val)
:- Checks if position
i
is valid (not first or last element) - If
nums[i-1] < nums[i] > nums[i+1]
, updates the BIT at positioni
with valueval
- Checks if position
-
Processing Queries:
Type 1 Query
[1, l, r]
- Count peaks in subarray:- Adjust range to
[l+1, r-1]
since endpoints can't be peaks - If
l+1 > r-1
, return 0 (no valid range) - Otherwise, compute
tree.query(r-1) - tree.query(l)
to get the count of 1s in the range
Type 2 Query
[2, idx, val]
- Update element:- Remove affected peaks: For positions
[idx-1, idx, idx+1]
, callupdate(i, -1)
to remove their current peak status from the BIT - Update the array: Set
nums[idx] = val
- Recalculate peaks: For the same three positions, call
update(i, 1)
to add back any positions that are now peaks
- Adjust range to
Time Complexity
- Initialization:
O(n log n)
to build the BIT - Type 1 Query:
O(log n)
for range sum query - Type 2 Query:
O(log n)
for updating at most 3 positions
Space Complexity
O(n)
for the Binary Indexed Tree
The elegance of this solution lies in treating peaks as binary values (1 for peak, 0 for non-peak) and using the BIT's efficient range sum capabilities to count peaks, while leveraging the local nature of updates to maintain the structure efficiently.
Ready to land your dream job?
Unlock your dream job with a 5-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through a concrete example to illustrate how the solution works.
Initial Setup:
nums = [1, 3, 2, 5, 4]
queries = [[1, 0, 4], [2, 3, 6], [1, 0, 4]]
Step 1: Initialize the Binary Indexed Tree
First, identify which positions are peaks:
- Position 0: Cannot be a peak (first element)
- Position 1: Is
1 < 3 > 2
? Yes! → Peak - Position 2: Is
3 < 2 > 5
? No - Position 3: Is
2 < 5 > 4
? Yes! → Peak - Position 4: Cannot be a peak (last element)
Create BIT with size 4 (n-1) and mark peaks:
- BIT position 1 (array index 1): Set to 1
- BIT position 2 (array index 2): Set to 0
- BIT position 3 (array index 3): Set to 1
BIT state: [0, 1, 0, 1]
(representing peaks at positions 1 and 3)
Step 2: Process Query [1, 0, 4] - Count peaks in nums[0..4]
Adjust range for peak counting: [0+1, 4-1]
= [1, 3]
- Calculate:
tree.query(3) - tree.query(0)
tree.query(3)
= sum of positions 1 to 3 = 1 + 0 + 1 = 2tree.query(0)
= 0- Result: 2 peaks
Step 3: Process Query [2, 3, 6] - Update nums[3] to 6
Before update: nums = [1, 3, 2, 5, 4]
Remove affected peaks (positions 2, 3, 4):
- Position 2: Not currently a peak, no change
- Position 3: Currently a peak, remove it (BIT update position 3 with -1)
- Position 4: Cannot be a peak (last element)
Update array: nums[3] = 6
→ nums = [1, 3, 2, 6, 4]
Recalculate affected positions:
- Position 2: Is
3 < 2 > 6
? No, still not a peak - Position 3: Is
2 < 6 > 4
? Yes! Add it back (BIT update position 3 with +1) - Position 4: Still cannot be a peak
BIT state remains: [0, 1, 0, 1]
Step 4: Process Query [1, 0, 4] - Count peaks again
Adjust range: [0+1, 4-1]
= [1, 3]
- Calculate:
tree.query(3) - tree.query(0)
- Result: 2 peaks (positions 1 and 3 are still peaks)
Final Answer: [2, 2]
The key insight demonstrated here is that the update at position 3 only required checking positions 2, 3, and 4 for their peak status, making the update operation efficient at O(log n) rather than having to recheck the entire array.
Solution Implementation
1from typing import List
2
3
4class BinaryIndexedTree:
5 """Fenwick Tree for efficient range sum queries and point updates."""
6
7 __slots__ = ("size", "tree")
8
9 def __init__(self, size: int) -> None:
10 """
11 Initialize Binary Indexed Tree with given size.
12
13 Args:
14 size: Maximum index that can be stored (1-indexed)
15 """
16 self.size = size
17 self.tree = [0] * (size + 1) # 1-indexed array
18
19 def update(self, index: int, delta: int) -> None:
20 """
21 Add delta to element at given index and update tree.
22
23 Args:
24 index: Position to update (1-indexed)
25 delta: Value to add at the position
26 """
27 while index <= self.size:
28 self.tree[index] += delta
29 # Move to next index affected by this update
30 # Adding the least significant bit moves to parent
31 index += index & -index
32
33 def query(self, index: int) -> int:
34 """
35 Calculate prefix sum from index 1 to given index.
36
37 Args:
38 index: End position for prefix sum (1-indexed)
39
40 Returns:
41 Sum of elements from 1 to index
42 """
43 prefix_sum = 0
44 while index > 0:
45 prefix_sum += self.tree[index]
46 # Move to previous range by removing least significant bit
47 index -= index & -index
48 return prefix_sum
49
50
51class Solution:
52 def countOfPeaks(self, nums: List[int], queries: List[List[int]]) -> List[int]:
53 """
54 Process queries on array to count peaks in ranges or update values.
55 A peak is an element greater than both its neighbors.
56
57 Args:
58 nums: Input array of integers
59 queries: List of queries where:
60 - [1, left, right]: Count peaks in range [left, right]
61 - [2, index, value]: Update nums[index] to value
62
63 Returns:
64 List of results for type 1 queries
65 """
66
67 def update_peak_status(position: int, delta: int) -> None:
68 """
69 Update Binary Indexed Tree if position is a peak.
70
71 Args:
72 position: Index to check for peak status
73 delta: 1 to add peak, -1 to remove peak
74 """
75 # Skip boundary elements (cannot be peaks)
76 if position <= 0 or position >= array_length - 1:
77 return
78
79 # Check if current position is a peak
80 if nums[position - 1] < nums[position] and nums[position] > nums[position + 1]:
81 fenwick_tree.update(position, delta)
82
83 array_length = len(nums)
84 # Initialize BIT to track peaks (excluding first and last elements)
85 fenwick_tree = BinaryIndexedTree(array_length - 1)
86
87 # Initially mark all peaks in the array
88 for i in range(1, array_length - 1):
89 update_peak_status(i, 1)
90
91 results = []
92
93 for query in queries:
94 if query[0] == 1:
95 # Type 1: Count peaks in range query
96 # Adjust range to exclude boundaries (they can't be peaks)
97 left_bound = query[1] + 1
98 right_bound = query[2] - 1
99
100 if left_bound > right_bound:
101 # No valid peaks possible in this range
102 results.append(0)
103 else:
104 # Calculate peaks in range using prefix sums
105 peaks_count = fenwick_tree.query(right_bound) - fenwick_tree.query(left_bound - 1)
106 results.append(peaks_count)
107
108 else:
109 # Type 2: Update value at index
110 update_index, new_value = query[1], query[2]
111
112 # Remove peak status for affected positions before update
113 # Check positions: update_index-1, update_index, update_index+1
114 for i in range(update_index - 1, update_index + 2):
115 update_peak_status(i, -1)
116
117 # Update the value in array
118 nums[update_index] = new_value
119
120 # Re-evaluate peak status for affected positions after update
121 for i in range(update_index - 1, update_index + 2):
122 update_peak_status(i, 1)
123
124 return results
125
1/**
2 * Binary Indexed Tree (Fenwick Tree) for efficient range sum queries and point updates
3 */
4class BinaryIndexedTree {
5 private int size;
6 private int[] tree;
7
8 /**
9 * Initialize Binary Indexed Tree with given size
10 * @param size The size of the array (1-indexed)
11 */
12 public BinaryIndexedTree(int size) {
13 this.size = size;
14 this.tree = new int[size + 1];
15 }
16
17 /**
18 * Update the value at index by adding delta
19 * @param index The 1-based index to update
20 * @param delta The value to add
21 */
22 public void update(int index, int delta) {
23 // Traverse all affected nodes in the tree
24 while (index <= size) {
25 tree[index] += delta;
26 // Move to next node that this index affects
27 // x & -x gives the rightmost set bit
28 index += index & -index;
29 }
30 }
31
32 /**
33 * Query the prefix sum from index 1 to index
34 * @param index The 1-based index to query up to
35 * @return The sum of elements from 1 to index
36 */
37 public int query(int index) {
38 int sum = 0;
39 // Traverse parents to accumulate the sum
40 while (index > 0) {
41 sum += tree[index];
42 // Move to parent node by removing rightmost set bit
43 index -= index & -index;
44 }
45 return sum;
46 }
47}
48
49/**
50 * Solution for counting peaks in array with update and query operations
51 */
52class Solution {
53 private BinaryIndexedTree binaryIndexedTree;
54 private int[] nums;
55
56 /**
57 * Process queries on the array to count peaks or update values
58 * @param nums The input array
59 * @param queries Array of queries where:
60 * - [1, l, r] means count peaks in range [l, r]
61 * - [2, idx, val] means update nums[idx] to val
62 * @return List of results for count queries
63 */
64 public List<Integer> countOfPeaks(int[] nums, int[][] queries) {
65 int n = nums.length;
66 this.nums = nums;
67
68 // Initialize BIT with size n-1 (excluding first and last elements)
69 binaryIndexedTree = new BinaryIndexedTree(n - 1);
70
71 // Initially mark all peaks in the array
72 for (int i = 1; i < n - 1; i++) {
73 updatePeakStatus(i, 1);
74 }
75
76 List<Integer> results = new ArrayList<>();
77
78 // Process each query
79 for (int[] query : queries) {
80 if (query[0] == 1) {
81 // Type 1: Count peaks in range [l, r]
82 int left = query[1] + 1; // Adjust to exclude boundary
83 int right = query[2] - 1; // Adjust to exclude boundary
84
85 // Handle edge case where adjusted range is invalid
86 if (left > right) {
87 results.add(0);
88 } else {
89 // Range sum query using BIT
90 int peakCount = binaryIndexedTree.query(right) - binaryIndexedTree.query(left - 1);
91 results.add(peakCount);
92 }
93 } else {
94 // Type 2: Update value at index
95 int index = query[1];
96 int newValue = query[2];
97
98 // Remove peak status for positions that might be affected
99 for (int i = index - 1; i <= index + 1; i++) {
100 updatePeakStatus(i, -1);
101 }
102
103 // Update the array value
104 nums[index] = newValue;
105
106 // Re-evaluate peak status for affected positions
107 for (int i = index - 1; i <= index + 1; i++) {
108 updatePeakStatus(i, 1);
109 }
110 }
111 }
112
113 return results;
114 }
115
116 /**
117 * Update the peak status of a position in the BIT
118 * @param index The position to check for peak
119 * @param delta The value to update (1 to add peak, -1 to remove peak)
120 */
121 private void updatePeakStatus(int index, int delta) {
122 // Boundary check: peaks can only exist at interior positions
123 if (index <= 0 || index >= nums.length - 1) {
124 return;
125 }
126
127 // Check if position is a peak (greater than both neighbors)
128 if (nums[index - 1] < nums[index] && nums[index] > nums[index + 1]) {
129 binaryIndexedTree.update(index, delta);
130 }
131 }
132}
133
1class BinaryIndexedTree {
2private:
3 int n;
4 vector<int> tree; // Fenwick tree array (1-indexed)
5
6public:
7 // Constructor: Initialize BIT with size n
8 BinaryIndexedTree(int n) : n(n), tree(n + 1) {}
9
10 // Update: Add delta to position x (1-indexed)
11 void update(int x, int delta) {
12 // Traverse all affected nodes in the tree
13 for (; x <= n; x += x & -x) {
14 tree[x] += delta;
15 }
16 }
17
18 // Query: Get prefix sum from 1 to x (1-indexed)
19 int query(int x) {
20 int sum = 0;
21 // Traverse and accumulate values
22 for (; x > 0; x -= x & -x) {
23 sum += tree[x];
24 }
25 return sum;
26 }
27};
28
29class Solution {
30public:
31 vector<int> countOfPeaks(vector<int>& nums, vector<vector<int>>& queries) {
32 int n = nums.size();
33 // BIT to track peak positions (uses 1-indexed positions)
34 BinaryIndexedTree fenwickTree(n - 1);
35
36 // Lambda function to update peak status at position i
37 auto updatePeakStatus = [&](int i, int delta) {
38 // Skip boundary positions (cannot be peaks)
39 if (i <= 0 || i >= n - 1) {
40 return;
41 }
42 // Check if position i is a peak
43 if (nums[i - 1] < nums[i] && nums[i] > nums[i + 1]) {
44 fenwickTree.update(i, delta);
45 }
46 };
47
48 // Initialize: Mark all initial peaks in the array
49 for (int i = 1; i < n - 1; ++i) {
50 updatePeakStatus(i, 1);
51 }
52
53 vector<int> result;
54
55 // Process each query
56 for (auto& query : queries) {
57 if (query[0] == 1) {
58 // Type 1: Count peaks in range [l+1, r-1]
59 int left = query[1] + 1;
60 int right = query[2] - 1;
61
62 // Handle empty range case
63 if (left > right) {
64 result.push_back(0);
65 } else {
66 // Range sum query using prefix sums
67 int peakCount = fenwickTree.query(right) - fenwickTree.query(left - 1);
68 result.push_back(peakCount);
69 }
70 } else {
71 // Type 2: Update value at index and recalculate affected peaks
72 int index = query[1];
73 int newValue = query[2];
74
75 // Remove peaks that might be affected by the update
76 for (int i = index - 1; i <= index + 1; ++i) {
77 updatePeakStatus(i, -1);
78 }
79
80 // Update the value
81 nums[index] = newValue;
82
83 // Re-evaluate and add back peaks after the update
84 for (int i = index - 1; i <= index + 1; ++i) {
85 updatePeakStatus(i, 1);
86 }
87 }
88 }
89
90 return result;
91 }
92};
93
1// Binary Indexed Tree (Fenwick Tree) for efficient range sum queries and point updates
2let n: number;
3let fenwickTree: number[];
4
5/**
6 * Initializes the Fenwick Tree with given size
7 * @param size - The size of the array to track
8 */
9function initializeFenwickTree(size: number): void {
10 n = size;
11 fenwickTree = new Array(size + 1).fill(0);
12}
13
14/**
15 * Updates the Fenwick Tree at position x by adding delta
16 * @param x - The 1-indexed position to update
17 * @param delta - The value to add at position x
18 */
19function update(x: number, delta: number): void {
20 // Traverse all affected nodes in the tree using bit manipulation
21 // x & -x gives the rightmost set bit
22 for (; x <= n; x += x & -x) {
23 fenwickTree[x] += delta;
24 }
25}
26
27/**
28 * Queries the prefix sum from index 1 to x
29 * @param x - The 1-indexed position to query up to
30 * @returns The sum of elements from index 1 to x
31 */
32function query(x: number): number {
33 let sum = 0;
34 // Traverse parent nodes by removing the rightmost set bit
35 for (; x > 0; x -= x & -x) {
36 sum += fenwickTree[x];
37 }
38 return sum;
39}
40
41/**
42 * Updates the peak status at index i in the Fenwick Tree
43 * @param nums - The array of numbers
44 * @param i - The index to check for peak
45 * @param val - The value to add (1) or remove (-1) if it's a peak
46 */
47function updatePeakStatus(nums: number[], i: number, val: number): void {
48 const arrayLength = nums.length;
49
50 // Skip boundary elements as they cannot be peaks
51 if (i <= 0 || i >= arrayLength - 1) {
52 return;
53 }
54
55 // Check if element at index i is a peak (greater than both neighbors)
56 if (nums[i - 1] < nums[i] && nums[i] > nums[i + 1]) {
57 update(i, val);
58 }
59}
60
61/**
62 * Counts peaks in subarrays and handles updates based on queries
63 * @param nums - The input array of numbers
64 * @param queries - Array of queries where:
65 * [1, l, r] means count peaks in subarray from l to r
66 * [2, idx, val] means update nums[idx] to val
67 * @returns Array of results for type 1 queries
68 */
69function countOfPeaks(nums: number[], queries: number[][]): number[] {
70 const arrayLength = nums.length;
71
72 // Initialize Fenwick Tree with size for valid peak positions
73 initializeFenwickTree(arrayLength - 1);
74
75 // Initial scan: mark all peaks in the array
76 for (let i = 1; i < arrayLength - 1; i++) {
77 updatePeakStatus(nums, i, 1);
78 }
79
80 const results: number[] = [];
81
82 // Process each query
83 for (const currentQuery of queries) {
84 if (currentQuery[0] === 1) {
85 // Type 1: Count peaks in range [l, r]
86 // Adjust indices to exclude boundaries (they can't be peaks)
87 const leftBound = currentQuery[1] + 1;
88 const rightBound = currentQuery[2] - 1;
89
90 // If invalid range, no peaks possible
91 if (leftBound > rightBound) {
92 results.push(0);
93 } else {
94 // Range sum query using Fenwick Tree
95 results.push(query(rightBound) - query(leftBound - 1));
96 }
97 } else {
98 // Type 2: Update value at index
99 const indexToUpdate = currentQuery[1];
100 const newValue = currentQuery[2];
101
102 // Remove peak status for affected positions (current and neighbors)
103 for (let i = indexToUpdate - 1; i <= indexToUpdate + 1; i++) {
104 updatePeakStatus(nums, i, -1);
105 }
106
107 // Update the value in the array
108 nums[indexToUpdate] = newValue;
109
110 // Re-evaluate peak status for affected positions
111 for (let i = indexToUpdate - 1; i <= indexToUpdate + 1; i++) {
112 updatePeakStatus(nums, i, 1);
113 }
114 }
115 }
116
117 return results;
118}
119
Time and Space Complexity
Time Complexity: O((n + q) × log n)
The time complexity breaks down as follows:
- Initialization of BinaryIndexedTree: Creating the tree takes
O(n)
time to allocate the array. - Initial peak detection: The loop from
1
ton-1
callsupdate(i, 1)
for each position. Eachupdate
call to the tree takesO(log n)
time due to the Binary Indexed Tree operations. This gives usO(n × log n)
for initialization. - Processing queries: For each of the
q
queries:- Type 1 queries (range query): Calls
tree.query()
twice, each takingO(log n)
time. - Type 2 queries (update):
- Calls
update(i, -1)
for up to 3 positions (fromidx-1
toidx+1
), each potentially callingtree.update()
which takesO(log n)
. - Updates the value in
nums
. - Calls
update(i, 1)
for up to 3 positions again, each potentially callingtree.update()
which takesO(log n)
. - Total per Type 2 query:
O(log n)
- Calls
- Overall for all queries:
O(q × log n)
- Type 1 queries (range query): Calls
- Total time complexity:
O(n × log n) + O(q × log n) = O((n + q) × log n)
Space Complexity: O(n)
The space complexity consists of:
- BinaryIndexedTree storage: The array
c
of sizen+1
requiresO(n)
space. - Answer array: Stores at most
q
results, but this is typically not counted as part of auxiliary space since it's the output. - Other variables: Constant space for loop variables and temporary values.
- Total space complexity:
O(n)
Learn more about how to find time and space complexity quickly.
Common Pitfalls
1. Off-by-One Errors in BIT Indexing
The Binary Indexed Tree uses 1-based indexing while the original array uses 0-based indexing. This creates multiple opportunities for indexing errors:
Pitfall Example:
# WRONG: Directly using array index for BIT fenwick_tree.update(i, 1) # i is 0-based array index # CORRECT: BIT expects 1-based index for internal positions fenwick_tree.update(i, 1) # where i is already adjusted (1 to n-2)
Solution: The code correctly handles this by:
- Creating a BIT of size
n-1
(excluding first and last elements) - Using positions 1 through n-2 in the BIT to represent array indices 1 through n-2
- In range queries, using
query(right_bound) - query(left_bound - 1)
with proper adjustments
2. Incorrect Range Adjustment for Peak Queries
When querying peaks in range [l, r], the endpoints cannot be peaks, so the actual searchable range is [l+1, r-1].
Pitfall Example:
# WRONG: Querying the full range if query[0] == 1: left, right = query[1], query[2] count = fenwick_tree.query(right) - fenwick_tree.query(left - 1) # CORRECT: Adjust range to exclude boundaries if query[0] == 1: left_bound = query[1] + 1 right_bound = query[2] - 1 if left_bound > right_bound: results.append(0) else: count = fenwick_tree.query(right_bound) - fenwick_tree.query(left_bound - 1)
3. Incomplete Update of Affected Peaks
When updating an element, it affects the peak status of three positions: the updated position and its two neighbors. Forgetting to update all three positions is a common mistake.
Pitfall Example:
# WRONG: Only updating the changed position
update_peak_status(update_index, -1)
nums[update_index] = new_value
update_peak_status(update_index, 1)
# CORRECT: Update all affected positions
for i in range(update_index - 1, update_index + 2):
update_peak_status(i, -1)
nums[update_index] = new_value
for i in range(update_index - 1, update_index + 2):
update_peak_status(i, 1)
4. Not Removing Old Peak Status Before Updates
Failing to remove the old peak status before recalculating can lead to double-counting peaks in the BIT.
Pitfall Example:
# WRONG: Directly adding new peak status without removing old
nums[update_index] = new_value
for i in range(update_index - 1, update_index + 2):
if is_peak(i):
fenwick_tree.update(i, 1) # May double-count if already a peak
# CORRECT: Remove old status first, then add new
for i in range(update_index - 1, update_index + 2):
update_peak_status(i, -1) # Remove old status
nums[update_index] = new_value
for i in range(update_index - 1, update_index + 2):
update_peak_status(i, 1) # Add new status if peak
5. Boundary Check Failures in Peak Detection
The update_peak_status
function must verify that a position is not at the array boundaries before checking peak conditions.
Pitfall Example:
# WRONG: Checking peak condition without boundary validation
def update_peak_status(position: int, delta: int) -> None:
if nums[position - 1] < nums[position] > nums[position + 1]: # IndexError!
fenwick_tree.update(position, delta)
# CORRECT: Check boundaries first
def update_peak_status(position: int, delta: int) -> None:
if position <= 0 or position >= array_length - 1:
return
if nums[position - 1] < nums[position] and nums[position] > nums[position + 1]:
fenwick_tree.update(position, delta)
These pitfalls highlight the importance of careful index management, proper range adjustments, and complete handling of all affected positions during updates when working with Binary Indexed Trees and peak detection algorithms.
In a binary min heap, the minimum element can be found in:
Recommended Readings
Segment Tree Faster Range Queries For this article we want to introduce the idea of a Segment Tree Segment Trees allow us to quickly perform range queries as well as range updates Suppose we have an array and we want to know the sum of a particular range of numbers as well
Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https assets algo monster recursion jpg You first call Ben and ask
Want a Structured Path to Master System Design Too? Don’t Miss This!