Given an array of N positive integers  Arr_{1}, Arr_{2} ............ Arr_{n}. The value of each contiguous subarray of given array is the maximum element present in that subarray. The task is to return the number of subarrays having value strictly greater than K.
Example 1:
Input:
N = 3, K = 2
Arr[] = {3, 2, 1}
Output: 3
Explanation: The subarrays having value
strictly greater than K are: [3], [3, 2]
and [3, 2, 1]. Thus there are 3 such
subarrays.
Example 2:
Input:
N = 4, K = 1
Arr[] = {1, 2, 3, 4}
Output: 9
Explanation: There are 9 subarrays having
value strictly greater than K.
Your Task:
Complete the function countSubarray() which takes an array arr, two integers n, k, as input parameters and returns an integer denoting the answer. You don't to print answer or take inputs.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)
Constraints:
1 <= N <= 10^{5}
1 <= Arr[i] <= 10^{5}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Dynamic programming

Data structures

Starter code: #User function Template for python3
class Solution:


	def countSubarray(self,arr, n, k):
	    # code here

Solutions:
class Solution:

	def countSubarray(self, arr, n, k):
		temp = 0
		ind = -1
		tot = 0
		for i in range(n):
			if arr[i] > k:
				temp = temp + i - ind
				ind = i
			tot = tot + temp
		return tot


class Solution:

	def countSubarray(self, arr, n, k):
		li = [0 for i in range(n)]
		for i in range(n):
			if arr[i] > k:
				li[i] = i + 1
			elif i != 0:
				li[i] = li[i - 1]
		return sum(li)


class Solution:

	def countSubarray(self, arr, n, k):
		ans = 0
		st = 0
		en = 0
		while st <= en:
			if arr[en] > k:
				ans += n - st + (n - en - 1) * (en - st)
				st = en + 1
			en += 1
			if en >= n:
				break
		return ans


class Solution:

	def countSubarray(self, arr, n, k):
		dp = [0 for _ in range(n)]
		if arr[0] > k:
			total = 1
			dp[0] = 1
		else:
			total = 0
			dp[0] = 0
		for i in range(1, n):
			if arr[i] > k:
				dp[i] = i + 1
				total += dp[i]
			else:
				dp[i] = dp[i - 1]
				total += dp[i]
		return total


class Solution:

	def countSubarray(self, arr, n, k):

		def maxsmallerthank(arr, n, k):
			lcount = 0
			i = 0
			while i < n:
				while i < n and arr[i] > k:
					i += 1
				cnt = 0
				while i < n and arr[i] <= k:
					cnt += 1
					i += 1
				lcount += cnt * (cnt + 1) // 2
			return lcount
		smallerEqualthank = maxsmallerthank(arr, n, k)
		total = n * (n + 1) // 2
		return total - smallerEqualthank


class Solution:

	def countSubarray(self, arr, n, k):
		(cnt, ans) = (0, n * (n + 1) // 2)
		for i in range(len(arr)):
			if arr[i] <= k:
				cnt += 1
			else:
				ans -= cnt * (cnt + 1) // 2
				cnt = 0
		return ans - cnt * (cnt + 1) // 2


class Solution:

	def countSubarray(self, arr, n, k):
		ans = 0
		bigger = -1
		for i in range(n):
			if arr[i] > k:
				ans += i + 1
				bigger = i
			elif bigger != -1:
				ans += bigger + 1
		return ans


class Solution:

	def countSubarray(self, arr, n, k):
		total = n * (n + 1) // 2
		con = 0
		for i in arr:
			if i <= k:
				con += 1
			else:
				total -= con * (con + 1) // 2
				con = 0
		total -= con * (con + 1) // 2
		return total


class Solution:

	def countSubarray(self, arr, N, K):
		ans = 0
		i = 0
		while i < N:
			if arr[i] > K:
				ans += N - i
				i += 1
			else:
				j = i + 1
				c = 0
				while j < N and arr[j] <= K:
					j += 1
					c += 1
				if j >= N:
					break
				ans += N - j
				while c > 0:
					ans += N - j
					c += -1
				i = j
		return ans


class Solution:

	def countSubarray(self, arr, n, k):
		(res, cur) = (0, 0)
		for i in range(n):
			if arr[i] <= k:
				cur += 1
				res += cur
			else:
				cur = 0
		return n * (n + 1) // 2 - res


class Solution:

	def countSubarray(self, arr, n, k):
		dp = [0] * n
		if arr[0] > k:
			dp[0] = 1
			t = 1
		c = 0
		for i in range(1, n):
			if arr[i] > k:
				dp[i] = dp[i - 1] + (i + 1)
				t = i + 1
			elif dp[i - 1] == 0:
				dp[i] = 0
			else:
				dp[i] = dp[i - 1] + t
		return dp[n - 1]


class Solution:

	def countSubarray(self, arr, n, k):
		count = 0
		temp = 0
		for i in range(n):
			curr = arr[i]
			if curr <= k:
				temp += 1
			else:
				count += (temp + 1) * (n - i)
				temp = 0
		return count


class Solution:

	def countSubarray(self, arr, n, k):
		subslessequalK = 0
		cnt = 0
		i = 0
		while i < n:
			while i < n and arr[i] > k:
				i += 1
			cnt = 0
			while i < n and arr[i] <= k:
				cnt += 1
				i += 1
			subslessequalK += cnt * (cnt + 1) // 2
		total = n * (n + 1) // 2
		return total - subslessequalK


class Solution:

	def countSubarray(self, arr, n, k):
		left = [0] * n
		stack = []
		for i in range(0, n):
			cnt = 1
			while stack and stack[-1][0] < arr[i]:
				cnt += stack[-1][1]
				stack.pop()
			left[i] = cnt
			stack.append((arr[i], cnt))
		right = [0] * n
		stack.clear()
		ans = 0
		for i in range(n - 1, -1, -1):
			cnt = 1
			while stack and stack[-1][0] <= arr[i]:
				cnt += stack[-1][1]
				stack.pop()
			right[i] = cnt
			stack.append((arr[i], cnt))
			if arr[i] > k:
				ans += left[i] * right[i]
		return ans


class Solution:

	def countSubarray(self, arr, n, k):
		total = 0
		count = 0
		for i in range(n):
			count += 1
			if arr[i] > k:
				total += count * (n - i)
				count = 0
		return total


class Solution:

	def countSubarray(self, arr, n, k):
		i = 0
		s = 0
		while i < n:
			if arr[i] > k:
				i = i + 1
				continue
			count = 0
			while i < n and arr[i] <= k:
				i = i + 1
				count += 1
			s += count * (count + 1) // 2
		return n * (n + 1) // 2 - s


class Solution:

	def countSubarray(self, a, n, k):
		l = []
		for i in range(n):
			if a[i] > k:
				l.append(i)
		r = 0
		j = 0
		m = len(l)
		for i in range(n):
			if j == m:
				break
			if i == l[j]:
				r = r + n - l[j]
				j += 1
			else:
				r = r + n - l[j]
		return r


class Solution:

	def countSubarray(self, arr, n, k):
		a = 0
		b = -1
		for i in range(n):
			if arr[i] > k:
				a += i + 1
				b = i
			elif b != -1:
				a += b + 1
		return a


class Solution:

	def countSubarray(self, arr, n, k):
		d = []
		for i in range(len(arr)):
			if arr[i] > k:
				d.append(i)
		if len(d) == 0:
			return 0
		res = (d[0] + 1) * (len(arr) - d[0])
		for i in range(1, len(d)):
			res += (d[i] - d[i - 1]) * (len(arr) - d[i])
		return res


class Solution:

	def countSubarray(self, arr, n, k):
		totsub = n * (n + 1) // 2
		less = 0
		for i in range(0, n):
			if arr[i] <= k:
				less += 1
			else:
				totsub -= less * (less + 1) // 2
				less = 0
		totsub -= less * (less + 1) // 2
		return totsub


class Solution:

	def countSubarray(self, arr, n, k):
		sub_array = n * (n + 1) / 2
		count = 0
		for i in range(n):
			if arr[i] <= k:
				count += 1
				continue
			sub_array -= count * (count + 1) / 2
			count = 0
		sub_array -= count * (count + 1) / 2
		return int(sub_array)


class Solution:

	def countSubarray(self, arr, n, k):
		count = 0
		for i in range(0, n):
			for j in range(i, n):
				if arr[j] > k:
					count += n - j
					break
		return count


class Solution:

	def countSubarray(self, arr, n, k):
		(running, ans) = (0, 0)
		for (i, e) in enumerate(arr):
			if e > k:
				ans += running * (running + 1) // 2
				running = 0
			else:
				running += 1
		else:
			ans += running * (running + 1) // 2
		return n * (n + 1) // 2 - ans


class Solution:

	def countSubarray(self, arr, n, k):
		c = 0
		s = 0
		for i in range(n):
			if arr[i] > k:
				s += (n - i) * (c + 1)
				c = 0
			else:
				c += 1
		return s


class Solution:

	def countSubarray(self, arr, n, k):
		ans = n * (n + 1) // 2
		(l, r) = (-1, -1)
		for i in range(n + 1):
			if i == n or arr[i] > k:
				if l != -1:
					ans -= (r - l + 1) * (r - l + 2) // 2
					l = -1
					r = -1
			elif l == -1:
				l = i
				r = i
			else:
				r = i
		return ans


class Solution:

	def countSubarray(self, arr, n, k):
		l = 0
		p = 0
		cout = 0
		ans = n * (n + 1) // 2
		for i in arr:
			if i <= k:
				l += 1
			else:
				ans -= l * (l + 1) // 2
				l = 0
		ans -= l * (l + 1) // 2
		return ans


class Solution:

	def countSubarray(self, arr, n, k):
		res = 0
		recent = -1
		for i in range(n):
			if arr[i] > k:
				res = res + (n - i) * (i - recent)
				recent = i
		return res


class Solution:

	def countSubarray(self, arr, n, k):
		(l, r, res) = (0, 0, 0)
		while r < n:
			if arr[r] > k:
				res += (r - l + 1) * (n - r)
				l = r + 1
			r += 1
		return res


class Solution:

	def countSubarray(self, arr, n, k):
		i = 0
		smaller = 0
		while i < n:
			curr = 0
			while i < n and arr[i] <= k:
				curr += 1
				i += 1
			smaller += curr * (curr + 1) // 2
			i += 1
		return n * (n + 1) // 2 - smaller


class Solution:

	def countSubarray(self, arr, n, k):
		as1 = 0
		ass = 0
		for i in range(0, n):
			if arr[i] > k:
				as1 += i + 1
				ass = i + 1
			else:
				as1 += ass
		return as1


class Solution:

	def countSubarray(self, arr, n, k):
		ans = n * (n + 1) // 2
		l = 0
		for v in arr:
			if v <= k:
				l += 1
			else:
				ans -= l * (l + 1) // 2
				l = 0
		ans -= l * (l + 1) // 2
		return ans


class Solution:

	def countSubarray(self, arr, n, k):
		total = n * (n + 1) // 2
		ans = 0
		i = 0
		while i < n:
			if arr[i] > k:
				i += 1
				continue
			count = 0
			while i < n and arr[i] <= k:
				count += 1
				i += 1
			val = count * (count + 1) // 2
			ans += val
		return total - ans


class Solution:

	def countSubarray(self, arr, n, k):
		ans = 0
		prev = 0
		for i in range(n):
			if arr[i] > k:
				ans += 1 + i
				prev = i + 1
			else:
				ans += prev
		return ans


class Solution:

	def countSubarray(self, arr, n, k):
		le = len(arr)
		ans = le * (le + 1) / 2
		l = 0
		for i in arr:
			if i <= k:
				l += 1
			else:
				ans -= l * (l + 1) / 2
				l = 0
		ans -= l * (l + 1) / 2
		return int(ans)


class Solution:

	def countSubarray(self, arr, n, k):
		me = [-1]
		nsarr = 0
		for i in range(n):
			if arr[i] > k:
				me.append(i)
		for i in range(1, len(me)):
			nsarr += (me[i] - me[i - 1]) * (n - me[i])
		return nsarr


class Solution:
	from sortedcontainers import SortedList

	def countSubarray(self, arr, n, k):
		ans = 0
		c = 0
		for i in range(n):
			if arr[i] <= k:
				c += 1
			else:
				ans += c * (c + 1) // 2
				c = 0
		if c:
			ans += c * (c + 1) // 2
		return n * (n + 1) // 2 - ans


class Solution:

	def countSubarray(self, arr, n, k):
		nofsubarrays = n * (n + 1) // 2
		count = 0
		ans = 0
		for v in arr:
			if v <= k:
				count += 1
			elif count >= 1:
				ans = ans + count * (count + 1) // 2
				count = 0
		ans = ans + count * (count + 1) // 2
		return nofsubarrays - ans


class Solution:

	def countSubarray(self, arr, n, k):
		last_index = -1
		ans = 0
		for (i, v) in enumerate(arr):
			if v > k:
				ans += (i - last_index) * (n - i)
				last_index = i
		return ans


class Solution:

	def countSubarray(self, arr, n, k):
		ans = 0
		x = -1
		for i in range(n):
			if arr[i] > k:
				ans += 1
				r = n - 1 - i
				l = i - (x + 1)
				ans += r
				ans += l
				ans += r * l
				x = i
		return ans


class Solution:

	def countSubarray(self, arr, n, k):
		count = n * (n + 1) / 2
		l = 0
		for el in arr:
			if el <= k:
				l += 1
			else:
				count -= l * (l + 1) / 2
				l = 0
		count -= l * (l + 1) / 2
		return int(count)


class Solution:

	def countSubarray(self, arr, n, k):
		idx = 0
		c = 0
		for i in range(len(arr)):
			if arr[i] > k:
				idx = i + 1
			c += idx
		return c


class Solution:

	def countSubarray(self, arr, n, k):
		combinations = n * (n + 1) / 2
		count = 0
		for i in range(n):
			if arr[i] <= k:
				count += 1
			else:
				combinations -= count * (count + 1) / 2
				count = 0
		combinations -= count * (count + 1) / 2
		return int(combinations)


class Solution:

	def countSubarray(self, arr, n, k):
		left_idx = 0
		total_count = 0
		for i in range(n):
			if arr[i] > k:
				total_count += i + 1
				left_idx = i + 1
			else:
				total_count += i + 1
				total_count -= i + 1 - left_idx
		return total_count