Problem Description

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.

Intuition

To solve the problem, we use a monotonic stack approach. The key observation is that for any valid subarray, the first and last elements should be the maximum in the subarray.

Here's the step-by-step intuition:

1. Understanding Subarrays: For a subarray to meet the condition, both the first and last elements must be the same and equal to the largest element within that subarray.

2. Using a Stack: We utilize a stack to keep track of potential subarrays starting from each element. For every element x in nums, we determine how many subarrays it can start that satisfy the condition. The stack helps in efficiently determining these boundaries.

3. Maintaining Monotonic Stack: The stack is maintained in a decreasing order of elements. This ensures that when a new element x is processed, it will either start a new subarray or join an existing set of subarrays at the top of the stack which already ends at an equivalent value x.

4. Counting Subarrays: Each time a new element x is processed:

   • If x is greater than the elements currently on the stack, we pop these elements until the stack is either empty or contains greater elements.
   • If x is equal to the top of the stack, we increment the count of subarrays for this element.
   • Every new or processed cumulative count from the stack top contributes to the answer.

By iterating through the array and applying the above principles, we efficiently calculate the number of valid subarrays matching the condition, optimizing time complexity compared to a direct approach.

Learn more about Stack, Binary Search and Monotonic Stack patterns.

Solution Approach

Monotonic Stack

To efficiently solve the problem, we employ a Monotonic Stack technique. This approach leverages a data structure that maintains stack elements in a monotonically decreasing order, greatly aiding in determining valid subarray boundaries.

Here's a detailed breakdown of the implementation:

1. Initialize the Stack and Counter:

   • We start by initializing an empty stack stk to store arrays [x, cnt], where x is an element from nums and cnt is the count of valid subarrays starting with x.
   • We also initialize an integer ans to accumulate the total count of valid subarrays.

2. Iterate Over Each Element:

   • For each element x in nums, we examine whether it can form subarrays or extend existing ones in the stack.

3. Maintain Stack Property:

   • While the stack is not empty and the current element x is greater than the top element of the stack, we pop the stack since our new element could form a larger boundary.
   • If x is less than or equal to the top element, determine its position in the stack:
     • If the stack is empty or x is less than the current top, it's treated as a new boundary initiating with a count 1: stk.append([x, 1]).
     • If x equals the top boundary, it extends those subarrays, so increment the count at the top of the stack: stk[-1][1] += 1.

4. Update the Answer:

   • Accumulate the count stk[-1][1] to ans after processing each element, reflecting all valid subarrays ending in x.

5. Return Total Count:

   • Once we've iterated through nums, ans holds the total number of valid subarrays sought in the problem.

This approach ensures that we always process new elements and adapt the stack efficiently, achieving better performance than brute force methods.

Example Walkthrough

Let's illustrate the solution approach with a small example. Consider the array nums = [2, 1, 3, 3, 1].

Step-by-step Explanation:

1. Initialization:

   • We start with an empty stack stk = [] and a total count ans = 0.

2. Process each element in nums:

   • Element 2:

     • The stack is empty, so we add [2, 1] to denote the start of subarrays with 2.
     • Stack: [[2, 1]]
     • Update ans += 1, now ans = 1.

   • Element 1:

     • Since 1 is less than 2 (the top of the stack), we consider it as a new subarray start.
     • Push [1, 1] onto the stack.
     • Stack: [[2, 1], [1, 1]]
     • Update ans += 1, now ans = 2.

   • Element 3:

     • It is greater than both 1 and 2, so we pop both elements from the stack.
     • Stack becomes empty and [3, 1] is added as a new subarray start.
     • Stack: [[3, 1]]
     • Update ans += 1, now ans = 3.

   • Second Element 3:

     • The top of the stack is 3, equal to the current element.
     • Therefore, we increment the count: stk[-1][1] += 1.
     • Stack: [[3, 2]]
     • Update ans += 2, now ans = 5 (as there are two subarrays: [3], [3, 3]).

   • Element 1:

     • This element is less than 3 on the stack.
     • Push [1, 1] onto the stack as a new boundary.
     • Stack: [[3, 2], [1, 1]]
     • Update ans += 1, now ans = 6.

3. Final Result:

   • After processing all elements, ans = 6, which is the number of subarrays fulfilling the condition.

This thorough breakdown demonstrates how each element is processed to identify valid subarrays efficiently using a monotonic stack.

Solution Implementation

Time and Space Complexity

The time complexity of the code is O(n), where n is the length of the array nums. This is because each element is processed at most twice - once when it is added to the stack and possibly once again if later removed due to a smaller element being encountered.

The space complexity is O(n) as well, given that in the worst-case scenario (for instance, when the array is in decreasing order), all the elements might end up on the stack simultaneously resulting in a stack size proportional to n.

Learn more about how to find time and space complexity quickly.