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 length 3 sub arrays whose nums[1]/2 == nums[0] + nums[2]

Brute force

  • We can generate all sub arrays of length 3 O(n^2).

Match

  • Subarray ending at index i trick
  • For subarray of length 3 ending at index i we can check if condition passes in constant time.

Plan

  • check nums[0] + nums[1] == nums[2]/2 and res += 1

Implement

def countSubarrays(self, nums: List[int]) -> int:
    res = 0
    for i in range(2, len(nums)):
        res += (1 if nums[i] + nums[i-2] == nums[i-1]/2 else 0)
    return res

Review

Evaluate

  • Time complexity: O(n)