<p>You are given an integer array <code>nums</code> and a <strong>positive</strong> integer <code>k</code>.</p>

<p>Return <em>the number of subarrays where the <strong>maximum</strong> element of </em><code>nums</code><em> appears <strong>at least</strong> </em><code>k</code><em> times in that subarray.</em></p>

<p>A <strong>subarray</strong> is a contiguous sequence of elements within an array.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,3,2,3,3], k = 2
<strong>Output:</strong> 6
<strong>Explanation:</strong> The subarrays that contain the element 3 at least 2 times are: [1,3,2,3], [1,3,2,3,3], [3,2,3], [3,2,3,3], [2,3,3] and [3,3].
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,4,2,1], k = 3
<strong>Output:</strong> 0
<strong>Explanation:</strong> No subarray contains the element 4 at least 3 times.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= nums[i] &lt;= 10<sup>6</sup></code></li>
	<li><code>1 &lt;= k &lt;= 10<sup>5</sup></code></li>
</ul>

#include <climits>
#include <vector>

class Solution {
 public:
  long long countSubarrays(std::vector<int>& nums, int k) {
    // Constraints:
    // - k is never smaller than 1.
    // - nums is never empty.
    // Traverse to find largest number.
    int largestNumber = INT_MIN;
    int numOccurances = 0;
    const size_t length = nums.size();
    for (size_t index = 0; index < length; ++index) {
      const int number = nums[index];
      if (number > largestNumber) {
        largestNumber = number;
        numOccurances = 0;
      }
      if (number == largestNumber) {
        ++numOccurances;
      }
    }

    if (numOccurances < k) {
      return 0;
    }

    // Traverse again and store index of occurences into vector.
    std::vector<size_t> occurances;
    occurances.reserve(numOccurances);
    for (size_t index = 0; index < length; ++index) {
      if (nums[index] == largestNumber) {
        occurances.push_back(index);
      }
    }

    // Compute all possible combinations based on these indices.
    long long totalPossibilities = 0;
    // How far we've iterated through the occurances.
    size_t kIndex = 0;
    // Index of first occurance to the right of the current position.
    size_t firstRightOccurance = occurances[kIndex];
    // Index of first + k - 1 occurance to the right of the current position. This index must be included in a subarray for it to be valid.
    size_t kthRightOccurance = occurances[kIndex + k - 1];
    // Index of the last possible start of a subarray, all subarrays after that will not contain at least k occurances.
    const size_t lastPossibleStart = occurances[numOccurances - k];
    // Walk through all array elements. (Not the optimal solution. It should be possible (and relatively easy) to just iterate over the occurances as those are the only indices at which the num of possibilities changes).
    for (size_t currentStart = 0; currentStart <= lastPossibleStart; ++currentStart) {
      if (currentStart > firstRightOccurance) {
        ++kIndex;
        firstRightOccurance = occurances[kIndex];
        kthRightOccurance = occurances[kIndex + k - 1];
      }

      const long long possibilites = length - kthRightOccurance;
      totalPossibilities += possibilites;
    }

    return totalPossibilities;
  }
};
123800