Frontend School

Dominant Subarray Sum

DSA
hard

Dominant Subarray Sum

Hard
Arrays
Monotonic Stack
Prefix Sum

Overview

In many data analysis scenarios, identifying influential segments within a sequence is crucial. Consider an array of numerical values representing, for instance, daily stock prices or sensor readings. We define a 'dominant subarray' as a contiguous segment where there exists exactly one element that is strictly greater than all other elements within that segment. This unique maximum element is called the 'dominant element', and its value defines the score of that dominant subarray.

Your task is to calculate the sum of scores of all possible dominant subarrays within a given input array. This problem challenges your ability to efficiently identify and aggregate contributions from specific substructures in an array, a common pattern in optimizing algorithmic solutions.

What you need to do / Task

Implement the function dominantSubarraySum that takes an array of integers nums and returns the total sum of scores of all dominant subarrays.

Input & output

  • Input: nums: number[]
    • An array of integers.
  • Output: number
    • The sum of scores of all dominant subarrays.

Clarifications

  • Empty input: If nums is empty, the sum of scores should be 0.
  • Single element array: An array [X] has one dominant subarray [X] with score X.
  • Large sum: The total sum can be very large. Consider the implications for your chosen language's number type (e.g., long long in C++, BigInt in JavaScript/TypeScript if necessary). The final result should be returned as a standard number type if possible, otherwise note the overflow potential.

Examples

1

Example 1

Input:

nums = [1, 3, 2]

Output:

15

Note:

Dominant subarrays and their scores:

  • [1]: dominant element 1, score 1
  • [3]: dominant element 3, score 3
  • [2]: dominant element 2, score 2
  • [1, 3]: dominant element 3, score 3
  • [3, 2]: dominant element 3, score 3
  • [1, 3, 2]: dominant element 3, score 3 Total sum = 1 + 3 + 2 + 3 + 3 + 3 = 15.
2

Example 2

Input:

nums = [3, 1, 3]

Output:

13

Note:

Dominant subarrays and their scores:

  • [3] (at index 0): dominant element 3, score 3
  • [1]: dominant element 1, score 1
  • [3] (at index 2): dominant element 3, score 3
  • [3, 1] (dominant element at index 0): dominant element 3, score 3
  • [1, 3] (dominant element at index 2): dominant element 3, score 3 Note that [3, 1, 3] is NOT a dominant subarray because there are two elements (nums[0] and nums[2]) that are equal to the maximum value (3), thus no single strictly greater dominant element. Total sum = 3 + 1 + 3 + 3 + 3 = 13.
3

Example 3

Input:

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

Output:

104

Note:

This example showcases how elements like 6 (at index 4) have a wide range of influence. The logic must correctly account for all valid dominant subarrays.

Constraints

Constraints & assumptions

  • 1 <= nums.length <= 10^5
  • 0 <= nums[i] <= 10^9
  • The sum of scores can exceed 2^31 - 1, and potentially 2^53 - 1.

What interviewers evaluate

  • Algorithmic Correctness: The solution must correctly identify all dominant subarrays and sum their scores, especially handling edge cases and duplicate values according to the problem's strict definition.
  • Time Efficiency: The solution should process the input array in linear time, O(N), where N is the length of nums.
  • Space Efficiency: The solution should use linear space, O(N), for auxiliary data structures.
  • Code Quality: Demonstrated ability to write clean, readable, and well-structured code with appropriate variable naming.

Loading editor...