DEV Community

Cover image for 3113. Find the Number of Subarrays Where Boundary Elements Are Maximum
MD ARIFUL HAQUE
MD ARIFUL HAQUE

Posted on • Edited on

3113. Find the Number of Subarrays Where Boundary Elements Are Maximum

3113. Find the Number of Subarrays Where Boundary Elements Are Maximum

Hard

You are given an array of positive integers nums.

Return the number of subarrays1 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: [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 <= 105
  • 1 <= nums[i] <= 109

Constraints:

class Solution {

    /**
     * @param Integer[] $nums
     * @return Integer
     */
    function numberOfSubarrays($nums) {
        $stack = [];
        $res = 0;

        for ($r = 0; $r < count($nums); $r++) {
            while ($stack && $stack[count($stack) - 1][0] < $nums[$r]) {
                array_pop($stack);
            }

            if ($stack && $stack[count($stack) - 1][0] == $nums[$r]) {
                $stack[count($stack) - 1][1]++;
            } else {
                array_push($stack, [$nums[$r], 1]);
            }

            $res += $stack[count($stack) - 1][1];
        }

        return $res;
    }
}
Enter fullscreen mode Exit fullscreen mode

Contact Links
If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!


  1. A subarray is a contiguous non-empty sequence of elements within an array. 

Billboard image

Imagine monitoring that's actually built for developers

Join Vercel, CrowdStrike, and thousands of other teams that trust Checkly to streamline monitor creation and configuration with Monitoring as Code.

Start Monitoring

Top comments (0)

AWS Security LIVE!

Tune in for AWS Security LIVE!

Join AWS Security LIVE! for expert insights and actionable tips to protect your organization and keep security teams prepared.

Learn More

👋 Kindness is contagious

Discover a treasure trove of wisdom within this insightful piece, highly respected in the nurturing DEV Community enviroment. Developers, whether novice or expert, are encouraged to participate and add to our shared knowledge basin.

A simple "thank you" can illuminate someone's day. Express your appreciation in the comments section!

On DEV, sharing ideas smoothens our journey and strengthens our community ties. Learn something useful? Offering a quick thanks to the author is deeply appreciated.

Okay