You are given an array A of N integers and an integer K, and your task is to find the total number of cuts that you can make such that for each cut these two conditions are satisfied
1. A cut divides an array into two parts equal or unequal length (non-zero).
2. Sum of the largest element in the left part and the smallest element in the right part is greater than or equal to K.
Example 1:
Input:
N=3
K=3
A[]={1,2,3}
Output:
2
Explanation:
Two ways in which array is divided to satisfy above conditions are:
{1} and {2,3} -> 1+2>=3(satisfies the condition)
{1,2} and {3} -> 2+3>=3(satisfies the condition)
Example 2:
Input:
N=5
K=5
A[]={1,2,3,4,5}
Output:
3
Explanation:
{1,2} and {3,4,5} -> 2+3>=5
{1,2,3} and {4,5} -> 3+4>=5
{1,2,3,4} and {5} -> 4+5>=5
Your Task:
You don't need to read input or print anything. Your task is to complete the function totalCuts() which takes two integers N, K, and an array A of size N as input parameters, and returns an integer representing the total number of cuts that satisfy both conditions.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
Constraints:
1 <= N <= 10^6
0 <= K <= 10^6
0 <= A[i] <= 10^6

Source: geeksforgeeks | Difficulty: EASY
Tags: Data structures

Range queries

Starter code: from typing import List





class Solution:

    def totalCuts(self, N : int, K : int, A : List[int]) -> int:

        # code here

        



Solutions:
from typing import List
import sys

class Solution:

	def totalCuts(self, N: int, K: int, A: List[int]) -> int:
		c = 0
		mi = [0] * N
		ma = [0] * N
		miv = sys.maxsize
		mav = -sys.maxsize - 1
		for i in range(N):
			mav = max(mav, A[i])
			ma[i] = mav
		for i in range(N - 1, -1, -1):
			miv = min(miv, A[i])
			mi[i] = miv
		for i in range(N - 1):
			if ma[i] + mi[i + 1] >= K:
				c += 1
		return c


from typing import List

class Solution:

	def totalCuts(self, N: int, K: int, A: List[int]) -> int:
		ans = 0
		left = [0] * N
		right = [0] * N
		left[0] = A[0]
		for i in range(1, N):
			left[i] = max(left[i - 1], A[i])
		right[N - 1] = A[N - 1]
		for i in range(N - 2, -1, -1):
			right[i] = min(right[i + 1], A[i])
		for i in range(1, N):
			if left[i - 1] + right[i] >= K:
				ans += 1
		return ans


from typing import List

class Solution:

	def totalCuts(self, N: int, K: int, A: List[int]) -> int:
		if N < 2:
			return 0
		count = 0
		n = len(A)
		maxim = min(A[1:])
		minim = min(A[1:])
		for i in range(1, n):
			if A[i - 1] > maxim:
				maxim = A[i - 1]
			if A[i - 1] == minim:
				minim = min(A[i:])
			if maxim + minim >= K:
				count += 1
		return count


from typing import List

class Solution:

	def totalCuts(self, N: int, K: int, A: List[int]) -> int:
		maxi = [0] * N
		mini = [0] * N
		maxi[0] = A[0]
		mini[N - 1] = A[N - 1]
		for i in range(1, N):
			maxi[i] = max(A[i], maxi[i - 1])
		for i in range(N - 2, -1, -1):
			mini[i] = min(A[i + 1], mini[i + 1])
		count = 0
		for i in range(N - 1):
			if mini[i] + maxi[i] >= K:
				count += 1
		return count


from typing import List

class Solution:

	def totalCuts(self, n: int, k: int, arr: List[int]) -> int:
		if n == 1:
			return 0
		(count, max1, min1) = (0, arr[0], arr[-1])
		(maxarr, minarr) = ([0 for i in range(n - 1)], [0 for i in range(n - 1)])
		(maxarr[0], minarr[-1]) = (arr[0], arr[-1])
		for i in range(1, n - 1):
			(max1, min1) = (max(max1, arr[i]), min(min1, arr[-1 - i]))
			(maxarr[i], minarr[-1 - i]) = (max1, min1)
		for i in range(n - 1):
			if maxarr[i] + minarr[i] >= k:
				count += 1
		return count


from typing import List

class Solution:

	def totalCuts(self, N: int, K: int, A: List[int]) -> int:
		n = 0
		m = A[0]
		for i in range(N - 1):
			if m >= K or m + min(A[i + 1:]) >= K:
				n = n + 1
			if A[i + 1] > m:
				m = A[i + 1]
		return n


from typing import List

class Solution:

	def totalCuts(self, N: int, K: int, A: List[int]) -> int:
		rs = 0
		tempSmallest = A[-1]
		smallestRight = [A[-1]]
		for i in range(2, N):
			if A[-i] < tempSmallest:
				tempSmallest = A[-i]
			smallestRight.append(tempSmallest)
		max = -1
		for i in range(N - 1):
			if A[i] > max:
				max = A[i]
			if max + smallestRight[-i - 1] >= K:
				rs += 1
		return rs


from typing import List

class Solution:

	def totalCuts(self, N: int, K: int, A: List[int]) -> int:
		count = 0
		maxl = A[0]
		minr = A[0]
		for i in range(N - 1):
			if A[i] == minr:
				minr = min(A[i + 1:])
			if maxl + minr >= K:
				count += 1
			if A[i + 1] > maxl:
				maxl = A[i + 1]
		return count


from typing import List

class Solution:

	def totalCuts(self, N: int, K: int, A: List[int]) -> int:
		l = 0
		maxleft = float('-inf')
		minright = float('inf')
		left = [0] * len(A)
		right = [0] * len(A)
		for i in range(N):
			maxleft = max(maxleft, A[i])
			left[i] = maxleft
		for i in range(N - 1, -1, -1):
			minright = min(minright, A[i])
			right[i] = minright
		for i in range(N - 1):
			if left[i] + right[i + 1] >= K:
				l += 1
		return l


from typing import List

class Solution:

	def totalCuts(self, N: int, K: int, A: List[int]) -> int:
		(mind, maxd) = ({}, {})
		(ma, mi) = (A[0], A[-1])
		c = 0
		for i in range(N):
			ma = max(ma, A[i])
			maxd[i] = ma
		for i in range(N - 1, -1, -1):
			mi = min(mi, A[i])
			mind[i] = mi
		for i in range(N - 1):
			if maxd[i] + mind[i + 1] >= K:
				c += 1
		return c


from typing import List

class Solution:

	def totalCuts(self, N: int, K: int, A: List[int]) -> int:
		min_el = [A[-1]]
		for i in range(N - 2, -1, -1):
			min_el.append(min(A[i], min_el[-1]))
		min_el.reverse()
		result = 0
		max_el = -1e+18
		for i in range(0, N - 1):
			max_el = max(A[i], max_el)
			if max_el + min_el[i + 1] >= K:
				result += 1
			else:
				continue
		return result


from typing import List

class Solution:

	def totalCuts(self, N: int, K: int, A: List[int]) -> int:
		(i, c) = (0, 0)
		lmax = A[i]
		while i != N - 1:
			if lmax >= K or lmax + min(A[i + 1:]) >= K:
				c = c + 1
				i = i + 1
			else:
				i = i + 1
			lmax = lmax if lmax >= A[i] else A[i]
		return c


from typing import List

class Solution:

	def totalCuts(self, n: int, ki: int, a: List[int]) -> int:
		s = 0
		l = 0
		r = [0] * n
		r[n - 1] = a[n - 1]
		for j in range(len(a) - 2, -1, -1):
			r[j] = min(a[j], r[j + 1])
		for i in range(len(a) - 1):
			l = max(a[i], l)
			if l + r[i + 1] >= ki:
				s += 1
		return s


from typing import List

class Solution:

	def totalCuts(self, N: int, K: int, A: List[int]) -> int:
		ways = 0
		for i in range(N - 1):
			left = max(A[:i + 1])
			if left >= K:
				return ways + N - 1 - i
			elif left + min(A[i + 1:]) >= K:
				ways += 1
		return ways


from typing import List

class Solution:

	def totalCuts(self, N: int, K: int, A: List[int]) -> int:
		trackMax = [-1]
		trackMin = [float('inf')]
		for i in A:
			x = trackMax[-1]
			if i > x:
				trackMax.append(i)
			else:
				trackMax.append(x)
		for i in A[::-1]:
			y = trackMin[-1]
			if i < y:
				trackMin.append(i)
			else:
				trackMin.append(y)
		c = 0
		trackMin = trackMin[::-1]
		trackMax = trackMax[1:]
		trackMin = trackMin[:N]
		for i in range(N - 1):
			if trackMax[i] + trackMin[i + 1] >= K:
				c += 1
		return c


from typing import List

class Solution:

	def totalCuts(self, n: int, k: int, a: List[int]) -> int:
		c = 0
		if n == 1:
			return c
		min = a[1]
		max = a[0]
		i = 1
		c = 0
		t = 1
		while i < n:
			if a[i] < min:
				min = a[i]
				t = i
			i += 1
		i = 1
		while i < n:
			if a[i - 1] > max:
				max = a[i - 1]
			if t < i and max < k:
				m = i
				min = a[m]
				while m < n:
					if a[m] < min:
						min = a[m]
					m += 1
			p = min + max
			if p >= k:
				c += 1
			i += 1
		return c


from typing import List

class Solution:

	def totalCuts(self, N: int, K: int, A: List[int]) -> int:
		leftMax = [A[0]] + [0] * (N - 2)
		rightMin = [0] * (N - 2) + [A[N - 1]]
		for i in range(1, N - 1):
			leftMax[i] = max(leftMax[i - 1], A[i])
		for i in range(N - 3, -1, -1):
			rightMin[i] = min(rightMin[i + 1], A[i + 1])
		count = 0
		for i in range(N - 1):
			if leftMax[i] + rightMin[i] >= K:
				count += 1
		return count


from typing import List

class Solution:

	def totalCuts(self, N, K, A) -> int:
		minR = []
		Max = A[0]
		Min = A[N - 1]
		result = 0
		for i in range(N - 1, 0, -1):
			Min = min(Min, A[i])
			minR.append(Min)
		minR.reverse()
		for i in range(N - 1):
			Max = max(Max, A[i])
			if Max + minR[i] >= K:
				result = result + 1
		return result


from typing import List

class Solution:

	def totalCuts(self, N: int, K: int, A: List[int]) -> int:
		t = list()
		t.append(A[0])
		k = A[1:]
		for x in range(N - 1):
			if max(t) + min(k) >= K:
				return len(A) - 1 - x
			t.append(k[0])
			k.pop(0)
		return 0


from typing import List

class Solution:

	def totalCuts(self, N: int, K: int, A: List[int]) -> int:
		min_list = []
		max_list = []
		for i in range(N - 1, -1, -1):
			if i == N - 1:
				min_list.append(A[i])
			else:
				min_list.append(min(min_list[-1], A[i]))
		min_list = min_list[::-1]
		for i in range(N):
			if i == 0:
				max_list.append(A[i])
			else:
				max_list.append(max(A[i], max_list[-1]))
		cuts = 0
		for i in range(1, N):
			su = max_list[i - 1] + min_list[i]
			if su >= K:
				cuts += 1
		return cuts


from typing import List

class Solution:

	def totalCuts(self, n: int, k: int, a: List[int]) -> int:
		m = a[0]
		s = a[-1]
		cnt = 0
		lm = [0] * n
		lm[0] = a[0]
		for i in range(1, n):
			lm[i] = max(m, a[i])
			m = max(m, a[i])
		rs = [0] * n
		rs[-1] = a[-1]
		for i in range(n - 2, -1, -1):
			rs[i] = min(s, a[i])
			s = min(s, a[i])
		for i in range(n - 1):
			if lm[i] + rs[i + 1] >= k:
				cnt += 1
		return cnt


from typing import List

class Solution:

	def totalCuts(self, N: int, K: int, A: List[int]) -> int:
		c = 0
		max_prefix = [0] * N
		min_suffix = [0] * N
		max_prefix[0] = A[0]
		for i in range(1, N):
			max_prefix[i] = max(A[i], max_prefix[i - 1])
		min_suffix[N - 1] = A[N - 1]
		for i in range(N - 2, -1, -1):
			min_suffix[i] = min(A[i], min_suffix[i + 1])
		for i in range(1, N):
			if max_prefix[i - 1] + min_suffix[i] >= K:
				c += 1
		return c


from typing import List

class Solution:

	def totalCuts(self, N: int, K: int, A: List[int]) -> int:
		if N == 1:
			return 0
		l = [A[0]]
		r = [A[-1]]
		maxi = A[0]
		for i in range(1, N - 1):
			maxi = max(maxi, A[i])
			l.append(maxi)
		mini = A[-1]
		for i in range(N - 2, 0, -1):
			mini = min(mini, A[i])
			r.append(mini)
		r = r[::-1]
		c = 0
		for i in range(len(l)):
			if l[i] + r[i] >= K:
				c += 1
		return c


from typing import List

class Solution:

	def totalCuts(self, N: int, K: int, A: List[int]) -> int:
		left_arr = [0] * N
		right_arr = [0] * N
		l_Max = 0
		r_Min = int(1000000000.0)
		for i in range(N):
			l_Max = max(l_Max, A[i])
			r_Min = min(r_Min, A[N - i - 1])
			left_arr[i] = l_Max
			right_arr[N - i - 1] = r_Min
		cnt = 0
		for i in range(1, N):
			if left_arr[i - 1] + right_arr[i] >= K:
				cnt += 1
		return cnt


from typing import List

class Solution:

	def totalCuts(self, n: int, k: int, a: List[int]) -> int:
		ans = 0
		if len(a) == 1:
			return 0
		left = [0 for i in range(n)]
		right = [0 for i in range(n)]
		left[0] = a[0]
		for i in range(1, n - 1):
			left[i] = max(left[i - 1], a[i])
		right[-1] = a[-1]
		for i in range(n - 2, 0, -1):
			right[i] = min(right[i + 1], a[i])
		for i in range(n):
			if left[i - 1] + right[i] >= k:
				ans += 1
			else:
				0
		return ans


from typing import List

class Solution:

	def totalCuts(self, N: int, K: int, A: List[int]) -> int:
		a = [0] * N
		b = [0] * N
		m = -1
		for i in range(N):
			m = max(m, A[i])
			a[i] = m
		m = 10 ** 7
		for i in range(N - 1, -1, -1):
			m = min(m, A[i])
			b[i] = m
		c = 0
		for i in range(N - 1):
			if a[i] + b[i + 1] >= K:
				c += 1
		return c


from typing import List

class Solution:

	def totalCuts(self, n: int, k: int, a: List[int]) -> int:
		ans = 0
		a = [[i] for i in a]
		a[0].append(a[0][0])
		for i in range(1, n):
			a[i].append(max(a[i][0], a[i - 1][1]))
		a[-1].append(a[-1][0])
		for i in range(n - 2, -1, -1):
			a[i].append(min(a[i][0], a[i + 1][2]))
		for i in range(n - 1):
			if a[i][1] + a[i + 1][2] >= k:
				ans += 1
		return ans


from typing import List

class Solution:

	def totalCuts(self, n: int, k: int, arr: List[int]) -> int:
		small = []
		right = n - 1
		for i in range(n - 1, -1, -1):
			if arr[i] <= arr[right]:
				small.append(i)
				right = i
		small = small[::-1]
		ans = 0
		leftMax = arr[0]
		ind = 0
		l = len(small)
		for i in range(1, n):
			while ind < l and small[ind] < i:
				ind += 1
			rightMin = arr[small[ind]]
			if leftMax + rightMin >= k:
				ans += 1
			leftMax = max(leftMax, arr[i])
		return ans


from typing import List

class Solution:

	def totalCuts(self, N: int, K: int, A: List[int]) -> int:
		small = []
		large = []
		(s, l) = (A[-1], A[0])
		for i in range(N):
			l = max(l, A[i])
			large.append(l)
			s = min(s, A[N - i - 1])
			small.append(s)
		small.reverse()
		c = 0
		for i in range(1, N):
			if small[i] + large[i - 1] >= K:
				c += 1
		return c


from typing import List

class Solution:

	def totalCuts(self, N: int, K: int, A: List[int]) -> int:
		if N == 1:
			return 0
		ans = 0
		big = A[0]
		small = min(A[1:])
		for i in range(1, N):
			if big + small >= K:
				ans += 1
			if A[i] > big:
				big = A[i]
			if i != N - 1 and small == A[i]:
				small = min(A[i + 1:])
		return ans


from typing import List

class Solution:

	def totalCuts(self, N: int, K: int, A: List[int]) -> int:
		small = []
		larg = []
		os = A[0]
		count = 0
		for i in range(0, N - 1):
			if A[i] > os:
				os = A[i]
			larg.append(os)
		os = A[N - 1]
		for k in range(N - 1, 0, -1):
			if A[k] < os:
				os = A[k]
			small.append(os)
		for j in range(1, N):
			if larg[j - 1] + small[N - 1 - j] >= K:
				count += 1
		return count


from typing import List

class Solution:

	def totalCuts(self, N: int, K: int, A: List[int]) -> int:
		(left, right) = ([-1] * N, [-1] * N)
		(max1, min1) = (-1, 10 ** 6 + 1)
		count = 0
		for i in range(N):
			max1 = max(A[i], max1)
			left[i] = max1
		for i in range(N - 1, -1, -1):
			min1 = min(A[i], min1)
			right[i] = min1
		for i in range(N - 1):
			if left[i] + right[i + 1] >= K:
				count += 1
		return count


from typing import List

class Solution:

	def totalCuts(self, N: int, K: int, A: List[int]) -> int:
		(maxv, minv) = ([0] * N, [0] * N)
		maxv[0] = A[0]
		for i in range(1, N):
			maxv[i] = max(maxv[i - 1], A[i])
		minv[-1] = A[-1]
		for i in range(-2, -N - 1, -1):
			minv[i] = min(minv[i + 1], A[i])
		return sum((1 for i in range(1, N) if maxv[i - 1] + minv[i] >= K))


class Solution:

	def totalCuts(self, N, K, A):
		maxi = [0] * N
		mini = [0] * N
		count = 0
		maxx = float('-inf')
		minn = float('inf')
		for i in range(N - 1):
			maxx = max(maxx, A[i])
			maxi[i] = maxx
			minn = min(minn, A[N - i - 1])
			mini[N - i - 1] = minn
		for i in range(N - 1):
			if maxi[i] + mini[i + 1] >= K:
				count += 1
		return count


class Solution:

	def totalCuts(self, N, K, A):
		leftlargest = [0] * N
		rightsmallest = [0] * N
		l = A[0]
		r = A[N - 1]
		count = 0
		for i in range(N):
			l = max(l, A[i])
			leftlargest[i] = l
		for i in range(N - 1, -1, -1):
			r = min(r, A[i])
			rightsmallest[i] = r
		for i in range(N - 1):
			if leftlargest[i] + rightsmallest[i + 1] >= K:
				count += 1
		return count


from typing import List

class Solution:

	def totalCuts(self, N: int, K: int, A: List[int]) -> int:
		dp = [A[-1]]
		(largest, ans) = (0, 0)
		for i in range(N - 2, -1, -1):
			dp.append(min(dp[-1], A[i]))
		dp.reverse()
		for i in range(N - 1):
			largest = max(largest, A[i])
			if largest + dp[i + 1] >= K:
				ans += 1
		return ans