Maximum in Subarrays of length K — Asked in Amazon Interview

Problem Statement :

Given an array of integers of size N and a number K, print the maximum value of each subarray of length K in the array

The first line contains two single space separated integers, N and K.

The second line contains N single space separated integers denoting the elements of the array.

Sample Input:

6 3
10 5 2 7 8 7

Sample Output:

10 7 8 8

Approach :

Deque Approach

  1. Create a double-ended queue. Note that the deque will store the indices of the elements, not the elements themselves
  2. Insert the first ‘K’ elements (the first subarray) in the deque. While inserting the current element, check if the element at the back of the queue is smaller than the current element. If yes, then remove all those elements and then insert the current element in the back of the deque.
  3. After you’ve done this, the front of the queue will have the index of the maximum element present in the first subarray of size ‘K’. Print the element present at front element (index of array element) of the deque.
  4. Then, we’ll follow the same idea for the next elements as well but there will be one extra step which is to remove all elements from the front of the deque that is out of the range of the subarray into consideration.

Time Complexity — O(N)
Space Complexity — O(K)

Code :

Thanks for Reading

Placewit grows the best engineers by providing an interactive classroom experience and by helping them develop their skills and get placed in amazing companies.

Learn more at Placewit. Follow us on Instagram and Facebook for daily learning.

--

--

--

Upskilling students for tech placements!

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

Vault Part2 - Introduction to Secrets and Secrets Engines

How to compare ’n’ number of flat lists in Python ?

Most popular open-source Java application tools in 2020

My Bootcamp Journey: Or How Project 2 Changed My Perspective

What VMware Pros need to know about VMWonAWS

Backtracking

An Introduction to Cloud Backup: What, Why, and How

UNDERGRAD ARCHIVE: CompileTile

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Placewit

Placewit

Upskilling students for tech placements!

More from Medium

LeetCode 146. LRU Cache

Scattered Rice Coding Question

PlatinumX Tech’s Algorithm Expert Course Review (How I got into Turing).

Knight Probability in Chessboard Solution | LeetCode-688: Medium | JavaScript Implementation