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.
Asked
Active
Viewed 202 times
1
-
show you current,. ineffective, approach – Marcin Orlowski Aug 14 '17 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 – Felix Aug 14 '17 at 20:31
-
I think you are looking for a Binary Heap array based implementation. You can take a look at this http://www.sanfoundry.com/java-program-implement-binary-heap/ – Sergei Sirik Aug 14 '17 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)`. – shmosel Aug 14 '17 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](https://stackoverflow.com/q/4802038/572670) discusses how to achieve this – amit Aug 14 '17 at 20:46