Peaks in Array - Practice Coding Problems

Peaks in Array - Problem

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.

Note: The first and the last element of an array or a subarray cannot be a peak.

Input & Output

Example 1 — Basic Peak Counting

$ Input: nums = [2,8,6,1,5], queries = [[2,3,4],[1,0,4]]

› Output: [1]

💡 Note: After updating nums[3] = 4, array becomes [2,8,6,4,5]. Query [1,0,4] counts peaks in range [0,4]. Only index 1 (value 8) is a peak since 8 > 2 and 8 > 6.

Example 2 — Multiple Queries

$ Input: nums = [1,3,2,4,1], queries = [[1,1,4],[2,2,5],[1,0,3]]

› Output: [2,1]

💡 Note: First query [1,1,4]: peaks at indices 1 (3>1,3>2) and 3 (4>2,4>1), count=2. After update nums[2]=5: [1,3,5,4,1]. Second query [1,0,3]: only peak at index 1 (3>1,3>5 is false), but index 2 (5>3,5>4) is peak, count=1.

Example 3 — Edge Case No Peaks

$ Input: nums = [1,2,3], queries = [[1,0,2]]

› Output: [0]

💡 Note: Range [0,2] has no valid peak positions since first and last elements cannot be peaks. Only index 1 could be a peak, but 2 < 3, so no peaks found.

Constraints

3 ≤ nums.length ≤ 10⁵
1 ≤ nums[i] ≤ 10⁵
1 ≤ queries.length ≤ 10⁵
queries[i] = [1, l_i, r_i] or queries[i] = [2, index_i, val_i]
0 ≤ l_i < r_i ≤ nums.length - 1
0 ≤ index_i ≤ nums.length - 1
1 ≤ val_i ≤ 10⁵

Visualization

Tap to expand

Understanding the Visualization

Input Array

Array with elements marked as peaks or non-peaks

Query Processing

Count peaks in range or update array values

Output

Results for all range queries

Key Takeaway

🎯 Key Insight: Use segment trees or BIT to efficiently track peak counts across range queries while handling dynamic updates

Asked in

G Google 25 f Facebook 18 a Amazon 15 M Microsoft 12

The key insight is to precompute peak information and use efficient data structures for range operations. The segment tree approach provides O(log n) queries and updates by maintaining peak counts in tree nodes. Best approach is segment tree with lazy propagation: Time O(n + q log n), Space O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Segment Tree with Lazy Propagation	O(n + q log n)	O(n)	Use segment tree to efficiently handle range queries and updates
Brute Force Range Scanning	O(q × n)	O(1)	For each query, scan the range and count peaks directly

Segment Tree with Lazy Propagation — Algorithm Steps

Step 1: Precompute initial peak array and build segment tree
Step 2: For range queries, use segment tree to get peak count in O(log n)
Step 3: For updates, modify array and update affected peak statuses, then update segment tree

Visualization

Tap to expand

Step-by-Step Walkthrough

Build Tree

Create segment tree with peak counts for each range

Range Query

Traverse tree to get sum of peaks in O(log n)

Update

Update affected peaks and propagate changes up the tree

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    int n;
    int* tree;
} SegmentTree;

SegmentTree* createSegmentTree(int* arr, int n) {
    SegmentTree* st = (SegmentTree*)malloc(sizeof(SegmentTree));
    st->n = n;
    st->tree = (int*)calloc(4 * n, sizeof(int));
    return st;
}

void buildTree(SegmentTree* st, int* arr, int node, int start, int end) {
    if (start == end) {
        st->tree[node] = arr[start];
    } else {
        int mid = (start + end) / 2;
        buildTree(st, arr, 2 * node, start, mid);
        buildTree(st, arr, 2 * node + 1, mid + 1, end);
        st->tree[node] = st->tree[2 * node] + st->tree[2 * node + 1];
    }
}

void updateTree(SegmentTree* st, int node, int start, int end, int idx, int val) {
    if (start == end) {
        st->tree[node] = val;
    } else {
        int mid = (start + end) / 2;
        if (idx <= mid) {
            updateTree(st, 2 * node, start, mid, idx, val);
        } else {
            updateTree(st, 2 * node + 1, mid + 1, end, idx, val);
        }
        st->tree[node] = st->tree[2 * node] + st->tree[2 * node + 1];
    }
}

int queryTree(SegmentTree* st, int node, int start, int end, int l, int r) {
    if (r < start || end < l) return 0;
    if (l <= start && end <= r) return st->tree[node];
    int mid = (start + end) / 2;
    return queryTree(st, 2 * node, start, mid, l, r) + queryTree(st, 2 * node + 1, mid + 1, end, l, r);
}

int* solution(int* nums, int numsSize, int** queries, int queriesSize, int* queriesColSize, int* returnSize) {
    int* peaks = (int*)calloc(numsSize, sizeof(int));
    
    // Initialize peaks array
    for (int i = 1; i < numsSize - 1; i++) {
        if (nums[i] > nums[i-1] && nums[i] > nums[i+1]) {
            peaks[i] = 1;
        }
    }
    
    SegmentTree* segTree = createSegmentTree(peaks, numsSize);
    buildTree(segTree, peaks, 1, 0, numsSize - 1);
    
    int* result = (int*)malloc(queriesSize * sizeof(int));
    int resultIndex = 0;
    
    for (int i = 0; i < queriesSize; i++) {
        if (queries[i][0] == 1) { // Range query
            int l = queries[i][1], r = queries[i][2];
            if (l + 1 >= r) {
                result[resultIndex++] = 0;
            } else {
                int count = queryTree(segTree, 1, 0, numsSize - 1, l + 1, r - 1);
                result[resultIndex++] = count;
            }
        } else { // Update
            int index = queries[i][1], val = queries[i][2];
            nums[index] = val;
            
            // Update affected peaks
            int start = (index - 1 > 1) ? index - 1 : 1;
            int end = (index + 1 < numsSize - 1) ? index + 1 : numsSize - 2;
            for (int j = start; j <= end; j++) {
                int oldPeak = peaks[j];
                int newPeak = (nums[j] > nums[j-1] && nums[j] > nums[j+1]) ? 1 : 0;
                if (oldPeak != newPeak) {
                    peaks[j] = newPeak;
                    updateTree(segTree, 1, 0, numsSize - 1, j, newPeak);
                }
            }
        }
    }
    
    *returnSize = resultIndex;
    free(peaks);
    free(segTree->tree);
    free(segTree);
    return result;
}

int main() {
    char line[10000];
    
    // Read nums array
    fgets(line, sizeof(line), stdin);
    line[strcspn(line, "\n")] = 0;
    
    // Parse nums - simple parsing for [1,2,3] format
    int nums[1000];
    int numsSize = 0;
    char* token = strtok(line + 1, ",]");
    while (token) {
        nums[numsSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    // Read queries array
    fgets(line, sizeof(line), stdin);
    line[strcspn(line, "\n")] = 0;
    
    // Simple parsing for queries
    int queries[100][3];
    int* queryPtrs[100];
    int queriesSize = 0;
    int queriesColSize[100];
    
    char* ptr = line + 1; // Skip first [
    while (*ptr) {
        if (*ptr == '[') {
            ptr++;
            int col = 0;
            while (*ptr != ']') {
                if (*ptr >= '0' && *ptr <= '9' || *ptr == '-') {
                    queries[queriesSize][col++] = atoi(ptr);
                    while (*ptr && *ptr != ',' && *ptr != ']') ptr++;
                } else {
                    ptr++;
                }
            }
            queryPtrs[queriesSize] = queries[queriesSize];
            queriesColSize[queriesSize] = col;
            queriesSize++;
            ptr++;
        } else {
            ptr++;
        }
    }
    
    int returnSize;
    int* result = solution(nums, numsSize, queryPtrs, queriesSize, queriesColSize, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%d", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n + q log n)

Initial setup O(n), each query takes O(log n) time

⚡ Linearithmic

Space Complexity

O(n)

Segment tree requires O(n) space for internal nodes

⚡ Linearithmic Space

12.5K Views

Medium Frequency

~35 min Avg. Time

450 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Segment Tree with Lazy Propagation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler