Sliding window minimum algorithm

Question

This is a homework problem. Let A[] is an array of integers and integer K -- window size. Generate array M of minimums seen in a window as it slides over A. I found an article with a solution for this problem but did not understand why it has O(n) complexity. Can anybody explain it to me?

@Andre: "the homework tag, like other so-called 'meta' tags, is now discouraged." — Roger Pate
– Roger Pate, Commented Nov 8, 2010 at 9:46
Oh, didn't know that. Saw it requested on stackoverflow.com/questions/4114917/…. Maybe there should be a note in the tag's description? — AndreKR
– AndreKR, Commented Nov 8, 2010 at 9:50

JPvdMerwe · Accepted Answer · 2010-11-09 11:12:45Z

9

This tends to catch people out. You would think it would take O(N^2) time since you reason adding takes O(N) time and you have O(N) elements. However, realise each element can only be added once and removed once. So in total it takes O(N) to slide over the whole array A.

This yields an amortised efficiency of O(1) every time you move the sliding window on by one element. In other words, the average time it takes to move the sliding window by one element is O(1).

edited Nov 9, 2010 at 11:12

answered Nov 8, 2010 at 9:31

JPvdMerwe

3,3843 gold badges30 silver badges32 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Sliding window minimum algorithm

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related