# Fastest way to find maximum deviation

I acknowledge that this exact question was asked here. I was working on the same problem from the same website. I had the same question and consulted the above as a reference, however with respect to the person answering the question, it is the wrong answer. That is why I decided to restart this thread.

Problem

With an array of integer elements, I have to consider all sequences of d consecutive elements. For every sequence (there can be almost 100k of them) I must find the difference between the highest and lowest values in that sequence. All of this has to be accomplished in under 2 seconds.

This was the first solution that came to my mind, but as expected it couldn't find the solution in less than 2 seconds for some test cases.

def find_deviation(v,d)
v.each_cons(d).to_a.map { |array|array.max - array.min}.max}
end


The answer given in that thread was

def find_deviation(values, m)
values.each_cons(m).map { |xs| xs.max - xs.min }.max
end


At first glance, that code looks nearly identical to mine, only with different variable names.

This puzzle had some pretty stringent data constraints

v: Array of integers

d: Integer value with the length of the sequence

1. The array will contain up to 100,000 elements
2. All elements in the array are integers in the range [1,2 ^ 31 - 1]
3. The value of d is less than the length of the array.
4. The algorithm has to solve in less than 2 seconds

In my solution, I'm using the each_cons method then mapping it.

The complexity is at least $O(n^2)$, which means this method will take way too long to solve.

With an array of 100,000 elements, and taking each_cons of more than 50,000 and then mapping them, this might take hours to solve.

I've tried generating random numbers like this.

v = 100000.times.map {(1..2**32-1).to_a.sample}
d = 97,854


and it will literally never finish.

Basically, I'm trying to find the bottlenecks in this code. I must be doing something wrong.

• I think you missed the second half of the answer you linked, where it's suggested to use a binary search tree for fast min/max/insert/delete. – mjolka Sep 24 '14 at 4:27

First, don't use those functions to create the array, it takes forever because you are depleting the memory of the computer that way.

Use something like this:

v = Array.new(100000).map {rand (2**32-1)}


That is, v is a new array of size 100000, where each element is set to a random number between 0 and 232-1.

For d, don't put commas in the integer, just d=97854. (EDIT: or use _ as mentioned in by Devon in the comments)

As for a fast way to get the difference in the array, that's probably the core of the quiz, so I won't provide code. Hint: code it like you would do manually: check the max/min of the first interval and modify the max/min depending on the element in the array that you gain/lose when you shift the begining/ending of the interval. Sorry if I'm cryptic in the explanation; this is supposed to be only a hint!

• Array.new(100000){ rand 2**32-1 } – Nakilon Sep 25 '14 at 9:59
• Thank you, that hint should be enough to help me solve this. – Johnson Sep 25 '14 at 16:58
• By the way, Ruby Style Guide says that you should separate large numbers with underscores. See github.com/bbatsov/ruby-style-guide#underscores-in-numerics – Devon Parsons Sep 26 '14 at 13:43

Based on Array#[] and Enumerable#each_cons I think the first one is faster since the last one should create a new enumerable object for each loop. Also instead of transverse each sub-array twice for min and for max I prefer to use Enumerable#minmax so the code should looks like:

def find_deviation(values, m)
step = 0
temp_results = []
length = values.length
while(step < length) do
minmax = values[step, step = step + m].minmax
temp_results << minmax[1] - minmax[0]
end
temp_results.max
end


I run some benchmarks for both your original method and my method:

a. my method

                 user     system      total        real
step 10     29.070000   0.000000  29.070000 ( 29.073000)
step 100     2.920000   0.000000   2.920000 (  2.921683)
step 1000    0.300000   0.000000   0.300000 (  0.295665)
step 10000   0.030000   0.000000   0.030000 (  0.035206)


step 10      0.280000   0.000000   0.280000 (  0.286872)

• Let me try to explain, the values size is not important, the important is the m param, for small m your method is ok, for big m my method is ok – Aguardientico Sep 25 '14 at 16:58