We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Peaks in Array

Number: 3438

Difficulty: Hard

Paid? No

Companies: Siemens

Problem Description

Given an integer array nums and a list of queries, implement a data structure that can efficiently answer two types of queries:

  1. Count the number of "peak" elements in a specified subarray. An element at index i in nums is a peak if it is strictly greater than both its previous and next elements (note that the first and last elements of any subarray cannot be peaks).
  2. Update the value at a specified index in nums.

For a subarray query [l, r], only indices in the range (l, r) (i.e. from l+1 to r-1) can be peaks.

Key Insights

  • Precompute a helper array peaks where peaks[i] = 1 if nums[i] is a peak (and 0 otherwise) for indices 1 to n-2.
  • Use a Binary Indexed Tree (BIT) / Segment Tree to support efficient range sum queries and point updates on the peaks array.
  • Note that an update to nums may affect the peak status of at most three indices: index-1, index, and index+1. Recompute these affected indices after any update.
  • During a subarray peak count query [l, r], exclude the boundary indices (l and r) and sum over the range [l+1, r-1] in the BIT.

Space and Time Complexity

Time Complexity:

  • Preprocessing the peaks array: O(n)
  • Each query (update or peak count) runs in O(log n) time due to BIT operations. Space Complexity:
  • O(n) for storing the peaks array and BIT.

Solution

The solution leverages a Binary Indexed Tree (BIT) to maintain the count of peak elements dynamically while supporting updates. The steps are as follows:

  1. Initialize a helper array called peaks such that peaks[i] is 1 if nums[i] > nums[i-1] and nums[i] > nums[i+1], for indices from 1 to n-2; otherwise, peaks[i] is 0.
  2. Build a BIT over this peaks array. The BIT supports efficient point updates and range sum queries.
  3. For a type 1 query ([1, l, r]), compute the sum of peaks in the range from l+1 to r-1 using the BIT (if r-l is less than 2, then answer is 0).
  4. For a type 2 query ([2, index, val]), update the value at nums[index]. Then for each index in {index-1, index, index+1} (ensuring they are valid for peak checks), recompute the peak condition and update the BIT with the difference relative to its old state.
  5. Return the results for all subarray queries in order.

Code Solutions

Below are code implementations in Python, JavaScript, C++, and Java with inline comments.

class BIT:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
    
    def update(self, index, delta):
        # BIT indices are 1-indexed
        i = index + 1
        while i <= self.size:
            self.tree[i] += delta
            i += i & -i

    def query(self, index):
        # returns the prefix sum from 0 to index
        res = 0
        i = index + 1
        while i > 0:
            res += self.tree[i]
            i -= i & -i
        return res

    def range_query(self, left, right):
        if left > right:
            return 0
        return self.query(right) - self.query(left - 1)

def is_peak(nums, i):
    # Check if index i is a peak; valid i are 1 <= i <= len(nums)-2
    return nums[i] > nums[i - 1] and nums[i] > nums[i + 1]

def processQueries(nums, queries):
    n = len(nums)
    # Build initial peaks array
    peaks = [0] * n
    for i in range(1, n - 1):
        peaks[i] = 1 if is_peak(nums, i) else 0

    # Build BIT using peaks array
    bit = BIT(n)
    for i in range(n):
        if peaks[i]:
            bit.update(i, peaks[i])
    
    result = []
    
    for query in queries:
        if query[0] == 1:
            # Query type 1: Count peaks in subarray [l, r]
            l, r = query[1], query[2]
            # If subarray length < 3, no valid peaks exist
            if r - l < 2:
                result.append(0)
            else:
                # Count peaks only in indices l+1 to r-1
                count = bit.range_query(l + 1, r - 1)
                result.append(count)
        else:  # query[0] == 2 - update query
            index, new_val = query[1], query[2]
            nums[index] = new_val
            # For indices that might be affected: index-1, index, index+1
            for i in [index - 1, index, index + 1]:
                if 1 <= i < n - 1:
                    new_peak = 1 if is_peak(nums, i) else 0
                    if new_peak != peaks[i]:
                        # Update BIT with the difference
                        bit.update(i, new_peak - peaks[i])
                        peaks[i] = new_peak
    return result

# Example usage:
if __name__ == '__main__':
    nums = [3, 1, 4, 2, 5]
    queries = [[2, 3, 4], [1, 0, 4]]
    print(processQueries(nums, queries))  # Expected output: [0]
← Back to All Questions