Author |
Topic: K window sliding in an array (Read 2845 times) |
|
witee
Newbie



Posts: 48
|
 |
K window sliding in an array
« on: Sep 14th, 2010, 7:15am » |
Quote 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: 
Posts: 1001
|
 |
Re: K window sliding in an array
« Reply #1 on: Sep 14th, 2010, 8:25am » |
Quote 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: 
Posts: 13730
|
 |
Re: K window sliding in an array
« Reply #2 on: Sep 14th, 2010, 9:52am » |
Quote 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 Modify
|
Use queue with Min() function. O(N) time, O(K) space.
|
|
IP Logged |
|
|
|
birbal
Full Member
  

Gender: 
Posts: 250
|
 |
Re: K window sliding in an array
« Reply #4 on: Jan 28th, 2011, 6:47am » |
Quote Modify
|
on Sep 14th, 2010, 8:25am, TenaliRaman wrote: 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: 
Posts: 2084
|
 |
Re: K window sliding in an array
« Reply #5 on: Jan 28th, 2011, 7:31am » |
Quote 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: 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: 
Posts: 250
|
 |
Re: K window sliding in an array
« Reply #6 on: Jan 28th, 2011, 8:34am » |
Quote 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: 
Posts: 140
|
 |
Re: K window sliding in an array
« Reply #7 on: Feb 9th, 2011, 9:21pm » |
Quote 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..
|
|
|
|