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. 

Image of Timescale

Timescale – the developer's data platform for modern apps, built on PostgreSQL

Timescale Cloud is PostgreSQL optimized for speed, scale, and performance. Over 3 million IoT, AI, crypto, and dev tool apps are powered by Timescale. Try it free today! No credit card required.

Try free

Top comments (0)

A Workflow Copilot. Tailored to You.

Pieces.app image

Our desktop app, with its intelligent copilot, streamlines coding by generating snippets, extracting code from screenshots, and accelerating problem-solving.

Read the docs

👋 Kindness is contagious

Please leave a ❤️ or a friendly comment on this post if you found it helpful!

Okay