Find the Number of Subarrays Where Boundary Elements Are Maximum solution and explanation
9 more videos on this problem
3113. Find the Number of Subarrays Where Boundary Elements Are Maximum | Binary Search | MonotonicAryan Mittal · 20:06 · 4K views
Leetcode Biweekly Contest 128 | Find the Number of Subarrays Where Boundary Elements Are MaximumPawan Kumar Giri · 27:08 · 1K views
3113. Find the Number of Subarrays Where Boundary Elements Are Maximum | Leetcode Biweekly 128codingMohan · 25:22 · 916 views
3113. Find the Number of Subarrays Where Boundary Elements Are Maximum (Leetcode Hard)Programming Live with Larry · 16:00 · 542 views
【每日一题】LeetCode 3113. Find the Number of Subarrays Where Boundary Elements Are MaximumHuifeng Guan · 10:47 · 269 views
3113. Find the Number of Subarrays Where Boundary Elements Are MaximumShivam Mishra LeetCode · 13:46 · 266 views
3113. Find the Number of Subarrays Where Boundary Elements Are Maximum Leetcode Biweekly Contest 128Ashish Kumar · 17:19 · 227 views
Study Session # 6 - LeetCode 3113 - Find The Number of SubArrays Where Boundary Elements Are MaximumAlpha-Code · 10:13 · 103 views
Find the Number of Subarrays Where Boundary Elements Are Maximum | LeetCode Bi-weekly 127sonpham@ - Competitive Programming · 15:27 · 56 views
Find the Number of Subarrays Where Boundary Elements Are Maximum | Leetcode Biweekly Contest - 128Shivam Gupta · 14:32 · 53 views
The problem
You are given an array of positive integers nums.
Return the number of subarrays of nums, where the first and the last elements of the subarray are equal to the largest element in the subarray.
Example 1:
Input: nums = [1,4,3,3,2]
Output: 6
Explanation:
There are 6 subarrays which have the first and the last elements equal to the largest element of the subarray:
- subarray
[1,4,3,3,2], with its largest element 1. The first element is 1 and the last element is also 1. - subarray
[1,4,3,3,2], with its largest element 4. The first element is 4 and the last element is also 4. - subarray
[1,4,3,3,2], with its largest element 3. The first element is 3 and the last element is also 3. - subarray
[1,4,3,3,2], with its largest element 3. The first element is 3 and the last element is also 3. - subarray
[1,4,3,3,2], with its largest element 2. The first element is 2 and the last element is also 2. - subarray
[1,4,3,3,2], with its largest element 3. The first element is 3 and the last element is also 3.
Hence, we return 6.
Example 2:
Input: nums = [3,3,3]
Output: 6
Explanation:
There are 6 subarrays which have the first and the last elements equal to the largest element of the subarray:
- subarray
[3,3,3], with its largest element 3. The first element is 3 and the last element is also 3. - subarray
[3,3,3], with its largest element 3. The first element is 3 and the last element is also 3. - subarray
[3,3,3], with its largest element 3. The first element is 3 and the last element is also 3. - subarray
[3,3,3], with its largest element 3. The first element is 3 and the last element is also 3. - subarray
[3,3,3], with its largest element 3. The first element is 3 and the last element is also 3. - subarray
[3,3,3], with its largest element 3. The first element is 3 and the last element is also 3.
Hence, we return 6.
Example 3:
Input: nums = [1]
Output: 1
Explanation:
There is a single subarray of nums which is [1], with its largest element 1. The first element is 1 and the last element is also 1.
Hence, we return 1.
Constraints:
1 <= nums.length <= 1051 <= nums[i] <= 109
Approach overview
Problem Overview: You are given an integer array and must count subarrays where the first and last elements are equal and also represent the maximum value inside that subarray. Any element between the boundaries must be less than or equal to those boundary values.
Approach 1: Brute Force Enumeration (O(n^2) time, O(1) space)
Enumerate every possible subarray using two indices i and j. For each subarray, compute the maximum value and check whether both boundary elements equal that maximum. This requires iterating through the elements inside the window or maintaining a running maximum while expanding j. The approach is straightforward and helps verify the definition of the constraint, but it becomes slow for large arrays since there are O(n^2) candidate subarrays.
Approach 2: Optimized Counting with Monotonic Stack (O(n) time, O(n) space)
The key observation: a valid subarray must have its maximum at both boundaries, meaning no element inside the range can exceed that value. A monotonic stack helps maintain a decreasing structure of elements while scanning the array. When you encounter a larger value, smaller elements are popped because they cannot serve as boundaries for future subarrays containing that larger value. For elements with the same value, maintain counts of how many times that value has appeared consecutively within the valid range. Each new equal element forms additional valid subarrays with previous occurrences of the same value. This converts the problem from enumerating ranges to counting combinations of equal maximum boundaries while preserving the decreasing stack property.
The stack ensures that all elements between equal boundaries remain smaller or equal. Each push/pop operation occurs once, giving linear complexity. The approach leverages concepts from stack processing and monotonic structures commonly used for next-greater-element style problems.
Recommended for interviews: Start by describing the brute force approach to demonstrate understanding of the constraint that boundary elements must equal the subarray maximum. Interviewers expect the optimized monotonic stack counting approach because it reduces the complexity from O(n^2) to O(n). Recognizing the connection to next greater element patterns and counting equal values within the stack shows strong mastery of array processing techniques.
Approach 1: Brute Force Approach
This approach involves checking every possible subarray in the array. For each subarray, we will check if the first and last elements are equal to the maximum element of that subarray, and if so, count it as a valid subarray.
def count_subarrays(nums):
count = 0
n = len(nums)
for i in range(n):
current_max = nums[i]
for j in range(i, n):
current_max = max(current_max, nums[j])
if nums[i] == current_max and nums[j] == current_max:
count += 1
return count
# Example Usage
nums = [1, 4, 3, 3, 2]
print(count_subarrays(nums)) # Output: 6public class SubarrayCounter {
public static int countSubarrays(int[] nums) {
int count = 0;
int n = nums.length;
for (int i = 0; i < n; i++) {
int currentMax = nums[i];
for (int j = i; j < n; j++) {
currentMax = Math.max(currentMax, nums[j]);
if (nums[i] == currentMax && nums[j] == currentMax) {
count++;
}
}
}
return count;
}
public static void main(String[] args) {
int[] nums = {1, 4, 3, 3, 2};
System.out.println(countSubarrays(nums)); // Output: 6
}
}function countSubarrays(nums) {
let count = 0;
const n = nums.length;
for (let i = 0; i < n; i++) {
let currentMax = nums[i];
for (let j = i; j < n; j++) {
currentMax = Math.max(currentMax, nums[j]);
if (nums[i] === currentMax && nums[j] === currentMax) {
count++;
}
}
}
return count;
}
// Example Usage
const nums = [1, 4, 3, 3, 2];
console.log(countSubarrays(nums)); // Output: 6#include <stdio.h>
int countSubarrays(int* nums, int numsSize) {
int count = 0;
for (int i = 0; i < numsSize; i++) {
int currentMax = nums[i];
for (int j = i; j < numsSize; j++) {
if (nums[j] > currentMax) {
currentMax = nums[j];
}
if (nums[i] == currentMax && nums[j] == currentMax) {
count++;
}
}
}
return count;
}
int main() {
int nums[] = {1, 4, 3, 3, 2};
int result = countSubarrays(nums, 5);
printf("%d\n", result); // Output: 6
return 0;
}using System;
class SubarrayCounter {
public static int CountSubarrays(int[] nums) {
int count = 0;
int n = nums.Length;
for (int i = 0; i < n; i++) {
int currentMax = nums[i];
for (int j = i; j < n; j++) {
currentMax = Math.Max(currentMax, nums[j]);
if (nums[i] == currentMax && nums[j] == currentMax) {
count++;
}
}
}
return count;
}
static void Main() {
int[] nums = {1, 4, 3, 3, 2};
Console.WriteLine(CountSubarrays(nums)); // Output: 6
}
}The function count_subarrays iterates over all subarray starting indices i. For each i, it iterates over all ending indices j, updating the current subarray's maximum element. If both the boundary elements of the current subarray are equal to this maximum, the subarray is counted.
Time Complexity: O(n^3), where n is the length of the array, as we compute the maximum for each subarray in a nested manner.
Space Complexity: O(1), as we are using constant space.
Approach 2: Optimized Counting Using Sliding Window
This method takes advantage of consecutive segments of the array where the maximum element appears. By counting these segments, we can efficiently determine the number of valid subarrays.
def count_subarrays_optimized(nums):
n = len(nums)
max_num = max(nums)
count = 0
i = 0
while i < n:
if nums[i] == max_num:
j = i
while j < n and nums[j] == max_num:
j += 1
length = j - i
count += (length * (length + 1)) // 2
i = j
else:
i += 1
return count
# Example Usage
nums = [1, 4, 3, 3, 2]
print(count_subarrays_optimized(nums)) # Output: 6public class SubarrayCounterOptimized {
public static int countSubarraysOptimized(int[] nums) {
int maxNum = nums[0];
for (int num : nums) {
if (num > maxNum) {
maxNum = num;
}
}
int count = 0, i = 0, n = nums.length;
while (i < n) {
if (nums[i] == maxNum) {
int j = i;
while (j < n && nums[j] == maxNum) {
j++;
}
int length = j - i;
count += (length * (length + 1)) / 2;
i = j;
} else {
i++;
}
}
return count;
}
public static void main(String[] args) {
int[] nums = {1, 4, 3, 3, 2};
System.out.println(countSubarraysOptimized(nums)); // Output: 6
}
}function countSubarraysOptimized(nums) {
const maxNum = Math.max(...nums);
let count = 0;
let i = 0;
const n = nums.length;
while (i < n) {
if (nums[i] === maxNum) {
let j = i;
while (j < n && nums[j] === maxNum) {
j++;
}
const length = j - i;
count += (length * (length + 1)) / 2;
i = j;
} else {
i++;
}
}
return count;
}
// Example Usage
const nums = [1, 4, 3, 3, 2];
console.log(countSubarraysOptimized(nums)); // Output: 6#include <stdio.h>
int countSubarraysOptimized(int* nums, int numsSize) {
int max_num = nums[0];
for (int i = 1; i < numsSize; i++) {
if (nums[i] > max_num) {
max_num = nums[i];
}
}
int count = 0, i = 0;
while (i < numsSize) {
if (nums[i] == max_num) {
int j = i;
while (j < numsSize && nums[j] == max_num) {
j++;
}
int length = j - i;
count += (length * (length + 1)) / 2;
i = j;
} else {
i++;
}
}
return count;
}
int main() {
int nums[] = {1, 4, 3, 3, 2};
int result = countSubarraysOptimized(nums, 5);
printf("%d\n", result); // Output: 6
return 0;
}using System;
class SubarrayCounterOptimized {
public static int CountSubarraysOptimized(int[] nums) {
int maxNum = nums[0];
foreach (int num in nums) {
if (num > maxNum) {
maxNum = num;
}
}
int count = 0, i = 0, n = nums.Length;
while (i < n) {
if (nums[i] == maxNum) {
int j = i;
while (j < n && nums[j] == maxNum) {
j++;
}
int length = j - i;
count += (length * (length + 1)) / 2;
i = j;
} else {
i++;
}
}
return count;
}
static void Main() {
int[] nums = {1, 4, 3, 3, 2};
Console.WriteLine(CountSubarraysOptimized(nums)); // Output: 6
}
}The count_subarrays_optimized function first determines the maximum value in the array. It then iterates through the array, counting consecutive segments of the maximum value and updates the total count using the mathematical sum formula.
Time Complexity: O(n), as we iterate through the array once.
Space Complexity: O(1), constant space is required.
Approach 3: Monotonic Stack
We consider each element x in the array nums as the boundary element and the maximum value of the subarray.
Each subarray of length 1 meets the condition, and for subarrays with length greater than 1, all elements in the subarray cannot be greater than the boundary element x. We can implement this with a monotonic stack.
We maintain a stack that decreases monotonically from the bottom to the top. Each element in the monotonic stack is a pair [x, cnt], representing the element x and the count cnt of subarrays with x as the boundary element and the maximum value.
We traverse the array nums from left to right. For each element x, we continuously pop the top element of the stack until the stack is empty or the first element of the top element of the stack is greater than or equal to x. If the stack is empty, or the first element of the top element of the stack is greater than x, it means that we have encountered the first subarray with x as the boundary element and the maximum value, and the length of this subarray is 1, so we push [x, 1] into the stack. If the first element of the top element of the stack is equal to x, it means that we have encountered a subarray with x as the boundary element and the maximum value, and we add 1 to the second element of the top element of the stack. Then, we add the second element of the top element of the stack to the answer.
After the traversal, we return the answer.
The time complexity is O(n), and the space complexity is O(n). Where n is the length of the array nums.
class Solution {
public:
long long numberOfSubarrays(vector<int>& nums) {
vector<pair<int, int>> stk;
long long ans = 0;
for (int x : nums) {
while (!stk.empty() && stk.back().first < x) {
stk.pop_back();
}
if (stk.empty() || stk.back().first > x) {
stk.push_back(make_pair(x, 1));
} else {
stk.back().second++;
}
ans += stk.back().second;
}
return ans;
}
};function numberOfSubarrays(nums: number[]): number {
const stk: number[][] = [];
let ans = 0;
for (const x of nums) {
while (stk.length > 0 && stk.at(-1)![0] < x) {
stk.pop();
}
if (stk.length === 0 || stk.at(-1)![0] > x) {
stk.push([x, 1]);
} else {
stk.at(-1)![1]++;
}
ans += stk.at(-1)![1];
}
return ans;
}func numberOfSubarrays(nums []int) (ans int64) {
stk := [][2]int{}
for _, x := range nums {
for len(stk) > 0 && stk[len(stk)-1][0] < x {
stk = stk[:len(stk)-1]
}
if len(stk) == 0 || stk[len(stk)-1][0] > x {
stk = append(stk, [2]int{x, 1})
} else {
stk[len(stk)-1][1]++
}
ans += int64(stk[len(stk)-1][1])
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(n^3), where n is the length of the array, as we compute the maximum for each subarray in a nested manner. |
| Optimized Counting Using Sliding Window | Time Complexity: O(n), as we iterate through the array once. |
| Monotonic Stack | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Enumeration | O(n^2) | O(1) | Useful for understanding the condition and validating correctness on small arrays |
| Monotonic Stack Counting | O(n) | O(n) | Best general solution for large inputs; leverages decreasing stack and equal-value counting |
Frequently asked questions
Is Find the Number of Subarrays Where Boundary Elements Are Maximum easy or hard?
LeetCode classifies this problem as Hard because recognizing the monotonic stack counting pattern is not obvious. A brute force solution is straightforward but inefficient at O(n^2). Achieving the optimal O(n) solution requires deeper understanding of stack-based array algorithms.
Find the Number of Subarrays Where Boundary Elements Are Maximum Python/Java solution
Python and Java implementations typically maintain a stack storing pairs of (value, count). While traversing the array, smaller values are popped and equal values increase the count, which contributes to the number of valid subarrays. This stack-based counting approach achieves O(n) time complexity and works efficiently for large inputs.
How to solve Find the Number of Subarrays Where Boundary Elements Are Maximum in O(n)?
Use a monotonic decreasing stack while iterating through the array. When a new element is larger than the stack top, pop smaller elements because they cannot remain maximum boundaries. If the value equals the stack top, increase a counter representing how many identical boundaries exist and add that count to the result. Each operation is constant amortized time, giving O(n) complexity.
What is the best approach for Find the Number of Subarrays Where Boundary Elements Are Maximum?
The most efficient approach uses a monotonic decreasing stack to track candidate boundary elements. While scanning the array, smaller elements are removed when a larger value appears, ensuring that the remaining elements can still act as maximum boundaries. Equal values are grouped and counted to form valid subarrays. This method runs in O(n) time with O(n) auxiliary space.
Is Find the Number of Subarrays Where Boundary Elements Are Maximum asked at Google/Amazon/Meta?
Problems involving monotonic stacks and counting subarrays with boundary constraints frequently appear in interviews at companies like Google, Amazon, and Meta. Variants include counting subarrays with maximum or minimum boundaries, next greater element patterns, and monotonic stack optimizations.
What data structure is used in Find the Number of Subarrays Where Boundary Elements Are Maximum?
The core data structure is a monotonic stack that maintains elements in decreasing order. This structure efficiently tracks candidate maximum values and removes invalid elements when larger values appear. Arrays are used for traversal while the stack enables linear-time processing.
What is the time complexity of Find the Number of Subarrays Where Boundary Elements Are Maximum?
The optimal solution runs in O(n) time because each element is pushed and popped from the monotonic stack at most once. Space complexity is O(n) for the stack used to maintain decreasing order and count equal values.