Facebook Pixel

3187. Peaks in Array

HardBinary Indexed TreeSegment TreeArray
Leetcode Link

Problem Description

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 subarray nums[li..ri].

  • queries[i] = [2, indexi, vali], change nums[indexi] to vali.

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.

Intuition

To solve the problem, the key observation is the definition of a peak: a number is a peak if it is greater than both its neighbors. This leads to the approach using a Binary Indexed Tree (or Fenwick Tree) which efficiently supports prefix sum queries and point updates.

Solution Approach

  1. Idea of Peaks Encoding:

    • For any position i where 0 < i < n - 1, if it satisfies nums[i - 1] < nums[i] and nums[i] > nums[i + 1], then nums[i] is considered a peak.
    • Peaks can be encoded as 1 and non-peaks as 0.

  2. Binary Indexed Tree:

    • Use a Binary Indexed Tree to maintain this 1 or 0 encoding. This allows us to efficiently count the number of peaks in any subarray.

  3. Handling Queries:

    • For a query of type [1, li, ri], we need to count the number of peaks in the interval from li + 1 to ri - 1 because peaks can't be at the ends of the subarray.
    • For a query of type [2, indexi, vali], if a change affects peaks, it can only do so at indexi and its two neighbors (indexi - 1 and indexi + 1). Hence, we only update these three positions.

This combination of encoding peaks and using a Binary Indexed Tree provides an efficient solution to handle both types of queries with the required updates and counting.

Learn more about Segment Tree patterns.

Solution Approach

The solution utilizes a Binary Indexed Tree to efficiently handle the problem of counting peaks and managing updates in the array nums. Here is a walk-through of the implementation:

  1. Binary Indexed Tree Setup:

    • A Binary Indexed Tree (BIT) is used to store the peak data. It allows for efficient querying and updating of prefix sums, which is suitable for our need to count peaks in subarrays.
    • The BIT is initialized with a size of n - 1, where n is the length of nums, because the first and last elements cannot be peaks.

  2. Peak Detection and Encoding:

    • For each index i (where 1 <= i < n - 1), check if nums[i-1] < nums[i] > nums[i+1].
    • If nums[i] is a peak, its position is updated with a 1 in the BIT, indicating a peak. Otherwise, it remains 0.

  3. Processing Queries:

    • Type [1, li, ri] Query (Count Peaks):

      • Convert the query range to li + 1 to ri - 1, because peaks cannot be at the boundaries.
      • Use the BIT to compute the sum of 1s in the range [li + 1, ri - 1]. This sum gives the count of peaks.

    • Type [2, indexi, vali] Query (Update):

      • For each index affected by the update (indexi - 1, indexi, indexi + 1):
        • Remove the peak status by updating the BIT with -1 if necessary.
      • Modify nums[indexi] to vali.
      • For the affected indices again, determine if new peaks are formed and update the BIT accordingly with +1 if necessary.

The Binary Indexed Tree provides the structure to achieve logarithmic time complexity for both updating an element and querying a range, making the implementation efficient even for large inputs.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's consider a small example to illustrate the solution approach.

Given:

  • nums = [1, 3, 2, 5, 4]
  • queries = [[1, 1, 3], [2, 1, 4], [1, 0, 4]]

Initial Setup:

  • Initialize a Binary Indexed Tree (BIT) to store peak information. The BIT is sized n-1 since the first and last elements cannot be peaks.
Peaks Detection:

  • For i = 1: nums[0] < nums[1] > nums[2] (1 < 3 > 2); nums[1] is a peak.

  • For i = 2: nums[1] > nums[2] < nums[3]; nums[2] is not a peak.

  • For i = 3: nums[2] < nums[3] > nums[4] (2 < 5 > 4); nums[3] is a peak.

  • Encode this in BIT: BIT = [1, 0, 1].

Processing Queries:

  1. Query [1, 1, 3]:

    • This requires counting peaks in the subarray nums[1..3], checking nums[2] because 1 < i < 3.
    • Check BIT for the range li + 1 to ri - 1 (2 to 2): Result is 0, indicating no peaks.

  2. Query [2, 1, 4]:

    • Update nums[1] from 3 to 4.
    • Check affected indices 0, 1, and 2:
      • No peak at 0.
      • Check if nums[1] (4) forms a peak with neighbors (nums[0] < nums[1] > nums[2]): Yes.
      • Update BIT at index 1 to 1.
    • Now BIT = [1, 1, 1].

  3. Query [1, 0, 4]:

    • Count peaks in the subarray nums[0..4], consider nums[1], nums[2], nums[3].
    • Check BIT for li + 1 to ri - 1 (1 to 3): Result is 2, indicating two peaks at nums[1] and nums[3].

Final Result:

  • For the type [1, li, ri] queries, the answers are [0, 2].
  • Output: [0, 2]

Solution Implementation

1from typing import List
2
3class BinaryIndexedTree:
4    __slots__ = "n", "c"
5
6    def __init__(self, n: int):
7        # Initialize the Binary Indexed Tree (BIT) with zero values
8        self.n = n
9        self.c = [0] * (n + 1)
10
11    def update(self, x: int, delta: int) -> None:
12        # Update the BIT with a given delta at position x
13        while x <= self.n:
14            self.c[x] += delta
15            x += x & -x  # Move to next index in tree
16
17    def query(self, x: int) -> int:
18        # Retrieve the sum from start to position x
19        s = 0
20        while x > 0:
21            s += self.c[x]
22            x -= x & -x  # Move to parent index in tree
23        return s
24
25class Solution:
26    def countOfPeaks(self, nums: List[int], queries: List[List[int]]) -> List[int]:
27        # Function to update the tree regarding peaks
28        def update(i: int, val: int):
29            # Verify index is within valid peak check range
30            if i <= 0 or i >= n - 1:
31                return 
32            # Check if nums[i] is a peak
33            if nums[i - 1] < nums[i] > nums[i + 1]:
34                tree.update(i, val)
35
36        n = len(nums)
37        tree = BinaryIndexedTree(n - 1)
38
39        # Initial update of the tree for all initial peaks
40        for i in range(1, n - 1):
41            update(i, 1)
42
43        ans = []
44        for q in queries:
45            if q[0] == 1:
46                # Query to count number of peaks in a range [l, r]
47                l, r = q[1] + 1, q[2] - 1
48                if l > r:
49                    ans.append(0)  # No range to query
50                else:
51                    ans.append(tree.query(r) - tree.query(l - 1))
52            else:
53                # Query to update nums[idx] with a new value
54                idx, val = q[1], q[2]
55                for i in range(idx - 1, idx + 2):
56                    update(i, -1)  # Remove existing peaks affected by the update
57                nums[idx] = val  # Update the value in nums
58                for i in range(idx - 1, idx + 2):
59                    update(i, 1)  # Add new peaks if formed after the update
60
61        return ans  # Return the results of each query
62
1import java.util.ArrayList;
2import java.util.List;
3
4class BinaryIndexedTree {
5    private int size; // Size of the binary indexed tree
6    private int[] BITree; // Array representation of the binary indexed tree
7
8    public BinaryIndexedTree(int n) {
9        this.size = n;
10        this.BITree = new int[n + 1]; // Initialize with size n+1 for 1-based indexing
11    }
12
13    // Update function to add 'delta' to index 'x'
14    public void update(int x, int delta) {
15        for (; x <= size; x += x & -x) {
16            BITree[x] += delta;
17        }
18    }
19
20    // Query function to get sum from index 1 to 'x'
21    public int query(int x) {
22        int sum = 0;
23        for (; x > 0; x -= x & -x) {
24            sum += BITree[x];
25        }
26        return sum;
27    }
28}
29
30class Solution {
31    private BinaryIndexedTree tree; // Binary Indexed Tree for managing peaks
32    private int[] nums; // Array to store the numbers
33
34    public List<Integer> countOfPeaks(int[] nums, int[][] queries) {
35        int n = nums.length;
36        this.nums = nums;
37        tree = new BinaryIndexedTree(n - 1); // Initialize BIT with size n-1
38
39        // Pre-process: update BIT for existing peaks
40        for (int i = 1; i < n - 1; ++i) {
41            update(i, 1);
42        }
43
44        List<Integer> result = new ArrayList<>(); // List to store results of each query
45
46        // Process each query
47        for (var q : queries) {
48            if (q[0] == 1) {
49                // Range query to count peaks between (q[1], q[2])
50                int left = q[1] + 1;
51                int right = q[2] - 1;
52                result.add(left > right ? 0 : tree.query(right) - tree.query(left - 1));
53            } else {
54                // Update query to modify the value at index q[1] to q[2]
55                int index = q[1];
56                int newValue = q[2];
57
58                // Remove existing peaks in the vicinity of index
59                for (int i = index - 1; i <= index + 1; ++i) {
60                    update(i, -1);
61                }
62
63                // Update the array with the new value
64                nums[index] = newValue;
65
66                // Re-evaluate peaks in the vicinity of index
67                for (int i = index - 1; i <= index + 1; ++i) {
68                    update(i, 1);
69                }
70            }
71        }
72
73        return result;
74    }
75
76    // Helper function to update peaks at index 'i'
77    private void update(int i, int val) {
78        // Ensure 'i' is a valid index for peak evaluation
79        if (i <= 0 || i >= nums.length - 1) {
80            return;
81        }
82
83        // Check if nums[i] is a peak
84        if (nums[i - 1] < nums[i] && nums[i] > nums[i + 1]) {
85            tree.update(i, val); // Update BIT if current index is a peak
86        }
87    }
88}
89
1#include <vector>
2using namespace std;
3
4// BinaryIndexedTree class represents a Fenwick Tree or Binary Indexed Tree
5class BinaryIndexedTree {
6private:
7    int n; // size of the tree
8    vector<int> c; // internal array to hold information
9
10public:
11    // Constructor initializes the tree with given size
12    BinaryIndexedTree(int n)
13        : n(n), c(n + 1) {}
14
15    // Update: Add 'delta' to the position 'x' in the tree
16    void update(int x, int delta) {
17        for (; x <= n; x += x & -x) {
18            c[x] += delta;
19        }
20    }
21
22    // Query: Return the sum of elements up to position 'x'
23    int query(int x) {
24        int sum = 0;
25        for (; x > 0; x -= x & -x) {
26            sum += c[x];
27        }
28        return sum;
29    }
30};
31
32// Solution class to handle the problem
33class Solution {
34public:
35    vector<int> countOfPeaks(vector<int>& nums, vector<vector<int>>& queries) {
36        int n = nums.size();
37
38        // Initialize the Binary Indexed Tree for peaks
39        BinaryIndexedTree tree(n - 1);
40
41        // Lambda function to update the peak condition
42        auto update = [&](int i, int val) {
43            if (i <= 0 || i >= n - 1) {
44                return;
45            }
46            if (nums[i - 1] < nums[i] && nums[i] > nums[i + 1]) {
47                tree.update(i, val);
48            }
49        };
50
51        // Check initial peaks
52        for (int i = 1; i < n - 1; ++i) {
53            update(i, 1);
54        }
55
56        vector<int> ans; // Result vector
57
58        // Process each query
59        for (auto& q : queries) {
60            if (q[0] == 1) {
61                // Range query: count peaks between q[1] and q[2]
62                int l = q[1] + 1, r = q[2] - 1;
63                ans.push_back(l > r ? 0 : tree.query(r) - tree.query(l - 1));
64            } else {
65                // Update query: change element at q[1] to q[2]
66                int idx = q[1], val = q[2];
67
68                // Remove previous peak status in the affected range
69                for (int i = idx - 1; i <= idx + 1; ++i) {
70                    update(i, -1);
71                }
72
73                // Update the element in nums
74                nums[idx] = val;
75
76                // Re-evaluate peak status in the affected range
77                for (int i = idx - 1; i <= idx + 1; ++i) {
78                    update(i, 1);
79                }
80            }
81        }
82
83        return ans; // Return the results for the queries
84    }
85};
86
1// Define the Binary Indexed Tree data structure with relevant operations
2let n: number; // The size of the array
3let c: number[]; // The Binary Indexed Tree array
4
5// Initializes the Binary Indexed Tree with size `n`
6function initializeBinaryIndexedTree(size: number): void {
7    n = size;
8    c = Array(n + 1).fill(0);
9}
10
11// Updates the Binary Indexed Tree at position `x` with `delta` value
12function update(x: number, delta: number): void {
13    // Increment values in tree upwards by the lowest set bit
14    for (; x <= n; x += x & -x) {
15        c[x] += delta;
16    }
17}
18
19// Queries the sum of values up to position `x`
20function query(x: number): number {
21    let sum = 0;
22    // Accumulate sums downwards by the lowest set bit
23    for (; x > 0; x -= x & -x) {
24        sum += c[x];
25    }
26    return sum;
27}
28
29// Function to calculate the number of peaks after each query
30function countOfPeaks(nums: number[], queries: number[][]): number[] {
31    const length = nums.length; // Length of the nums array
32    initializeBinaryIndexedTree(length - 1); // Initialize BIT with size n-1
33
34    // Update peak status for position `i` based on changes
35    function updatePeaks(i: number, val: number): void {
36        if (i <= 0 || i >= length - 1) {
37            return; // Only update peaks if within valid bounds
38        }
39        // Check if `i` is a peak
40        if (nums[i - 1] < nums[i] && nums[i] > nums[i + 1]) {
41            update(i, val); // Update the BIT if `i` is a peak
42        }
43    }
44
45    // Initialize peaks in the given array
46    for (let i = 1; i < length - 1; ++i) {
47        updatePeaks(i, 1); // Add each existing peak to the BIT
48    }
49
50    const results: number[] = []; // Stores results of each query
51
52    // Process each query
53    for (const query of queries) {
54        if (query[0] === 1) {
55            // Type 1: Query total peaks in a range
56            const [left, right] = [query[1] + 1, query[2] - 1];
57            const peakCount = left > right ? 0 : query(right) - query(left - 1);
58            results.push(peakCount); // Calculate and store the number of peaks
59        } else {
60            // Type 2: Update the `nums` array at a specific index
61            const [index, value] = [query[1], query[2]];
62            // Remove possible peaks around index
63            for (let i = index - 1; i <= index + 1; ++i) {
64                updatePeaks(i, -1);
65            }
66            nums[index] = value; // Update the value in the array
67            // Recalculate possible peaks around index
68            for (let i = index - 1; i <= index + 1; ++i) {
69                updatePeaks(i, 1);
70            }
71        }
72    }
73
74    return results; // Return the accumulated results
75}
76

Time and Space Complexity

The time complexity of the code is O((n + q) \times \log n). This is because updating the Binary Indexed Tree (BIT) takes O(\log n) time, and there are n - 2 initial updates for potential peaks in the array nums. Each query also takes O(\log n) time due to either the query or update operations on the BIT, and since there are q queries, this results in a complexity of O(q \times \log n) for handling the queries. Combined with the initial O(n \times \log n) updates, the total complexity becomes O((n + q) \times \log n).

The space complexity is O(n), as the Binary Indexed Tree requires an array of size n + 1 to store the cumulative frequencies, where n is the length of the array nums.

Learn more about how to find time and space complexity quickly.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

Is the following code DFS or BFS?

void search(Node root) {
  if (!root) return;
  visit(root);
  root.visited = true;
  for (Node node in root.adjacent) {
    if (!node.visited) {
      search(node);
    }
  }
}

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 algomonster s3 us east 2 amazonaws com recursion jpg You first

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More