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

You spin me round (like a monitor)

How to increase the security of your application with JSON Web Tokens — JWT (Rails and React)

Module Oriented Architecture — Part 6: Outsmarting the MVC

5–2 [Modeling] How to model a business process (Business Process Diagram)

Goodbye Oracle! Exclusive Insights into PrestoMall’s Transition to Alibaba Cloud

TASK -10 -

Materialized views

Create Your Own Software Development Platform using Phabricator on CentOS 7

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

Color of Next Ball Puzzle

Koko Eating Bananas

Josephus Problem in O(1) Time

The ultimate Software Engineering job search guide