Given an array arr[] of size N and an integer K. Find the maximum for each and every contiguous subarray of size K.
Example 1:
Input:
N = 9, K = 3
arr[] = 1 2 3 1 4 5 2 3 6
Output: 
3 3 4 5 5 5 6 
Explanation: 
1st contiguous subarray = {1 2 3} Max = 3
2nd contiguous subarray = {2 3 1} Max = 3
3rd contiguous subarray = {3 1 4} Max = 4
4th contiguous subarray = {1 4 5} Max = 5
5th contiguous subarray = {4 5 2} Max = 5
6th contiguous subarray = {5 2 3} Max = 5
7th contiguous subarray = {2 3 6} Max = 6
Example 2:
Input:
N = 10, K = 4
arr[] = 8 5 10 7 9 4 15 12 90 13
Output: 
10 10 10 15 15 90 90
Explanation: 
1st contiguous subarray = {8 5 10 7}, Max = 10
2nd contiguous subarray = {5 10 7 9}, Max = 10
3rd contiguous subarray = {10 7 9 4}, Max = 10
4th contiguous subarray = {7 9 4 15}, Max = 15
5th contiguous subarray = {9 4 15 12}, 
Max = 15
6th contiguous subarray = {4 15 12 90},
Max = 90
7th contiguous subarray = {15 12 90 13}, 
Max = 90
Your Task:  
You dont need to read input or print anything. Complete the function max_of_subarrays() which takes the array, N and K as input parameters and returns a list of integers denoting the maximum of every contiguous subarray of size K.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(k)
Constraints:
1 ≤ N ≤ 10^{5}
1 ≤ K ≤ N
0 ≤ arr[i] ≤ 10^{7}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Data structures

Amortized analysis

Starter code: #User function Template for python3



class Solution:

    

    #Function to find maximum of each subarray of size k.

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

        

        #code here

Solutions:
class Solution:

	def max_of_subarrays(self, arr, n, k):
		ans = []
		Q = deque([])
		for i in range(n):
			if Q and Q[0] <= i - k:
				Q.popleft()
			while Q and arr[Q[-1]] <= arr[i]:
				Q.pop()
			Q.append(i)
			if i >= k - 1:
				ans.append(arr[Q[0]])
		return ans


from collections import deque

class Solution:

	def max_of_subarrays(self, arr, n, k):
		result = []
		window = deque()
		for i in range(k):
			while window and arr[i] >= arr[window[-1]]:
				window.pop()
			window.append(i)
		for i in range(k, n):
			result.append(arr[window[0]])
			while window and window[0] <= i - k:
				window.popleft()
			while window and arr[i] >= arr[window[-1]]:
				window.pop()
			window.append(i)
		result.append(arr[window[0]])
		return result


class Solution:

	def max_of_subarrays(self, arr, n, k):
		queue = []
		maxi = 0
		for i in range(k):
			queue.append(arr[i])
			maxi = max(maxi, arr[i])
		res = []
		res.append(maxi)
		for i in range(k, n):
			a = queue.pop(0)
			queue.append(arr[i])
			if a == maxi:
				maxi = max(queue)
			else:
				maxi = max(maxi, arr[i])
			res.append(maxi)
		return res


class Solution:

	def max_of_subarrays(self, arr, n, k):
		result = []
		window = []
		for i in range(k):
			while window and arr[i] > arr[window[-1]]:
				window.pop()
			window.append(i)
		result.append(arr[window[0]])
		for i in range(k, n):
			while window and window[0] <= i - k:
				window.pop(0)
			while window and arr[i] > arr[window[-1]]:
				window.pop()
			window.append(i)
			result.append(arr[window[0]])
		return result


from collections import deque

class Solution:

	def max_of_subarrays(self, arr, N, K):
		result = []
		dq = deque()
		for i in range(N):
			while dq and arr[dq[-1]] < arr[i]:
				dq.pop()
			dq.append(i)
			if dq[0] <= i - K:
				dq.popleft()
			if i >= K - 1:
				result.append(arr[dq[0]])
		return result


class Solution:

	def max_of_subarrays(self, arr, n, k):
		dq = deque()
		res = []
		for i in range(n):
			if dq and dq[0] == i - k:
				dq.popleft()
			while dq and arr[dq[-1]] < arr[i]:
				dq.pop()
			dq.append(i)
			if i >= k - 1:
				res.append(arr[dq[0]])
		return res


class Solution:

	def max_of_subarrays(self, arr, n, k):
		i = 0
		j = 0
		maxi = []
		ans = []
		while j < len(arr):
			while len(maxi) != 0 and maxi[-1] < arr[j]:
				maxi.pop()
			maxi.append(arr[j])
			if j - i + 1 < k:
				j += 1
			elif j - i + 1 == k:
				ans.append(maxi[0])
				if arr[i] == maxi[0]:
					maxi.pop(0)
				i += 1
				j += 1
		return ans


from collections import deque

class Solution:

	def max_of_subarrays(self, arr, n, k):
		ans = []
		queue = deque()
		for i in range(k):
			while len(queue) > 0 and arr[queue[-1]] <= arr[i]:
				queue.pop()
			queue.append(i)
		ans.append(arr[queue[0]])
		for i in range(k, n):
			while len(queue) > 0 and queue[0] <= i - k:
				queue.popleft()
			while len(queue) > 0 and arr[queue[-1]] <= arr[i]:
				queue.pop()
			queue.append(i)
			ans.append(arr[queue[0]])
		return ans


from collections import deque

class Solution:

	def max_of_subarrays(self, arr, n, k):
		q = deque()
		for i in range(k):
			while q and arr[i] > arr[q[-1]]:
				q.pop()
			q.append(i)
		answ = []
		for i in range(k, n):
			answ.append(arr[q[0]])
			if q and i - k >= q[0]:
				q.popleft()
			while q and arr[i] >= arr[q[-1]]:
				q.pop()
			q.append(i)
		return answ + [arr[q[0]]]


from collections import deque

class Solution:

	def max_of_subarrays(self, arr, n, k):
		res = []
		a = arr[:k]
		m = max(a)
		res.append(m)
		for i in range(k, n):
			if arr[i] > m:
				a.pop(0)
				m = arr[i]
				a.append(m)
				res.append(m)
			elif a[0] == m:
				a.pop(0)
				a.append(arr[i])
				m = max(a)
				res.append(m)
			else:
				a.pop(0)
				a.append(arr[i])
				res.append(m)
		return res


class Solution:

	def max_of_subarrays(self, arr, n, k):
		curr = max(arr[:k])
		res = [curr]
		for i in range(1, n - k + 1):
			if arr[i + k - 1] >= curr:
				curr = arr[i + k - 1]
			elif arr[i - 1] == curr:
				curr = max(arr[i:i + k])
			res.append(curr)
		return res


class Solution:

	def max_of_subarrays(self, arr, n, K):
		q = deque()
		result = []
		for i in range(K):
			while q and arr[i] >= arr[q[-1]]:
				q.pop()
			q.append(i)
		for i in range(K, len(arr)):
			result.append(arr[q[0]])
			while q and q[0] <= i - K:
				q.popleft()
			while q and arr[i] >= arr[q[-1]]:
				q.pop()
			q.append(i)
		result.append(arr[q[0]])
		return result


class Solution:

	def max_of_subarrays(self, arr, N, K):
		ans = []
		d = deque()
		for x in range(N):
			while d and arr[d[-1]] <= arr[x]:
				d.pop()
			d.append(x)
			if d[0] == x - K:
				d.popleft()
			if x >= K - 1:
				ans.append(arr[d[0]])
		return ans


class Solution:

	def max_of_subarrays(self, arr, N, K):
		result = []
		window = deque()
		for i in range(N):
			while window and window[0] <= i - K:
				window.popleft()
			while window and arr[i] >= arr[window[-1]]:
				window.pop()
			window.append(i)
			if i >= K - 1:
				result.append(arr[window[0]])
		return result


class Solution:

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


class Solution:

	def max_of_subarrays(self, arr, n, k):
		arr1 = []
		max_val = max(arr[:k])
		arr1.append(max_val)
		for i in range(1, n - k + 1):
			if arr[i - 1] == max_val:
				max_val = max(arr[i:i + k])
			elif arr[i + k - 1] > max_val:
				max_val = arr[i + k - 1]
			arr1.append(max_val)
		return arr1


class Solution:

	def max_of_subarrays(self, arr, n, k):
		b = []
		l = []
		for i in range(k):
			while len(l) != 0 and arr[i] >= arr[l[-1]]:
				l.pop()
			l.append(i)
		for i in range(k, n):
			b.append(arr[l[0]])
			if l and l[0] <= i - k:
				l.pop(0)
			while len(l) != 0 and arr[i] >= arr[l[-1]]:
				l.pop()
			l.append(i)
		b.append(arr[l[0]])
		return b


class Solution:

	def max_of_subarrays(self, arr, n, k):
		m = []
		max_val = float('-inf')
		for i in range(k):
			max_val = max(max_val, arr[i])
		m.append(max_val)
		for i in range(k, n):
			if arr[i] > max_val:
				max_val = arr[i]
			elif arr[i - k] == max_val:
				max_val = max(arr[i - k + 1:i + 1])
			m.append(max_val)
		return m


import collections

class Solution:

	def max_of_subarrays(self, arr, n, k):
		dq = collections.deque()
		solution = [0] * (n - k + 1)
		l = r = j = 0
		while r < k:
			while len(dq) > 0 and dq[-1] < arr[r]:
				dq.pop()
			dq.append(arr[r])
			r += 1
		solution[j] = dq[0]
		l += 1
		j += 1
		while r < n:
			while len(dq) > 0 and dq[-1] < arr[r]:
				dq.pop()
			dq.append(arr[r])
			if dq[0] == arr[l - 1]:
				dq.popleft()
			solution[j] = dq[0]
			r += 1
			l += 1
			j += 1
		return solution


class Solution:

	def max_of_subarrays(self, arr, n, k):
		queue = []
		result = []
		for i in range(n):
			if len(queue) == 0 or queue[len(queue) - 1] >= arr[i]:
				queue.append(arr[i])
			else:
				j = len(queue) - 1
				while j >= 0 and queue[j] < arr[i]:
					j -= 1
					queue.pop()
				queue.append(arr[i])
			if i >= k - 1:
				result.append(queue[0])
				if queue[0] == arr[i - k + 1]:
					queue.pop(0)
		return result


from collections import deque

class Solution:

	def max_of_subarrays(self, arr, n, k):
		(dq, res) = (deque(), [])
		for i in range(n):
			while len(dq) > 0 and arr[dq[0]] < arr[i]:
				dq.popleft()
			dq.appendleft(i)
			while dq[-1] <= i - k:
				dq.pop()
			if i >= k - 1:
				res.append(arr[dq[-1]])
		return res


class Solution:

	def max_of_subarrays(self, arr, n, k):
		deq = deque()
		max = []
		for i in range(k):
			while deq and arr[i] > arr[deq[-1]]:
				deq.pop()
			deq.append(i)
		for i in range(k, n):
			max.append(arr[deq[0]])
			while deq and deq[0] <= i - k:
				deq.popleft()
			while deq and arr[i] > arr[deq[-1]]:
				deq.pop()
			deq.append(i)
		max.append(arr[deq[0]])
		return max


class Solution:

	def max_of_subarrays(self, arr, n, k):
		res = []
		d = deque()
		for i in range(k):
			while len(d) and arr[i] >= arr[d[-1]]:
				d.pop()
			d.append(i)
		for i in range(k, n):
			res.append(arr[d[0]])
			while len(d) and d[0] <= i - k:
				d.popleft()
			while len(d) and arr[i] >= arr[d[-1]]:
				d.pop()
			d.append(i)
		res.append(arr[d[0]])
		d.popleft()
		return res


class Solution:

	def max_of_subarrays(self, a, n, k):
		s = []
		o = []
		for i in range(k):
			while len(s) != 0 and a[s[-1]] < a[i]:
				s.pop()
			s.append(i)
		o.append(a[s[0]])
		for i in range(k, n):
			if i - k >= s[0]:
				s.pop(0)
			while len(s) != 0 and a[s[-1]] < a[i]:
				s.pop()
			s.append(i)
			o.append(a[s[0]])
		return o


from collections import deque

class Solution:

	def max_of_subarrays(self, nums, n, k):
		i = 0
		j = 0
		d = deque()
		res = []
		while j < len(nums):
			while len(d) > 0 and d[-1] < nums[j]:
				d.pop()
			d.append(nums[j])
			if j - i + 1 < k:
				j += 1
			elif j - i + 1 == k:
				res.append(d[0])
				if d[0] == nums[i]:
					d.popleft()
				i += 1
				j += 1
		return res


class Solution:

	def max_of_subarrays(self, arr, n, k):
		mx_v = []
		r = []
		for i in range(n):
			if mx_v and mx_v[0] == i - k:
				mx_v.pop(0)
			while mx_v and arr[mx_v[-1]] < arr[i]:
				mx_v.pop()
			mx_v.append(i)
			if i >= k - 1:
				r.append(arr[mx_v[0]])
		return r


class Solution:

	def max_of_subarrays(self, arr, n, k):
		result = []
		max_element = max(arr[:k])
		result.append(max_element)
		for i in range(k, n):
			if arr[i - k] == max_element:
				max_element = max(arr[i - k + 1:i + 1])
			elif arr[i] > max_element:
				max_element = arr[i]
			result.append(max_element)
		return result


class Solution:

	def max_of_subarrays(self, arr, n, k):
		r = []
		r.append(max(arr[:k]))
		j = 0
		for i in range(k, n):
			if arr[j] == r[-1]:
				r.append(max(arr[j + 1:i + 1]))
			elif arr[i] > r[-1]:
				r.append(arr[i])
			else:
				r.append(r[-1])
			j += 1
		return r