3187. Peaks in Array
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 subarraynums[li..ri].queries[i] = [2, indexi, vali], changenums[indexi]tovali.
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.
Example 1:
Input: nums = [3,1,4,2,5], queries = [[2,3,4],[1,0,4]]
Output: [0]
Explanation:
First query: We change nums[3] to 4 and nums becomes [3,1,4,4,5].
Second query: The number of peaks in the [3,1,4,4,5] is 0.
Example 2:
Input: nums = [4,1,4,2,1,5], queries = [[2,2,4],[1,0,2],[1,0,4]]
Output: [0,1]
Explanation:
First query: nums[2] should become 4, but it is already set to 4.
Second query: The number of peaks in the [4,1,4] is 0.
Third query: The second 4 is a peak in the [4,1,4,2,1].
Constraints:
3 <= nums.length <= 1051 <= nums[i] <= 1051 <= queries.length <= 105queries[i][0] == 1orqueries[i][0] == 2- For all
ithat:queries[i][0] == 1:0 <= queries[i][1] <= queries[i][2] <= nums.length - 1queries[i][0] == 2:0 <= queries[i][1] <= nums.length - 1,1 <= queries[i][2] <= 105
Solutions
Solution 1: Binary Indexed Tree
According to the problem description, for $0 < i < n - 1$, if it satisfies $nums[i - 1] < nums[i]$ and $nums[i] > nums[i + 1]$, we can consider $nums[i]$ as $1$, otherwise as $0$. Thus, for operation $1$, i.e., querying the number of peak elements in the subarray $nums[l..r]$, it is equivalent to querying the number of $1$s in the interval $[l + 1, r - 1]$. We can use a binary indexed tree to maintain the number of $1$s in the interval $[1, n - 1]$.
For operation $1$, i.e., updating $nums[idx]$ to $val$, it will only affect the values at positions $idx - 1$, $idx$, and $idx + 1$, so we only need to update these three positions. Specifically, we can first remove the peak elements at these three positions, then update the value of $nums[idx]$, and finally add back the peak elements at these three positions.
The time complexity is $O((n + q) \times \log n)$, and the space complexity is $O(n)$. Here, $n$ and $q$ are the lengths of the array nums and the query array queries, respectively.
Python3
class BinaryIndexedTree:
__slots__ = "n", "c"
def __init__(self, n: int):
self.n = n
self.c = [0] * (n + 1)
def update(self, x: int, delta: int) -> None:
while x <= self.n:
self.c[x] += delta
x += x & -x
def query(self, x: int) -> int:
s = 0
while x:
s += self.c[x]
x -= x & -x
return s
class Solution:
def countOfPeaks(self, nums: List[int], queries: List[List[int]]) -> List[int]:
def update(i: int, val: int):
if i <= 0 or i >= n - 1:
return
if nums[i - 1] < nums[i] and nums[i] > nums[i + 1]:
tree.update(i, val)
n = len(nums)
tree = BinaryIndexedTree(n - 1)
for i in range(1, n - 1):
update(i, 1)
ans = []
for q in queries:
if q[0] == 1:
l, r = q[1] + 1, q[2] - 1
ans.append(0 if l > r else tree.query(r) - tree.query(l - 1))
else:
idx, val = q[1:]
for i in range(idx - 1, idx + 2):
update(i, -1)
nums[idx] = val
for i in range(idx - 1, idx + 2):
update(i, 1)
return ans
Java
class BinaryIndexedTree {
private int n;
private int[] c;
public BinaryIndexedTree(int n) {
this.n = n;
this.c = new int[n + 1];
}
public void update(int x, int delta) {
for (; x <= n; x += x & -x) {
c[x] += delta;
}
}
public int query(int x) {
int s = 0;
for (; x > 0; x -= x & -x) {
s += c[x];
}
return s;
}
}
class Solution {
private BinaryIndexedTree tree;
private int[] nums;
public List<Integer> countOfPeaks(int[] nums, int[][] queries) {
int n = nums.length;
this.nums = nums;
tree = new BinaryIndexedTree(n - 1);
for (int i = 1; i < n - 1; ++i) {
update(i, 1);
}
List<Integer> ans = new ArrayList<>();
for (var q : queries) {
if (q[0] == 1) {
int l = q[1] + 1, r = q[2] - 1;
ans.add(l > r ? 0 : tree.query(r) - tree.query(l - 1));
} else {
int idx = q[1], val = q[2];
for (int i = idx - 1; i <= idx + 1; ++i) {
update(i, -1);
}
nums[idx] = val;
for (int i = idx - 1; i <= idx + 1; ++i) {
update(i, 1);
}
}
}
return ans;
}
private void update(int i, int val) {
if (i <= 0 || i >= nums.length - 1) {
return;
}
if (nums[i - 1] < nums[i] && nums[i] > nums[i + 1]) {
tree.update(i, val);
}
}
}
C++
class BinaryIndexedTree {
private:
int n;
vector<int> c;
public:
BinaryIndexedTree(int n)
: n(n)
, c(n + 1) {}
void update(int x, int delta) {
for (; x <= n; x += x & -x) {
c[x] += delta;
}
}
int query(int x) {
int s = 0;
for (; x > 0; x -= x & -x) {
s += c[x];
}
return s;
}
};
class Solution {
public:
vector<int> countOfPeaks(vector<int>& nums, vector<vector<int>>& queries) {
int n = nums.size();
BinaryIndexedTree tree(n - 1);
auto update = [&](int i, int val) {
if (i <= 0 || i >= n - 1) {
return;
}
if (nums[i - 1] < nums[i] && nums[i] > nums[i + 1]) {
tree.update(i, val);
}
};
for (int i = 1; i < n - 1; ++i) {
update(i, 1);
}
vector<int> ans;
for (auto& q : queries) {
if (q[0] == 1) {
int l = q[1] + 1, r = q[2] - 1;
ans.push_back(l > r ? 0 : tree.query(r) - tree.query(l - 1));
} else {
int idx = q[1], val = q[2];
for (int i = idx - 1; i <= idx + 1; ++i) {
update(i, -1);
}
nums[idx] = val;
for (int i = idx - 1; i <= idx + 1; ++i) {
update(i, 1);
}
}
}
return ans;
}
};
Go
type BinaryIndexedTree struct {
n int
c []int
}
func NewBinaryIndexedTree(n int) *BinaryIndexedTree {
return &BinaryIndexedTree{n: n, c: make([]int, n+1)}
}
func (bit *BinaryIndexedTree) update(x, delta int) {
for ; x <= bit.n; x += x & -x {
bit.c[x] += delta
}
}
func (bit *BinaryIndexedTree) query(x int) int {
s := 0
for ; x > 0; x -= x & -x {
s += bit.c[x]
}
return s
}
func countOfPeaks(nums []int, queries [][]int) (ans []int) {
n := len(nums)
tree := NewBinaryIndexedTree(n - 1)
update := func(i, val int) {
if i <= 0 || i >= n-1 {
return
}
if nums[i-1] < nums[i] && nums[i] > nums[i+1] {
tree.update(i, val)
}
}
for i := 1; i < n-1; i++ {
update(i, 1)
}
for _, q := range queries {
if q[0] == 1 {
l, r := q[1]+1, q[2]-1
t := 0
if l <= r {
t = tree.query(r) - tree.query(l-1)
}
ans = append(ans, t)
} else {
idx, val := q[1], q[2]
for i := idx - 1; i <= idx+1; i++ {
update(i, -1)
}
nums[idx] = val
for i := idx - 1; i <= idx+1; i++ {
update(i, 1)
}
}
}
return
}
TypeScript
class BinaryIndexedTree {
private n: number;
private c: number[];
constructor(n: number) {
this.n = n;
this.c = Array(n + 1).fill(0);
}
update(x: number, delta: number): void {
for (; x <= this.n; x += x & -x) {
this.c[x] += delta;
}
}
query(x: number): number {
let s = 0;
for (; x > 0; x -= x & -x) {
s += this.c[x];
}
return s;
}
}
function countOfPeaks(nums: number[], queries: number[][]): number[] {
const n = nums.length;
const tree = new BinaryIndexedTree(n - 1);
const update = (i: number, val: number): void => {
if (i <= 0 || i >= n - 1) {
return;
}
if (nums[i - 1] < nums[i] && nums[i] > nums[i + 1]) {
tree.update(i, val);
}
};
for (let i = 1; i < n - 1; ++i) {
update(i, 1);
}
const ans: number[] = [];
for (const q of queries) {
if (q[0] === 1) {
const [l, r] = [q[1] + 1, q[2] - 1];
ans.push(l > r ? 0 : tree.query(r) - tree.query(l - 1));
} else {
const [idx, val] = [q[1], q[2]];
for (let i = idx - 1; i <= idx + 1; ++i) {
update(i, -1);
}
nums[idx] = val;
for (let i = idx - 1; i <= idx + 1; ++i) {
update(i, 1);
}
}
}
return ans;
}