wu :: forums
« wu :: forums - K window sliding in an array »

Welcome, Guest. Please Login or Register.
Jun 17th, 2025, 6:37am

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   cs
(Moderators: william wu, towr, Eigenray, SMQ, Grimbal, ThudnBlunder, Icarus)
   K window sliding in an array
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: K window sliding in an array  (Read 2845 times)
witee
Newbie
*





   
Email

Posts: 48
K window sliding in an array  
« on: Sep 14th, 2010, 7:15am »
Quote Quote Modify Modify

Given an array of N elements, A[0 .. N - 1], Produce an array B such that: B[i] = min (A[i], A[i+1], ..., A[i+K-1]); (The array B will have exactly (N-k+1) elts..
 
T.C< (N*K)
IP Logged
TenaliRaman
Uberpuzzler
*****



I am no special. I am only passionately curious.

   


Gender: male
Posts: 1001
Re: K window sliding in an array  
« Reply #1 on: Sep 14th, 2010, 8:25am »
Quote Quote Modify Modify

*SPOILER*
 
-- AI
IP Logged

Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
Posts: 13730
Re: K window sliding in an array  
« Reply #2 on: Sep 14th, 2010, 9:52am »
Quote Quote Modify Modify

With a min-heap of size K you can get O(log(K)*N) runtime.
But you can probably do better.
IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
alexeigor
Newbie
*





   


Posts: 45
Re: K window sliding in an array  
« Reply #3 on: Sep 27th, 2010, 10:15pm »
Quote Quote Modify Modify

Use queue with Min() function. O(N) time, O(K) space.
IP Logged
birbal
Full Member
***





   


Gender: male
Posts: 250
Re: K window sliding in an array  
« Reply #4 on: Jan 28th, 2011, 6:47am »
Quote Quote Modify Modify

on Sep 14th, 2010, 8:25am, TenaliRaman wrote:
*SPOILER*
 
-- AI

I have a doubt about this algorithm. Its not explained how we answer the min() query at any position of window. If my sequence is a monotonically increasing sequence, Ascending minima vevtor - A will contain as many elements as there are in window and when window is moved one step forward, an element x is added but no element is deleted except for 1, which is moving out of window (as the seq is monotonically increasing) but we need to go through all the elements of vector A. This will make it O(n*k)
how is it O(n) ?
« Last Edit: Jan 28th, 2011, 6:48am by birbal » IP Logged

The only thing we have to fear is fear itself!
SMQ
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
Posts: 2084
Re: K window sliding in an array  
« Reply #5 on: Jan 28th, 2011, 7:31am »
Quote Quote Modify Modify

on Jan 28th, 2011, 6:47am, birbal wrote:
I have a doubt about this algorithm. Its not explained how we answer the min() query at any position of window.

min() = A[0]
 
Quote:
If my sequence is a monotonically increasing sequence, Ascending minima vevtor - A will contain as many elements as there are in window and when window is moved one step forward, an element x is added but no element is deleted except for 1, which is moving out of window (as the seq is monotonically increasing) but we need to go through all the elements of vector A. This will make it O(n*k)

No, we compare from the back of the array.  In the case of an increasing sequence we only compare the new element with the last element in the array A; the others are irrelevant.
 
Quote:
how is it O(n) ?

For every step of the window we
a) compare and remove some elements of A which are greater than the about-to-be-added element,
a-and-a-half) compare a single element of A which is less than the about-to-be-added element,
b) add an element to A, and
c) compare indexes and possibly remove the first element of A.
 
Clearly steps a-and-a-half), b), and c) are O(1).  Since no element can be added to A more than once, step a) must be amortized O(1).  Thus the entire algorithm is O(N).
 
--SMQ
IP Logged

--SMQ

birbal
Full Member
***





   


Gender: male
Posts: 250
Re: K window sliding in an array  
« Reply #6 on: Jan 28th, 2011, 8:34am »
Quote Quote Modify Modify

Thank you SQM. I missed that elements in vector are in acsending order.
IP Logged

The only thing we have to fear is fear itself!
Ronno
Junior Member
**






   


Gender: male
Posts: 140
Re: K window sliding in an array  
« Reply #7 on: Feb 9th, 2011, 9:21pm »
Quote Quote Modify Modify

Break the array into k sized parts. For each element, store the minimum from the left boundary and the right boundary. Then to find the minimum in the ith k-window, take the minimum of the left value at the (i+k-1)th place and right value at ith place.  
 
This is O(n) space and time.
IP Logged

Sarchasm: The gulf between the author of sarcastic wit and the person who doesn't get it..
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board