Windows of size k (Must Read the Accepted Answer, New Method)

Asked Jun 21 '13 at 11:04

Active Jun 21 '13 at 22:20

Viewed 271 times

Given an Array of Size n , that is it have n elements in it. and window size 'W'. you have to find maximum in all subarrays of size 'W'. starting from index 0.

Sample Input:
n=10 , W = 3 // n is number of element in array and W is window size.

10 3
1 -2 5 6 0 9 8 -1 2 0

Answer = 5 6 6 9 9 9 8 2

What i tried - (Self-Balancing BST)

Pick first k elements and create a Self-Balancing Binary Search Tree (BST) of size W.
Run a loop for i = 0 to n – W
1. Get the maximum element from the BST, and print it.
2. Search for arr[i] in the BST and delete it from the BST.
3. Insert arr[i+W] into the BST.

Time Complexity:

Step 1 is O(WLogW).
Time Complexity of steps 2.1, 2.2 and 2.3 is O(LogW). Since Steps of 2.1, 2.2 and 2.3 are in a loop that runs n-W+1 times, time complexity of the complete algorithm is O(WLogW + (n-W+1)*LogW) which can also be written as O(nLogW).

My Question is can i improve it ? any suggestion on BST approach or Any other algorithm i haven't heard if ?

Everywhere i see only Dequeue Method. isn't there any Method ?

edited Jun 21 '13 at 22:20

asked Jun 21 '13 at 11:04

1

This can be Easily solved by dynamic programming in O(n) ? tried ? – S J Jun 21 '13 at 11:05
how ? i have seen method of dequeue. but i didn't get it. – Jun 21 '13 at 11:06
Deqeue method is Quite Common. it is in O(n). have you tried it ? – S J Jun 21 '13 at 11:08
You said about Dynamic Programming Method ? how to do it using that ? can you explain ? – Jun 21 '13 at 11:10
Try it once ! else i will tell approach . it is common approach to come up with ! – S J Jun 21 '13 at 11:15
Can you tell me a way, all i can find is DEQUEUE method ! – Jun 21 '13 at 11:28
What's wrong with the Dequeue method? – Bernhard Barker Jun 21 '13 at 11:39
that is hard to understand !! – Jun 21 '13 at 11:43
http://stackoverflow.com/questions/12190184/can-min-max-of-moving-window-achieve-in-on – legends2k Jun 21 '13 at 12:47
http://people.cs.uct.ac.za/~ksmith/articles/sliding_window_minimum.html – legends2k Jun 21 '13 at 12:52
yeah that's right ! but please look at solution below, you won't be disappointed i assure. this answer is different from all duplicates on Stackoverflow – Jun 21 '13 at 20:07

Maximum/Minimum of all subarrays/ Windows of size k (Must Read the Accepted Answer, New Method)

0 Answers0