UMPIRE
- [U]nderstand the problem, ask questions and come up with corner test cases.
- [M]atch the leetcode pattern
- [P]lan to using pattern template and data structures
- [I]mplement the code
- [R]eview by running the example and corner test cases
- [E]valuate time and space complexity

Understand

  • return number of sub arrays that max element atleast k times

Brute force

  • Generate all sub arrays, count mx element. O(n^2)

Match

  • Sliding window
  • Grow till max_cnt equals k

Plan

  • Grow till max_cnt equals k say i
  • Once k then all the sub arrays that end with i+1, i+2 .. len(nums) are also valid sub arrays. res += (len(nums) - right)
  • Shrink till max_cnt is less k. During shrink every sub array starting at left if max_cnt satisfied. res += (len(nums) - right)

Implement

res = 0
mx = max(nums)
left = 0
freq = 0
for right in range(len(nums)):
    freq += (1 if nums[right] == mx else 0)
    if freq == k:
        res += (len(nums) - right)
    while freq == k:
        freq -= (1 if nums[left] == mx else 0)
        left += 1
        if freq == k:
            res += (len(nums) - right)
return res

res = 0
mx = max(nums)
left = 0
freq = 0
for right in range(len(nums)):
    freq += (1 if nums[right] == mx else 0)
    while freq == k:
        res += (len(nums) - right)
        freq -= (1 if nums[left] == mx else 0)
        left += 1
return res

Review

Evaluate

  • Time complexity: O(n)