Given an array of integers arr and two integers k and threshold.
Return the number of sub-arrays of size k and average greater than or equal to threshold.
 
Example 1:
Input: arr = [2,2,2,2,5,5,5,8], k = 3, threshold = 4
Output: 3
Explanation: Sub-arrays [2,5,5],[5,5,5] and [5,5,8] have averages 4, 5 and 6 respectively. All other sub-arrays of size 3 have averages less than 4 (the threshold).

Example 2:
Input: arr = [1,1,1,1,1], k = 1, threshold = 0
Output: 5

Example 3:
Input: arr = [11,13,17,23,29,31,7,5,2,3], k = 3, threshold = 5
Output: 6
Explanation: The first 6 sub-arrays of size 3 have averages greater than 5. Note that averages are not integers.

Example 4:
Input: arr = [7,7,7,7,7,7,7], k = 7, threshold = 7
Output: 1

Example 5:
Input: arr = [4,4,4,4], k = 4, threshold = 1
Output: 1

 
Constraints:

1 <= arr.length <= 10^5
1 <= arr[i] <= 10^4
1 <= k <= arr.length
0 <= threshold <= 10^4

Source: leetcode | Difficulty: MEDIUM
Tags: Data structures

Amortized analysis

Starter code: class Solution:
    def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
        

Solutions:
class Solution:

	def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
		if len(arr) < k:
			return 0
		bar = k * threshold
		total = 0
		window = sum(arr[:k])
		if window >= bar:
			total += 1
		for i in range(k, len(arr)):
			window -= arr[i - k]
			window += arr[i]
			if window >= bar:
				total += 1
		return total


class Solution:

	def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
		s = threshold * k
		s1 = sum(arr[:k])
		n = len(arr)
		c = 0
		if s1 >= s:
			c += 1
		for i in range(k, n):
			s1 -= arr[i - k]
			s1 += arr[i]
			if s1 >= s:
				c += 1
		return c


class Solution:

	def numOfSubarrays(self, nums: List[int], k: int, target: int) -> int:
		target *= k
		ans = 0
		summ = 0
		for (i, n) in enumerate(nums):
			if i >= k:
				summ -= nums[i - k]
			summ += n
			if i >= k - 1:
				if summ >= target:
					ans += 1
		return ans


class Solution:

	def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
		minVal = k * threshold
		beg = 0
		end = k - 1
		total = 0
		currSum = 0
		for i in range(beg, end + 1):
			currSum += arr[i]
		while end < len(arr):
			if beg != 0:
				currSum = currSum - arr[beg - 1] + arr[end]
			if currSum >= minVal:
				total += 1
			beg += 1
			end += 1
		return total


class Solution:

	def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
		cur = 0
		res = 0
		for i in range(k):
			cur += arr[i]
		if cur / k >= threshold:
			res += 1
		for i in range(k, len(arr)):
			cur = cur + arr[i] - arr[i - k]
			if cur / k >= threshold:
				res += 1
		return res


class Solution:

	def numOfSubarrays(self, a: List[int], k: int, threshold: int) -> int:
		prefixSum = [0]
		for i in a:
			prefixSum.append(i + prefixSum[-1])
		return sum((prefixSum[i + k] - prefixSum[i] >= k * threshold for i in range(len(a) - k + 1)))


class Solution:

	def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
		start = 0
		end = k
		count = 0
		sumInit = sum(arr[start:end])
		if sumInit / k >= threshold:
			count += 1
		while end < len(arr):
			sumInit = sumInit - arr[start] + arr[end]
			if sumInit / k >= threshold:
				count += 1
			start += 1
			end += 1
		return count


class Solution:

	def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
		if len(arr) < k:
			return 0
		prevAverage = 0
		counter = 0
		for i in range(len(arr) - k + 1):
			if i == 0:
				average = sum(arr[i:i + k]) / k
			else:
				average = (prevAverage * k - arr[i - 1] + arr[i + k - 1]) / k
			if average >= threshold:
				counter += 1
			prevAverage = average
		return counter


class Solution:

	def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
		start = 0
		count = 0
		threshold = threshold * k
		avg = sum(arr[start:k])
		i = k
		while i <= len(arr):
			if start != 0:
				avg = avg - arr[start - 1] + arr[i - 1]
			if avg >= threshold:
				count += 1
				start += 1
				i = start + k
			else:
				start += 1
				i += 1
		return count


class Solution:

	def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
		(i, j) = (0, k - 1)
		total = sum(arr[i:j + 1])
		target = threshold * k
		res = 0
		if total >= target:
			res += 1
		while j < len(arr) - 1:
			total -= arr[i]
			i += 1
			j += 1
			total += arr[j]
			if total >= target:
				res += 1
		return res


class Solution:

	def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
		dp = [0] * len(arr)
		dp[0] = arr[0]
		for i in range(1, len(arr)):
			dp[i] = dp[i - 1] + arr[i]
		cn = 0
		for i in range(k - 1, len(arr)):
			if i == k - 1:
				if dp[i] // k >= threshold:
					cn += 1
			elif (dp[i] - dp[i - k]) // k >= threshold:
				cn += 1
		return cn


class Solution:

	def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
		target = k * threshold
		curr_sum = sum(arr[:k])
		res = 1 if curr_sum >= target else 0
		for i in range(k, len(arr)):
			curr_sum = curr_sum - arr[i - k] + arr[i]
			if curr_sum >= target:
				res += 1
		return res


class Solution:

	def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
		c = 0
		a = 0
		f = 0
		for i in range(len(arr)):
			a = a + 1
			c = c + arr[i]
			if a >= k:
				if c / k >= threshold:
					f = f + 1
				c = c - arr[i - a + 1]
				a = a - 1
		return f


class Solution:

	def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
		size = len(arr)
		avg = sum(arr[:k]) / k
		count = 1 if avg >= threshold else 0
		end = k
		while end < size:
			prevVal = arr[end - k] / k
			nextVal = arr[end] / k
			avg += nextVal - prevVal
			count += 1 if avg >= threshold else 0
			end += 1
		return count


class Solution:

	def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
		total = sum(arr[:k])
		result = 0
		for i in range(k, len(arr) + 1):
			avg = total / k
			if avg >= threshold:
				result += 1
			if i < len(arr):
				left = arr[i - k]
				right = arr[i]
				total -= left
				total += right
		return result


class Solution:

	def numOfSubarrays(self, arr: List[int], k: int, t: int) -> int:
		cur = 0
		ans = 0
		for i in range(len(arr)):
			cur += arr[i]
			if i >= k:
				cur -= arr[i - k]
			if i >= k - 1 and cur >= k * t:
				ans += 1
		return ans


class Solution:

	def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
		presum = [0]
		for num in arr:
			presum.append(presum[-1] + num)
		res = 0
		i = 0
		while i + k < len(presum):
			if presum[i + k] - presum[i] >= threshold * k:
				res += 1
			i += 1
		return res


class Solution:

	def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
		(ans, sm) = (0, 0)
		q = deque()
		for v in arr:
			sm += v
			q.append(v)
			if len(q) > k:
				sm -= q.popleft()
			if len(q) == k:
				ans += sm / k >= threshold
		return ans


class Solution:

	def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
		if not arr or len(arr) < k:
			return 0
		summ = [0]
		res = 0
		for (p, v) in enumerate(arr):
			i = p + 1
			summ.append(summ[p] + v)
			if i - k >= 0:
				if (summ[i] - summ[i - k]) / k >= threshold:
					res += 1
		return res


class Solution:

	def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
		rep = 0
		target = k * threshold
		cur = sum(arr[:k])
		if cur >= target:
			rep += 1
		(l, r) = (0, k)
		while r < len(arr):
			cur -= arr[l]
			cur += arr[r]
			l += 1
			r += 1
			if cur >= target:
				rep += 1
		return rep


class Solution:

	def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
		answer = 0
		initial_sum = sum(arr[:k])
		for i in range(len(arr) - k + 1):
			if i == 0:
				if initial_sum / k >= threshold:
					answer += 1
			else:
				initial_sum = initial_sum - arr[i - 1] + arr[i + k - 1]
				if initial_sum / k >= threshold:
					answer += 1
		return answer


class Solution:

	def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
		threshold *= k
		window = 0
		ans = 0
		for (r, num) in enumerate(arr):
			window += num
			if r >= k:
				window -= arr[r - k]
			if r >= k - 1 and window >= threshold:
				ans += 1
		return ans


class Solution:

	def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
		ans = 0
		n = len(arr)
		start = 0
		end = 0
		presum = [0]
		for num in arr:
			presum.append(presum[-1] + num)
		for i in range(0, n - k + 1):
			if (presum[i + k] - presum[i]) / k >= threshold:
				ans += 1
		return ans


class Solution:

	def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
		if len(arr) < k:
			return None
		k_sum = sum([arr[i] for i in range(0, k)])
		count = 0
		(p1, p2) = (0, k)
		if k_sum / k >= threshold:
			count += 1
		while p2 < len(arr):
			k_sum = k_sum - arr[p1] + arr[p2]
			if k_sum / k >= threshold:
				count += 1
			p1 += 1
			p2 += 1
		return count


class Solution:

	def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
		sm = threshold * k
		ct = 0
		tot = 0
		for i in range(len(arr)):
			tot += arr[i]
			if i < k - 1:
				continue
			if i > k - 1:
				tot -= arr[i - k]
			if tot >= sm:
				ct += 1
		return ct


class Solution:

	def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
		n = len(arr)
		a = [0] * (n + 1)
		for i in range(1, n + 1):
			a[i] = arr[i - 1] + a[i - 1]
		cnt = 0
		for i in range(k, n + 1):
			res = a[i] - a[i - k]
			if res / k >= threshold:
				cnt += 1
		return cnt


class Solution:

	def __init__(self):
		self.counter = 0
		self.threshold = 0
		self.k = 0

	def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
		self.k = k
		self.threshold = threshold
		interval = sum(arr[:k])
		self._count_if_slice_sum_passes_threshold(interval)
		left = 0
		while left + k < len(arr):
			interval -= arr[left]
			left += 1
			right = left + k - 1
			interval += arr[right]
			self._count_if_slice_sum_passes_threshold(interval)
		return self.counter

	def _count_if_slice_sum_passes_threshold(self, slice):
		if slice / self.k >= self.threshold:
			self.counter += 1


class Solution:

	def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
		temp = sum(arr[:k])
		count = 0 if temp / k < threshold else 1
		for i in range(k, len(arr)):
			temp = temp - arr[i - k] + arr[i]
			if temp / k >= threshold:
				count += 1
		return count


class Solution:

	def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
		s = l = 0
		for r in range(k):
			s += arr[r]
		ans = 0
		while r < len(arr) - 1:
			if s >= threshold * k:
				ans += 1
			s -= arr[l]
			l += 1
			r += 1
			s += arr[r]
		ans += s >= threshold * k
		return ans


class Solution:

	def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
		ans = 0
		x = 0
		running_sum = sum(arr[0:k])
		if running_sum / k >= threshold:
			ans += 1
		for x in range(len(arr) - k):
			running_sum += arr[k + x] - arr[x]
			if running_sum / k >= threshold:
				ans += 1
		return ans


class Solution:

	def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
		averages = []
		first = True
		sum_avg = 0
		for i in range(len(arr) - (k - 1)):
			if first:
				for j in range(k):
					sum_avg += arr[i + j]
				first = False
			else:
				sum_avg -= arr[i - 1]
				sum_avg += arr[i + (k - 1)]
			averages.append(sum_avg / k)
		averages.sort(reverse=True)
		i = 0
		while i < len(averages) and averages[i] >= threshold:
			i += 1
		return i


class Solution:

	def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
		(l, r) = (0, k - 1)
		temp = 0
		for i in range(l, r + 1):
			temp += arr[i]
		res = 0 if temp < k * threshold else 1
		while r < len(arr) - 1:
			temp += arr[r + 1] - arr[l]
			r += 1
			l += 1
			if temp >= k * threshold:
				res += 1
		return res


class Solution:

	def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
		l = 0
		r = k - 1
		total = sum(arr[0:k])
		if total / k >= threshold:
			count = 1
		else:
			count = 0
		while r < len(arr) - 1:
			total -= arr[l]
			l += 1
			r += 1
			total += arr[r]
			if total / k >= threshold:
				count += 1
		return count


class Solution:

	def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
		i = 0
		j = i + k
		s = sum(arr[i:j])
		c = 0
		while j <= len(arr):
			if s // k >= threshold:
				c += 1
			s -= arr[i]
			if j < len(arr):
				s += arr[j]
			j += 1
			i += 1
		return c


class Solution:

	def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
		ans = 0
		total = 0
		if len(arr) < k:
			return 0
		else:
			for i in range(k):
				total += arr[i]
			if float(total / k) >= threshold:
				ans += 1
			i = k
			while i < len(arr):
				total += arr[i] - arr[i - k]
				if float(total / k) >= threshold:
					ans += 1
				i += 1
			return ans


class Solution:

	def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
		if len(arr) < k:
			return 0
		store = [0] * len(arr)
		i = 0
		j = 0
		ans = 0
		while i < len(arr):
			if i - j + 1 == k:
				if j == 0:
					store[i] = store[i - 1] + arr[i]
				else:
					store[i] = store[i - 1] + arr[i] - arr[j - 1]
				if store[i] // k >= threshold:
					ans = ans + 1
				j = j + 1
				i = i + 1
			else:
				if i == 0:
					store[i] = arr[i]
				else:
					store[i] = arr[i] + store[i - 1]
				i = i + 1
		return ans


class Solution:

	def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
		goal = k * threshold
		cSums = [0 for i in arr]
		c = 0
		for i in range(len(arr)):
			if i == 0:
				cSums[0] = arr[0]
			else:
				cSums[i] = cSums[i - 1] + arr[i]
			if i == k - 1:
				if cSums[i] >= goal:
					c += 1
			elif i >= k:
				if cSums[i] - cSums[i - k] >= goal:
					c += 1
		print(cSums)
		return c


class Solution:

	def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
		sumThreshold = k * threshold
		arrLength = len(arr)
		currentSum = 0
		for i in range(k):
			currentSum += arr[i]
		count = 0
		if currentSum >= sumThreshold:
			count += 1
		for i in range(k, arrLength):
			currentSum += arr[i] - arr[i - k]
			if currentSum >= sumThreshold:
				count += 1
		return count


class Solution:

	def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
		s = 0
		ret = 0
		for (i, num) in enumerate(arr):
			if i - k < 0:
				s += num
				if s >= threshold * k and i == k - 1:
					ret += 1
					print(i)
				continue
			s -= arr[i - k]
			s += num
			if s >= threshold * k:
				ret += 1
				print(i)
		return ret


class Solution:

	def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
		output = 0
		summ = 0
		for i in range(k):
			summ += arr[i]
		if summ / k >= threshold:
			output += 1
		for i in range(k, len(arr)):
			summ = summ + arr[i] - arr[i - k]
			if summ / k >= threshold:
				output += 1
		return output


class Solution:

	def numOfSubarrays(self, a: List[int], k: int, threshold: int) -> int:
		(lo, sum_of_win, cnt, target) = (-1, 0, 0, k * threshold)
		for (hi, v) in enumerate(a):
			sum_of_win += v
			if hi - lo == k:
				if sum_of_win >= target:
					cnt += 1
				lo += 1
				sum_of_win -= a[lo]
		return cnt


class Solution:

	def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
		res = 0
		s = sum(arr[:k - 1])
		t = threshold * k
		for i in range(k - 1, len(arr)):
			s += arr[i]
			if s >= t:
				res += 1
			s -= arr[i + 1 - k]
		return res


class Solution:

	def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
		target = k * threshold
		(s, ans) = (0, 0)
		for (i, num) in enumerate(arr):
			if i < k:
				s += num
				continue
			if s >= target:
				ans += 1
			s = s - arr[i - k] + arr[i]
		if s >= target:
			ans += 1
		return ans


class Solution:

	def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
		tmp = [sum(arr[:k])]
		for i in range(k, len(arr)):
			temp = tmp[-1]
			temp = temp - arr[i - k] + arr[i]
			tmp.append(temp)
		print(tmp)
		count = 0
		for el in tmp:
			if el / k >= threshold:
				count += 1
		return count


class Solution:

	def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
		threshold *= k
		n = len(arr)
		l = 0
		tmp_sum = 0
		count = 0
		for i in range(k):
			tmp_sum += arr[i]
		if tmp_sum >= threshold:
			count += 1
		for l in range(n - k):
			tmp_sum -= arr[l]
			r = l + k
			tmp_sum += arr[r]
			if tmp_sum >= threshold:
				count += 1
		return count


class Solution:

	def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
		l = len(arr)
		ans = 0
		x = 0
		running_sum = sum(arr[0:k])
		if running_sum / k >= threshold:
			ans += 1
		while k + x < l:
			running_sum += arr[k + x] - arr[x]
			if running_sum / k >= threshold:
				ans += 1
			x += 1
		return ans


class Solution:

	def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
		curr = sum(arr[:k])
		ans = 1 if curr >= threshold * k else 0
		for i in range(k, len(arr)):
			curr += arr[i]
			curr -= arr[i - k]
			if curr >= threshold * k:
				ans += 1
		return ans


class Solution:

	def numOfSubarrays(self, A, k, target):
		target *= k
		s = 0
		for i in range(k):
			s += A[i]
		res = 1 if s >= target else 0
		for i in range(len(A) - k):
			s += -A[i] + A[i + k]
			res += 1 if s >= target else 0
		return res


class Solution:

	def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
		start = 0
		s = 0
		count = 0
		for end in range(len(arr)):
			s = s + arr[end]
			if end - start + 1 == k:
				if s / k >= threshold:
					count += 1
				s -= arr[start]
				start += 1
		return count


class Solution:

	def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
		(l, r) = (0, k - 1)
		res = 0
		s = sum(arr[:k])
		t = threshold * k
		while r < len(arr):
			if s >= t:
				res += 1
			if r + 1 < len(arr):
				s = s - arr[l] + arr[r + 1]
			l += 1
			r += 1
		return res


class Solution:

	def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
		total = 0
		subarray = 0
		for i in range(k):
			subarray += arr[i]
		average = subarray / k
		if average >= threshold:
			total += 1
		for i in range(len(arr) - k):
			subarray = subarray - arr[i] + arr[i + k]
			average = subarray / k
			if average >= threshold:
				total += 1
		return total


class Solution:

	def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
		(res, curr) = (0, 0)
		for (i, v) in enumerate(arr):
			curr += v
			if i >= k:
				curr -= arr[i - k]
			if i >= k - 1 and curr / k >= threshold:
				res += 1
		return res


class Solution:

	def numOfSubarrays(self, arr, k, threshold) -> int:
		s = 0
		sub = arr[0:k]
		subSum = sum(sub)
		avg = subSum / k
		if avg >= threshold:
			s += 1
		i = k
		j = 0
		while i < len(arr):
			subSum += arr[i]
			subSum -= arr[j]
			j += 1
			i += 1
			avg = subSum / k
			if avg >= threshold:
				s += 1
		return s


class Solution:

	def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
		answer = 0
		avg = average(arr[0:k])
		prev_el = arr[0]
		if avg >= threshold:
			answer += 1
		for i in range(k, len(arr)):
			new_avg = (avg * k - prev_el + arr[i]) / k
			if new_avg >= threshold:
				answer += 1
			avg = new_avg
			prev_el = arr[i - k + 1]
		return answer

def average(l):
	return sum(l) / len(l)