Find the Number of Subarrays Where Boundary Elements Are Maximum - Problem

You are given an array of positive integers nums.

Return the number of subarrays of nums where the first and last elements of the subarray are equal to the largest element in the subarray.

A subarray is a contiguous sequence of elements within an array.

Input & Output

Example 1 — Basic Case

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

› Output: 6

💡 Note: Valid subarrays: [1] (first=last=max=1), [4] (first=last=max=4), [3] at index 2, [3] at index 3, [3,3] (first=last=max=3), [2] (first=last=max=2)

Example 2 — All Same Elements

$ Input: nums = [3,3,3]

› Output: 6

💡 Note: All elements equal, so all subarrays are valid: [3], [3], [3], [3,3], [3,3], [3,3,3]

Example 3 — Single Element

$ Input: nums = [1]

› Output: 1

💡 Note: Only one subarray [1] where first=last=max=1

Constraints

1 ≤ nums.length ≤ 10⁵
1 ≤ nums[i] ≤ 10⁹

Visualization

Tap to expand

Asked in

G Google 15 f Meta 12 a Amazon 8

The key insight is that a subarray is valid only when its first and last elements equal the maximum element within that subarray. The optimal approach uses a monotonic stack to efficiently find the range where each element can be the maximum, then counts valid subarrays within those ranges. Time: O(n), Space: O(n)

Common Approaches

✓ Math

⏱️ Time: N/A Space: N/A

Brute Force - Check All Subarrays

⏱️ Time: O(n³) Space: O(1)

For each possible starting position, extend the subarray to all possible ending positions. For each subarray, find the maximum element and check if it equals both the first and last elements.

Monotonic Stack Optimization

⏱️ Time: O(n) Space: O(n)

For each element, use a monotonic decreasing stack to find the leftmost and rightmost positions where it can be the maximum. Then count valid subarrays within that range.

Optimized Two-Pass Solution

⏱️ Time: O(n²) Space: O(1)

For each position as a potential maximum, expand in both directions while the element remains the maximum. Count subarrays where the boundary elements equal the current maximum.

Algorithm Steps — Algorithm Steps

Code -

solution.c — C

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

int solution(int* nums, int n) {
    int count = 0;
    
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            // Find maximum in subarray nums[i:j+1]
            int max_val = nums[i];
            for (int k = i; k <= j; k++) {
                if (nums[k] > max_val) {
                    max_val = nums[k];
                }
            }
            // Check if first and last elements equal the maximum
            if (nums[i] == nums[j] && nums[i] == max_val) {
                count++;
            }
        }
    }
    
    return count;
}

void parseArray(const char* str, int* arr, int* size) {
    *size = 0;
    const char* p = str;
    while (*p && *p != '[') p++;
    if (*p == '[') p++;
    while (*p && *p != ']') {
        while (*p == ' ' || *p == ',') p++;
        if (*p == ']' || *p == '\0') break;
        arr[(*size)++] = (int)strtol(p, (char**)&p, 10);
    }
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int nums[1000];
    int n = 0;
    char* token = strtok(line + 1, ",]");
    
    while (token != NULL) {
        nums[n++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int result = solution(nums, n);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

⚠ Quadratic Growth

Space Complexity

✓ Linear Space

23.4K Views

Medium Frequency

~25 min Avg. Time

856 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