3113. Max Boundary Subarrays

Find the Number of Subarrays Where Boundary Elements Are Maximum

At first glance, this problem looks quite scary. AC rate is only ~$34\%$.

However, if we look closer, it's incredibly easy to capture core logic and AC instantly.

I say, this nagging long title is just a bluff 👻

Boundary Elements Must Be the Maximum

The core property of all desired subarrays we need to find.

From here, we immediately lock down a vital observation when traversing nums:

When traversing to $nums[j]$:

Any $nums[i]$ that satisfies $nums[i] < nums[j]$ where $i < j$

can't form a valid subarray $nums[i: k + 1]$, where $j \le k$, that meets required criteria.

Why? All because $nums[i] <$nums[j]$.

$nums[i]$ as left boundary fails to be the maximum of this subarray.

Any $nums[i]$ that satisfies $nums[i] < nums[j]$ with $i < j$

can be forever eliminated upon traversing to $nums[j]$.

Continue From Above

Once we cancel out all $nums[i] < nums[j]$ where $i < j$,

remaining elements is either equal to $nums[j]$, or greater.

Our logic simplifies into two scenarios:

I. There is no $nums[i]$ equal to $nums[j]$ remaining,

when $nums[j]$ acts as right boundary, there is only one subarray satisfying requirement:

yep, $nums[j]$ itself as a single-element subarray.

II. There are existing elements $nums[i] = nums[j]$,

which means we simply increment $Count_{nums[i]}$ by 1.

Incremented $Count_{nums[i]}$ represents total number of valid left boundaries

that can pair with the right boundary $nums[j]$.

In Short

Both scenarios include the case of $nums[j]$ forming a valid subarray by itself.

However, scenario II also captures when prior identical elements pair up as left boundary.

Monotonicity Again

As of now, you've probably realized that this problem is all about monotonicity.

We implement aforementioned strategy via a strictly decreasing stack.

When traversing to $nums[j]$, as long as the stack isn't empty,

and top element satisfies $nums[i] < nums[j]$, we pop stack.

After popping all smaller elements,

we might find that stack top has an element exactly equal to $nums[j]$.

If so, just do increment: $Count_{nums[i]} += 1$.

Otherwise, we push $nums[j]$ into the stack with $Count_{nums[j]} = 1$.

Valid left boundaries that right boundary $nums[j]$ can pair: the count attached to stack top's element.

An essential implementation detail: the count is tied to its respective element itself.

When popping, $Count_{nums[i]}$ is also popped away.

All we have to do now is push $nums[j]$ along with its count into the stack,

and accumulate its count into our final answer subarrays_count.

C++

#include <stack>
#include <vector>
using namespace std;

long long count_subarrays(vector<int>& nums) {
    stack<pair<int, int>> stack; // Format: {num, count}.

    long long subarraysCount = 0;

    for (const auto& num : nums) {
        while (!stack.empty() && stack.top().first < num) stack.pop();

        if (!stack.empty() && stack.top().first == num)
            stack.top().second++;

        else
            stack.push({num, 1});

        subarraysCount += stack.top().second;
    }

    return subarraysCount;
}

Python

def count_subarrays(nums: list[int]) -> int:
    stack: list[tuple[int, int]] = []  # Format: (num, count).

    subarrays_count = 0

    for num in nums:
        while stack and stack[-1][0] < num:
            stack.pop(-1)

        count = 1  # Base case: current num only.

        if stack and stack[-1][0] == num:
            count += stack.pop(-1)[1]

        subarrays_count += count
        stack.append((num, count))

    return subarrays_count

Both time and space complexities align with typical monotonic stack problems: clean $O(n)$.

Once we see through the traversal elimination mechanism, this problem is an easy AC~~

Follow-up Problems

What are the lower and upper bounds for our final answer subarrays_count?