Given an array arr[] and a number k. The task is to delete k elements which are smaller than next element (i.e., we delete arr[i] if arr[i] < arr[i+1]) or become smaller than next because next element is deleted.
Example 1:
Ã¢â¬â¹Input : arr[ ] = {20, 10, 25, 30, 40} 
        and K = 2
Output : 25 30 40
Explanation:
First we delete 10 because it follows 
arr[i] < arr[i+1]. Then we delete 20 
because 25 is moved next to it and it 
also starts following the condition.
Ã¢â¬â¹Example 2:
Input : arr[ ] = {3, 100, 1} and K = 1
Output :  100 1 
 
Your Task:
This is a function problem. The input is already taken care of by the driver code. You only need to complete the function deleteElement() that takes an array (arr), sizeOfArray (n), an integer K and return the array arr[] after deleting the k elements from the array if possible, else print the left array as it is. The driver code takes care of the printing.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(N).
 
Constraints:
2 ≤ N ≤ 10^{5}
1 ≤ K < N

Source: geeksforgeeks | Difficulty: EASY
Tags: Data structures

Starter code: #User function Template for python3



def deleteElement (arr, n, k) : 

    #Complete the function

    



Solutions:
def deleteElement(arr, n, k):
	st = []
	st.append(arr[0])
	c = 0
	for i in arr[1:]:
		while st and st[-1] < i and (c < k):
			st.pop()
			c += 1
		st.append(i)
	return st


def deleteElement(arr, n, k):
	stack = []
	for item in arr:
		while stack and k and (stack[-1] < item):
			stack.pop()
			k -= 1
		stack.append(item)
	return stack


def deleteElement(arr, n, k):
	stack = []
	n = len(arr)
	i = 0
	while i < n:
		if len(stack) == 0:
			stack.append(arr[i])
			i += 1
		elif k > 0:
			if stack[-1] >= arr[i]:
				stack.append(arr[i])
				i += 1
			else:
				stack.pop()
				k -= 1
		else:
			stack.append(arr[i])
			i += 1
	return stack


def deleteElement(arr, n, k):
	stack = []
	for i in arr:
		while stack and k > 0 and (stack[-1] < i):
			stack.pop()
			k -= 1
		stack.append(i)
	return stack


def deleteElement(arr, n, k):
	stack = []
	for i in range(n):
		while len(stack) > 0 and stack[-1] < arr[i] and (k != 0):
			stack.pop()
			k = k - 1
		else:
			stack.append(arr[i])
	return stack


def deleteElement(arr, n, k):
	ans = []
	index = 0
	while index < n and k > 0:
		cur = arr[index]
		if not ans:
			ans.append(cur)
		else:
			while ans and ans[-1] < cur:
				ans.pop()
				k -= 1
				if k == 0:
					break
			ans.append(cur)
		index += 1
	for i in range(index, n):
		ans.append(arr[i])
	return ans


def deleteElement(arr, n, k):
	st = []
	st.append(arr[0])
	count = 0
	for i in range(1, n):
		while len(st) != 0 and count < k and (st[-1] < arr[i]):
			st.pop()
			count += 1
		st.append(arr[i])
	return st


def deleteElement(arr, n, k):
	i = 0
	while i < len(arr):
		if i != len(arr) - 1 and arr[i] < arr[i + 1]:
			k -= 1
			arr.pop(i)
			i = 0
		else:
			i += 1
		if k == 0:
			return arr
	return arr


def deleteElement(arr, n, k):
	l = []
	for i in range(n):
		while l and k != 0 and (l[-1] < arr[i]):
			l.pop()
			k -= 1
		l.append(arr[i])
	return l


def deleteElement(arr, n, k):
	s = []
	for i in arr:
		while s and k and (s[-1] < i):
			s.pop()
			k -= 1
		s.append(i)
	return s


def deleteElement(arr, n, k):
	sta = []
	for i in range(n):
		while len(sta) != 0 and arr[sta[-1]] < arr[i] and k:
			arr[sta[-1]] = -1
			k -= 1
			sta.pop()
		sta.append(i)
	return [int(i) for i in arr if i != -1]


def deleteElement(l, n, k):
	c = 0
	i = 0
	while i < len(l) - 1:
		if l[i] < l[i + 1]:
			l.pop(i)
			i = 0
			c += 1
			if c == k:
				return l
		else:
			i += 1
			continue
	return l


def deleteElement(arr, n, k):
	while k > 0:
		for i in range(0, len(arr) - 1):
			if arr[i] < arr[i + 1]:
				arr.remove(arr[i])
				break
		k = k - 1
	return arr


def deleteElement(arr, n, k):
	a = []
	for i in arr:
		while len(a) > 0 and k > 0 and (a[-1] < i):
			a.pop()
			k -= 1
		a.append(i)
	return a


def deleteElement(x, n, k):
	c = 0
	l = []
	l.append(arr.pop(0))
	while c != k:
		if l == []:
			l.append(arr.pop(0))
		elif arr:
			if l[-1] < arr[0]:
				l.pop()
				c += 1
			else:
				l.append(arr.pop(0))
		else:
			return l
	return l + arr


def deleteElement(arr, n, k):
	stack = []
	b = []
	for i in range(n):
		while stack and stack[-1] < arr[i] and (k != 0):
			stack.pop()
			k -= 1
		stack.append(arr[i])
	while stack:
		b.append(stack[-1])
		stack.pop()
	b.reverse()
	return b


def deleteElement(arr, n, k):
	s = []
	ans = []
	for i in range(n):
		while s and s[-1] < arr[i] and (k != 0):
			s.pop()
			k -= 1
		s.append(arr[i])
	while s:
		ans.append(s[-1])
		s.pop()
	ans.reverse()
	return ans


def deleteElement(arr, n, k):
	i = 0
	count = 0
	while i < len(arr) - 1:
		if arr[i] < arr[i + 1] and count < k:
			arr.pop(i)
			count += 1
			if i < 2:
				i = -1
			if i >= 2:
				i -= 2
		i += 1
	return arr


def deleteElement(arr, n, k):
	i = 0
	j = 0
	while i < n - 1:
		if i < len(arr) - 1:
			if arr[i] < arr[i + 1] and j != k:
				arr.remove(arr[i])
				j = j + 1
				i = -1
		i += 1
	return arr


def deleteElement(arr, n, k):
	i = 0
	while i != -1:
		if i + 1 < len(arr):
			if k != 0:
				if arr[i] < arr[i + 1]:
					arr.remove(arr[i])
					k = k - 1
					i = 0
				else:
					i = i + 1
			else:
				return arr
				i = -1
		else:
			return arr


def deleteElement(arr, n, k):
	for i in range(k):
		for j in range(len(arr) - 1):
			if arr[j] < arr[j + 1]:
				arr.remove(arr[j])
				break
	return arr


def deleteElement(a, n, k):
	(s, r) = ([], [])
	for i in range(n):
		while s and s[-1] < a[i] and (k != 0):
			s.pop()
			k -= 1
		s.append(a[i])
	while s:
		r.append(s[-1])
		s.pop()
	r.reverse()
	return r


from collections import deque

def deleteElement(arr, n, k):
	stq = deque()
	ans = []
	top = -1
	for i in arr:
		while k > 0 and stq and (stq[top] < i):
			stq.pop()
			top -= 1
			k -= 1
		stq.append(i)
		top += 1
	while stq:
		ans.append(stq.popleft())
	return ans


def deleteElement(a, n, k):
	st = []
	for i in a:
		if not st:
			st.append(i)
		elif i < st[-1]:
			st.append(i)
		else:
			while k and st and (st[-1] < i):
				st.pop()
				k -= 1
			st.append(i)
	a[:] = st[:]
	return a


def deleteElement(arr, n, k):
	q = []
	i = 0
	while i < n and k > 0:
		if len(q) == 0:
			q.append(arr[i])
			i += 1
		elif q[-1] < arr[i]:
			q.pop()
			k -= 1
			if k == 0:
				break
		else:
			q.append(arr[i])
			i += 1
	while i < n:
		q.append(arr[i])
		i += 1
	return q


def deleteElement(arr, n, k):
	st = []
	for i in range(n):
		flag = 1
		while len(st) != 0 and arr[i] > st[-1]:
			st.pop()
			k = k - 1
			if k == 0:
				flag = 0
				break
		st.append(arr[i])
		if flag == 0:
			i = i + 1
			while i < n:
				st.append(arr[i])
				i += 1
			break
	return st


def deleteElement(arr, n, k):
	for i in range(0, k):
		for i in range(0, len(arr) - 1):
			if arr[i] < arr[i + 1]:
				arr.pop(i)
				break
	return arr


def deleteElement(arr, n, k):
	stack = []
	count = 0
	for i in range(n):
		if count == k:
			stack.append(arr[i])
		elif stack:
			x = stack[-1]
			while count < k and x < arr[i]:
				count += 1
				stack.pop()
				if stack:
					x = stack[-1]
				else:
					break
			stack.append(arr[i])
		else:
			stack.append(arr[i])
	answer = []
	while stack:
		x = stack.pop()
		answer.append(x)
	return answer[-1::-1]
for _ in range(0, int(input())):
	n = int(input())
	arr = list(map(int, input().strip().split()))
	k = int(input())
	ans = deleteElement(arr, n, k)
	print(*ans)


def deleteElement(arr, n, k):
	count = 0
	top = 0
	stack = []
	stack.append(arr[0])
	for i in range(1, n):
		while len(stack) != 0 and stack[top] < arr[i] and (count < k):
			stack.pop()
			count += 1
			top -= 1
		stack.append(arr[i])
		top += 1
	return stack
for _ in range(0, int(input())):
	n = int(input())
	arr = list(map(int, input().strip().split()))
	k = int(input())
	ans = deleteElement(arr, n, k)
	print(*ans)


def deleteElement(arr, n, k):
	ans = []
	s = []
	c = 0
	for i in range(n):
		if c != k:
			while s != [] and c != k and (s[-1] < arr[i]):
				s.pop()
				c += 1
			s.append(arr[i])
		else:
			s.append(arr[i])
	for i in s:
		ans.append(i)
	return ans
for _ in range(0, int(input())):
	n = int(input())
	arr = list(map(int, input().strip().split()))
	k = int(input())
	ans = deleteElement(arr, n, k)
	print(*ans)


def deleteElement(arr, n, k):
	s = [arr[0]]
	d = 0
	for i in range(1, n):
		if len(s) != 0:
			if s[-1] >= arr[i]:
				s.append(arr[i])
			if s[-1] < arr[i] and d == k:
				s.append(arr[i])
			if s[-1] < arr[i] and d < k:
				while s[-1] < arr[i] and d < k:
					s.pop()
					d = d + 1
					if len(s) == 0:
						break
				s.append(arr[i])
		else:
			s.append(arr[i])
	return s


def deleteElement(arr, n, k):
	for m in range(k):
		xx = 0
		for kp in arr:
			if xx + 1 != len(arr) and kp < arr[xx + 1]:
				arr.remove(kp)
				break
			xx = xx + 1
	return arr


def deleteElement(arr, n, k):
	i1 = 0
	s = []
	for i in range(n):
		while len(s) > 0 and s[-1] < arr[i] and (k != 0):
			s.pop()
			k -= 1
		s.append(arr[i])
	return s


def deleteElement(arr, n, k):
	st = []
	for i in range(n):
		if len(st) == 0 or st[len(st) - 1] >= arr[i]:
			st.append(arr[i])
		else:
			while k > 0 and len(st) > 0 and (st[len(st) - 1] < arr[i]):
				st.pop()
				k -= 1
			st.append(arr[i])
	return st


def deleteElement(arr, n, k):
	stack = []
	c = 0
	for num in arr:
		if len(stack) == 0 or num <= stack[-1] or c == k:
			stack.append(num)
		elif num > stack[-1]:
			while len(stack) != 0 and num > stack[-1]:
				stack.pop()
				c += 1
				if c == k:
					break
			stack.append(num)
	return stack


def deleteElement(arr, n, k):
	j = 0
	for i in range(n):
		if j < k:
			for _ in range(len(arr)):
				if _ <= len(arr) - 2 and arr[_ + 1] > arr[_]:
					arr.pop(_)
					j += 1
					break
		else:
			break
	return arr


def deleteElement(arr, n, k):
	s1 = []
	s2 = []
	for item in arr[::-1]:
		s1.append(item)
	while s1 and k != 0:
		if not s2:
			s2.append(s1.pop())
			if not s1:
				return s2
		if s2[-1] >= s1[-1]:
			s2.append(s1.pop())
		else:
			s2.pop()
			k -= 1
	while s2:
		s1.append(s2.pop())
	return s1[::-1]


def deleteElement(arr, n, k):
	s = [arr[0]]
	c = 0
	i = 1
	while i < n:
		if len(s) != 0:
			if s[len(s) - 1] < arr[i]:
				s.pop()
				c += 1
			else:
				s.append(arr[i])
				i += 1
		else:
			s.append(arr[i])
			i += 1
		if c == k:
			break
	for j in range(i, n):
		s.append(arr[j])
	return s


def deleteElement(arr, n, k):
	i = 0
	j = 0
	while i < k:
		if j >= len(arr) - 1:
			break
		if arr[j] < arr[j + 1]:
			arr.pop(j)
			j = 0
			i = i + 1
		else:
			j = j + 1
	return arr


def deleteElement(arr, n, k):
	stack = []
	i = 0
	count = 0
	while i < len(arr):
		if len(stack) != 0 and arr[i] > stack[-1] and (count < k):
			stack.pop()
			i -= 1
			count += 1
		else:
			stack.append(arr[i])
		i += 1
	return stack