Facebook Pixel

3187. Peaks in Array

HardBinary Indexed TreeSegment TreeArray
Leetcode Link

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:

  1. Type 1 Query [1, l, r]: Count how many peaks exist in the subarray nums[l..r] (inclusive).

  2. Type 2 Query [2, index, val]: Update the element at position index to value val, i.e., set nums[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 because 1 < 3 > 2
  • nums[3] = 5 is a peak because 2 < 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.

Quick Interview Experience
Help others by sharing your interview experience
Have you seen this problem before?

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:

  1. Position idx - 1 (because its right neighbor changed)
  2. Position idx itself (because its value changed)
  3. 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:

  1. Remove the contribution of these three positions (set them to 0 in our BIT)
  2. Update the actual value in the array
  3. 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): Adds delta to position x in O(log n) time
  • query(x): Returns the prefix sum from position 1 to x in O(log n) time

Main Solution Logic

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

  2. 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 position i with value val

  3. 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], call update(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

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 Evaluator

Example 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 = 2
  • tree.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 to n-1 calls update(i, 1) for each position. Each update call to the tree takes O(log n) time due to the Binary Indexed Tree operations. This gives us O(n × log n) for initialization.
  • Processing queries: For each of the q queries:
    • Type 1 queries (range query): Calls tree.query() twice, each taking O(log n) time.
    • Type 2 queries (update):
      • Calls update(i, -1) for up to 3 positions (from idx-1 to idx+1), each potentially calling tree.update() which takes O(log n).
      • Updates the value in nums.
      • Calls update(i, 1) for up to 3 positions again, each potentially calling tree.update() which takes O(log n).
      • Total per Type 2 query: O(log n)
    • Overall for all queries: O(q × log n)
  • 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 size n+1 requires O(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.

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan:

Which of these properties could exist for a graph but not a tree?

Recommended Readings

Segment Tree

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: The Smart, Data-Driven Way to Prepare for Tech Interviews

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 Review

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!

Load More