In this guide, you will get 3187. Peaks in Array LeetCode Solution with the best time and space complexity. The solution to Peaks in Array problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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.
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 <= 105
1 <= nums[i] <= 105
1 <= queries.length <= 105
queries[i][0] == 1 or queries[i][0] == 2
For all i that:
class FenwickTree {
public:
FenwickTree(int n) : sums(n + 1) {}
void add(int i, int delta) {
while (i < sums.size()) {
sums[i] += delta;
i += lowbit(i);
}
}
int get(int i) const {
int sum = 0;
while (i > 0) {
sum += sums[i];
i -= lowbit(i);
}
return sum;
}
private:
vector<int> sums;
static inline int lowbit(int i) {
return i & -i;
}
};
class Solution {
public:
vector<int> countOfPeaks(vector<int>& nums, vector<vector<int>>& queries) {
vector<int> ans;
vector<int> peak = getPeak(nums);
FenwickTree tree(peak.size());
for (int i = 0; i < peak.size(); ++i)
tree.add(i + 1, peak[i]);
// Update the peak array and Fenwick tree if the peak status of nums[i]
// changes.
auto update = [&](int i) {
const int newPeak = isPeak(nums, i);
if (newPeak != peak[i]) {
tree.add(i + 1, newPeak - peak[i]);
peak[i] = newPeak;
}
};
for (const vector<int>& query : queries)
if (query[0] == 1) {
const int l = query[1];
const int r = query[2];
ans.push_back(r - l < 2 ? 0 : tree.get(r) - tree.get(l + 1));
} else if (query[0] == 2) {
const int index = query[1];
const int val = query[2];
nums[index] = val;
update(index);
if (index > 0)
update(index - 1);
if (index + 1 < nums.size())
update(index + 1);
}
return ans;
}
private:
vector<int> getPeak(const vector<int>& nums) {
vector<int> peak(nums.size());
for (int i = 1; i + 1 < nums.size(); ++i)
peak[i] = nums[i] > nums[i - 1] && nums[i] > nums[i + 1];
return peak;
}
bool isPeak(const vector<int>& nums, int i) {
return i > 0 && i + 1 < nums.size() && nums[i] > nums[i - 1] &&
nums[i] > nums[i + 1];
}
}; /* code provided by PROGIEZ */
3187. Peaks in Array LeetCode Solution in Java
class FenwickTree {
public FenwickTree(int n) {
sums = new int[n + 1];
}
public void add(int i, int delta) {
while (i < sums.length) {
sums[i] += delta;
i += lowbit(i);
}
}
public int get(int i) {
int sum = 0;
while (i > 0) {
sum += sums[i];
i -= lowbit(i);
}
return sum;
}
private int[] sums;
private static int lowbit(int i) {
return i & -i;
}
}
class Solution {
public List<Integer> countOfPeaks(int[] nums, int[][] queries) {
List<Integer> ans = new ArrayList<>();
int[] peak = getPeak(nums);
FenwickTree tree = new FenwickTree(peak.length);
for (int i = 0; i < peak.length; ++i)
tree.add(i + 1, peak[i]);
// Update the peak array and Fenwick tree if the peak status of nums[i]
// changes.
for (int[] query : queries) {
if (query[0] == 1) {
final int l = query[1];
final int r = query[2];
ans.add(r - l < 2 ? 0 : tree.get(r) - tree.get(l + 1));
} else if (query[0] == 2) {
final int index = query[1];
final int val = query[2];
nums[index] = val;
update(nums, peak, tree, index);
if (index > 0)
update(nums, peak, tree, index - 1);
if (index + 1 < nums.length)
update(nums, peak, tree, index + 1);
}
}
return ans;
}
private void update(int[] nums, int[] peak, FenwickTree tree, int i) {
final int newPeak = isPeak(nums, i) ? 1 : 0;
if (newPeak != peak[i]) {
tree.add(i + 1, newPeak - peak[i]);
peak[i] = newPeak;
}
}
private int[] getPeak(int[] nums) {
int[] peak = new int[nums.length];
for (int i = 1; i + 1 < nums.length; i++)
peak[i] = nums[i] > nums[i - 1] && nums[i] > nums[i + 1] ? 1 : 0;
return peak;
}
private boolean isPeak(int[] nums, int i) {
return i > 0 && i + 1 < nums.length && nums[i] > nums[i - 1] && nums[i] > nums[i + 1];
}
} // code provided by PROGIEZ
3187. Peaks in Array LeetCode Solution in Python
class FenwickTree:
def __init__(self, n: int):
self.sums = [0] * (n + 1)
def add(self, i: int, delta: int) -> None:
while i < len(self.sums):
self.sums[i] += delta
i += FenwickTree.lowbit(i)
def get(self, i: int) -> int:
summ = 0
while i > 0:
summ += self.sums[i]
i -= FenwickTree.lowbit(i)
return summ
@staticmethod
def lowbit(i: int) -> int:
return i & -i
class Solution:
def countOfPeaks(
self,
nums: list[int],
queries:
list[list[int]],
) -> list[int]:
ans = []
peak = [0] + [int(a < b > c)
for a, b, c in zip(nums[:-2], nums[1:-1], nums[2:])] + [0]
tree = FenwickTree(len(peak))
for i, p in enumerate(peak):
tree.add(i + 1, p)
def update(i: int) -> None:
"""
Update the peak array and Fenwick tree if the peak status of nums[i]
changes.
"""
newPeak = self._isPeak(nums, i)
if newPeak != peak[i]:
tree.add(i + 1, newPeak - peak[i])
peak[i] = newPeak
for query in queries:
if query[0] == 1:
l = query[1]
r = query[2]
ans.append(0 if r - l < 2 else tree.get(r) - tree.get(l + 1))
elif query[0] == 2:
index = query[1]
val = query[2]
nums[index] = val
update(index)
if index > 0:
update(index - 1)
if index + 1 < len(nums):
update(index + 1)
return ans
def _isPeak(self, nums: list[int], i: int) -> bool:
return i > 0 and i + 1 < len(nums) and nums[i - 1] < nums[i] > nums[i + 1] # code by PROGIEZ
