LeetCode 3113 - Find the Number of Subarrays Where Boundary Elements Are Maximum

We are given an array nums of positive integers. We need to count how many contiguous subarrays satisfy a very specific condition: - The first element of the subarray and the last element of the subarray must both be equal to the maximum value inside that subarray.

leetcodehardarraybinary-searchstackmonotonic-stack

LeetCode Problem 3113

Difficulty: 🔴 Hard
Topics: Array, Binary Search, Stack, Monotonic Stack

Solution

Problem Understanding

We are given an array nums of positive integers. We need to count how many contiguous subarrays satisfy a very specific condition:

  • The first element of the subarray and the last element of the subarray must both be equal to the maximum value inside that subarray.

In other words, for a subarray nums[l:r+1], we need:

  • nums[l] == nums[r]
  • That value must also be the largest element anywhere in the subarray

A subarray is contiguous, so we only consider consecutive elements.

For example, consider the subarray [3, 1, 3]:

  • The first element is 3
  • The last element is 3
  • The maximum element in the subarray is also 3

So this subarray is valid.

However, [3, 4, 3] is invalid because the maximum element is 4, not 3.

The constraints are important:

  • nums.length can be up to 10^5
  • Values can be as large as 10^9

An O(n^2) solution will be far too slow for the maximum input size. We need something close to linear time.

There are several edge cases worth noticing immediately.

If all elements are equal, then every subarray is valid. For an array of length n, the answer becomes n * (n + 1) / 2.

If all elements are strictly increasing, then only single-element subarrays are valid, because any longer subarray has a larger element somewhere inside.

Single-element subarrays are always valid because the only element is both the first, last, and maximum element.

The main challenge is efficiently determining which equal-value pairs can form valid boundaries without any larger value appearing between them.

Approaches

Brute Force

The most direct solution is to enumerate every possible subarray.

For each subarray:

  1. Compute its maximum value
  2. Check whether the first and last elements are equal
  3. Check whether that value equals the maximum

This approach is correct because it explicitly verifies the problem definition for every subarray.

However, there are O(n^2) subarrays. If we compute the maximum naively for each one, the complexity becomes O(n^3).

We can improve slightly by maintaining the running maximum while expanding the right boundary, reducing the complexity to O(n^2), but that is still too slow for n = 10^5.

Optimal Insight

The key observation is this:

A subarray is valid if:

  • Its endpoints have the same value x
  • No element larger than x appears between them

This transforms the problem into a structural question.

Suppose we process the array from left to right while maintaining a monotonic decreasing stack.

The stack helps us track which values are still "active", meaning they have not been invalidated by a larger value appearing later.

For each value x:

  • Any smaller values on top of the stack are removed because x blocks them from extending further
  • If x already exists on top of the stack, then every previous occurrence of x currently active can pair with the current x
  • We count how many active occurrences of x exist

This works because active occurrences of x are precisely those that do not have a larger element between them and the current position.

We can compress equal values in the stack by storing:

  • the value
  • how many active occurrences currently exist

This yields an O(n) solution.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(1) Enumerates every subarray and checks validity
Optimal O(n) O(n) Uses a monotonic decreasing stack with frequency counts

Algorithm Walkthrough

Optimal Monotonic Stack Algorithm

  1. Initialize an empty monotonic decreasing stack.

Each stack entry stores:

  • the value
  • the number of active occurrences of that value

The stack remains in decreasing order from bottom to top. 2. Initialize answer = 0. 3. Iterate through each number num in nums. 4. While the stack is not empty and the top value is smaller than num, pop it.

This step is critical.

If a larger value appears, then any smaller value can no longer form valid subarrays extending beyond this point, because the larger value would become the maximum. 5. After removing smaller elements, there are two possibilities.

If the stack top has value equal to num:

  • Increment its frequency
  • Add the updated frequency to the answer

Why?

Every previous active occurrence of num can pair with the current num.

Additionally, the current element itself forms a valid single-element subarray. 6. Otherwise:

  • Push (num, 1) onto the stack
  • Add 1 to the answer for the single-element subarray
  1. Continue until the entire array is processed.
  2. Return answer.

Why it works

The monotonic stack guarantees that between any two active occurrences of value x, there is no element greater than x.

Whenever a larger element appears, smaller values are removed because they can no longer participate in future valid subarrays.

Thus, when we encounter another x, every active x in the stack corresponds exactly to one valid subarray ending at the current position.

This invariant ensures correctness.

Python Solution

from typing import List

class Solution:
    def numberOfSubarrays(self, nums: List[int]) -> int:
        stack = []  # (value, frequency)
        answer = 0

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

            if stack and stack[-1][0] == num:
                stack[-1][1] += 1
                answer += stack[-1][1]
            else:
                stack.append([num, 1])
                answer += 1

        return answer

The implementation follows the algorithm directly.

The stack stores pairs of [value, frequency]. The frequency represents how many active occurrences of that value currently exist.

For each number:

  • Smaller stack elements are removed because they are blocked by the current larger value.
  • If the top value equals the current number, we increase its frequency.
  • The new frequency equals the number of valid subarrays ending at this position with maximum equal to the boundary value.
  • Otherwise, we start a new group with frequency 1.

The answer accumulates all valid subarrays across the traversal.

Go Solution

func numberOfSubarrays(nums []int) int64 {
	type Pair struct {
		value int
		count int64
	}

	stack := []Pair{}
	var answer int64 = 0

	for _, num := range nums {
		for len(stack) > 0 && stack[len(stack)-1].value < num {
			stack = stack[:len(stack)-1]
		}

		if len(stack) > 0 && stack[len(stack)-1].value == num {
			stack[len(stack)-1].count++
			answer += stack[len(stack)-1].count
		} else {
			stack = append(stack, Pair{
				value: num,
				count: 1,
			})
			answer += 1
		}
	}

	return answer
}

The Go version mirrors the Python logic closely.

A custom Pair struct stores the value and frequency count.

The answer uses int64 because the number of valid subarrays can reach approximately n * (n + 1) / 2, which exceeds 32-bit integer range for n = 10^5.

Slices are used as stacks with append and truncation operations.

Worked Examples

Example 1

Input:

nums = [1,4,3,3,2]

Processing steps:

Step num Stack Before Action Stack After Added Total
1 1 [] Push 1 [[1,1]] 1 1
2 4 [[1,1]] Pop 1, push 4 [[4,1]] 1 2
3 3 [[4,1]] Push 3 [[4,1],[3,1]] 1 3
4 3 [[4,1],[3,1]] Increment freq [[4,1],[3,2]] 2 5
5 2 [[4,1],[3,2]] Push 2 [[4,1],[3,2],[2,1]] 1 6

Final answer:

6

Example 2

Input:

nums = [3,3,3]
Step num Stack Before Action Stack After Added Total
1 3 [] Push 3 [[3,1]] 1 1
2 3 [[3,1]] Increment freq [[3,2]] 2 3
3 3 [[3,2]] Increment freq [[3,3]] 3 6

Final answer:

6

The valid subarrays are:

  • Three length-1 subarrays
  • Two length-2 subarrays
  • One length-3 subarray

Example 3

Input:

nums = [1]
Step num Stack Before Action Stack After Added Total
1 1 [] Push 1 [[1,1]] 1 1

Final answer:

1

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each element is pushed and popped at most once
Space O(n) Stack may contain all elements in decreasing order

The time complexity is linear because every array element enters the stack once and leaves the stack at most once.

The space complexity is linear in the worst case, such as a strictly decreasing array where all elements remain in the stack.

Test Cases

from typing import List

class Solution:
    def numberOfSubarrays(self, nums: List[int]) -> int:
        stack = []
        answer = 0

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

            if stack and stack[-1][0] == num:
                stack[-1][1] += 1
                answer += stack[-1][1]
            else:
                stack.append([num, 1])
                answer += 1

        return answer

sol = Solution()

assert sol.numberOfSubarrays([1,4,3,3,2]) == 6  # provided example
assert sol.numberOfSubarrays([3,3,3]) == 6  # all equal
assert sol.numberOfSubarrays([1]) == 1  # single element

assert sol.numberOfSubarrays([1,2,3,4]) == 4  # strictly increasing
assert sol.numberOfSubarrays([4,3,2,1]) == 4  # strictly decreasing

assert sol.numberOfSubarrays([2,1,2]) == 3  # one additional valid pair
assert sol.numberOfSubarrays([5,1,5]) == 3  # large boundary pair
assert sol.numberOfSubarrays([5,6,5]) == 3  # invalid pair because 6 is larger

assert sol.numberOfSubarrays([2,2,2,2]) == 10  # all subarrays valid
assert sol.numberOfSubarrays([1,3,2,3,1]) == 6  # separated equal maxima

assert sol.numberOfSubarrays([10]) == 1  # minimum size
assert sol.numberOfSubarrays([1,1000000000,1]) == 3  # large values

Test Summary

Test Why
[1,4,3,3,2] Validates mixed structure example
[3,3,3] Every subarray should be valid
[1] Smallest possible input
[1,2,3,4] Increasing sequence, only singles valid
[4,3,2,1] Decreasing sequence
[2,1,2] Valid boundary pair around smaller value
[5,1,5] Equal maxima separated by smaller value
[5,6,5] Larger middle value invalidates pair
[2,2,2,2] Maximum number of valid subarrays
[1,3,2,3,1] Multiple valid regions
[10] Boundary size validation
[1,1000000000,1] Large integer handling

Edge Cases

A very important edge case is when all elements are equal. In this situation, every possible subarray satisfies the condition because the first and last elements are always equal to the maximum value. Many incorrect implementations undercount these combinations. The stack frequency compression handles this naturally by incrementally counting all active equal elements.

Another important edge case is a strictly increasing array such as [1,2,3,4]. Every new element immediately removes all previous smaller elements from the stack. As a result, only single-element subarrays remain valid. This validates that the popping logic correctly invalidates smaller values once a larger element appears.

A third important case is when equal boundary values are separated by a larger value, such as [5,6,5]. Although the endpoints match, the maximum inside the subarray is 6, so the subarray is invalid. The monotonic stack correctly handles this because the first 5 is removed when 6 appears, preventing it from pairing with the later 5.

Finally, single-element arrays must always return 1. The implementation handles this automatically because every element contributes at least one valid subarray consisting of itself alone.