1

At every iteration, two new values are added and the two oldest values are removed. How to efficiently find the minimum value at each iteration without processing the entire array again. The array starts filling from size 0 to N. Only after the entire array is filled, the removing of oldest values starts.

Improve this question
5
  • show you current,. ineffective, approach Commented Aug 14, 2017 at 20:28
  • When the array starts with a size of 0 you can simply check if one of the new values is the smallest Commented Aug 14, 2017 at 20:31
  • I think you are looking for a Binary Heap array based implementation. You can take a look at this sanfoundry.com/java-program-implement-binary-heap Commented Aug 14, 2017 at 20:35
  • If you compare a running minimum against incoming values, you'll only have to iterate when it hits the bottom. That should keep the cost at O((1/n)*n) or O(1). Commented Aug 14, 2017 at 20:44
  • You can reduce this "sliding array" problem easily to a queue data structure, and then the problem boils down to "how do I efficiently find min in a queue DS". This thread discusses how to achieve this Commented Aug 14, 2017 at 20:46
Load 7 more related questions Show fewer related questions

0

Reset to default

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.