Return to Answer

Some notes:

• find_deviation(v, d): Try to write more meaningful names for variables. Specially, I'd give a plurar name to v, since it's a collection.

• max = 0, each, inline if: All of this denote you think in imperative terms. Some notes on functional programming with Ruby.

I'd write, with a functional approach:

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

Now, this function has exactly the same time complexity than yours (though it may be faster or slower depending on how Ruby works). The complexity is: len(values) = n -> O(n*m). Note that you can use Enumerable#minmax to avoid one traversal, but it's still the same complexity.

To make it faster here's an idea, even though it's not trivial to implement: use a structure with O(log n) times for insertion/deletion/max/min (a binary search tree is ideal for this) to hold values of the sliding window, this way the overall complexity is O(nlog m). I guess some of the tests have big values of m so the trivial approach O(nm) is too slow.

[edit] Just for fun, I wrote a O(n log m) implementation, it's pretty fast (sorry, in Haskell, I found no BST gem for Ruby):

deviation :: (Num a, Ord a) => [a] -> Int -> a 
deviation [] _ = 0
deviation xs m = maximum $ [Tree.maximum w - Tree.minimum w | w <- windows]
  where
    windows = scanl shift (Tree.fromList $ take m xs) (zip xs (drop m xs))
    shift window (old, new) = Tree.insert (Tree.delete window old) new

Some notes:

• find_deviation(v, d): Try to write more meaningful names for variables. Specially, I'd give a plurar name to v, since it's a collection.

• max = 0, each, inline if: All of this denote you think in imperative terms. Some notes on functional programming with Ruby.

I'd write, with a functional approach:

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

Now, this function has exactly the same time complexity than yours (though it may be faster or slower depending on how Ruby works). The complexity is: len(values) = n -> O(n*m). Note that you can use Enumerable#minmax to avoid one traversal, but it's still the same complexity.

To make it faster here's an idea, even though it's not trivial to implement: use a structure with O(log n) times for insertion/deletion/max/min (a binary search tree is ideal for this) to hold values of the sliding window, this way the overall complexity is O(nlog m). I guess some of the tests have big values of m so the trivial approach O(nm) is too slow.

[edit] Just for fun, I wrote a O(n log m) implementation in Haskell (I found no BST gem for Ruby):

deviation :: (Num a, Ord a) => [a] -> Int -> a 
deviation [] _ = 0
deviation xs m = maximum $ [Tree.maximum w - Tree.minimum w | w <- windows]
  where
    windows = scanl shift (Tree.fromList $ take m xs) (zip xs (drop m xs))
    shift window (old, new) = Tree.insert (Tree.delete window old) new

Some notes:

• find_deviation(v, d): Try to write more meaningful names for variables. Specially, I'd give a plurar name to v, since it's a collection.

• max = 0, each, inline if: All of this denote you think in imperative terms. Some notes on functional programming with Ruby.

I'd write, with a functional approach:

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

Now, this function has exactly the same time complexity than yours (though it may be faster or slower depending on how Ruby works). The complexity is: len(values) = n -> O(n*m). Note that you can use Enumerable#minmax to avoid one traversal, but it's still the same complexity.

To make it faster here's an idea, even though it's not trivial to implement: create a binary search tree containing the elements in the sliding window (of length m), this way insertion/deletion operations are O(log m) and the overall complexity is O(nlog m). I guess some of the tests have big values of m so the trivial approach O(nm) is too slow.

[edit] Just for fun, I wrote a O(n log m) implementation, it's pretty fast (sorry, in Haskell, I found no BST gem for Ruby):

deviation :: (Num a, Ord a) => [a] -> Int -> a 
deviation [] _ = 0
deviation xs m = maximum $ [Tree.maximum w - Tree.minimum w | w <- windows]
  where
    windows = scanl shift (Tree.fromList $ take m xs) (zip xs (drop m xs))
    shift window (old, new) = Tree.insert (Tree.delete window old) new

Some notes:

• find_deviation(v, d): Try to write more meaningful names for variables. Specially, I'd give a plurar name to v, since it's a collection.

• max = 0, each, inline if: All of this denote you think in imperative terms. Some notes on functional programming with Ruby.

I'd write, with a functional approach:

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

Now, this function has exactly the same time complexity than yours (though it may be faster or slower depending on how Ruby works). The complexity is: len(values) = n -> O(n*m). Note that you can use Enumerable#minmax to avoid one traversal, but it's still the same complexity.

To make it faster here's an idea, even though it's not trivial to implement: use a structure with O(log n) times for insertion/deletion/max/min (a binary search tree is ideal for this) to hold values of the sliding window, this way the overall complexity is O(nlog m). I guess some of the tests have big values of m so the trivial approach O(nm) is too slow.

[edit] Just for fun, I wrote a O(n log m) implementation, it's pretty fast (sorry, in Haskell, I found no BST gem for Ruby):

deviation :: (Num a, Ord a) => [a] -> Int -> a 
deviation [] _ = 0
deviation xs m = maximum $ [Tree.maximum w - Tree.minimum w | w <- windows]
  where
    windows = scanl shift (Tree.fromList $ take m xs) (zip xs (drop m xs))
    shift window (old, new) = Tree.insert (Tree.delete window old) new

Some notes:

• find_deviation(v, d): Try to write more meaningful names for variables. Specially, I'd give a plurar name to v, since it's a collection.

• max = 0, each, inline if: All of this denote you think in imperative terms. Some notes on functional programming with Ruby.

I'd write, with a functional approach:

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

Now, this function has exactly the same time complexity than yours (though it may be faster or slower depending on how Ruby works). The complexity is: len(values) = n -> O(n*m). Note that you can use Enumerable#minmax to avoid one traversal, but it's still the same complexity.

To make it faster here's an idea, even though it's not trivial to implement: create a binary search tree containing the elements in the sliding window (of length m), this way insertion/deletion operations are O(log m) and the overall complexity is O(nlog m). I guess some of the tests have big values of m so the trivial approach O(nm) is too slow.

[edit] Just out of fun I made a O(n log m) implementation, it's very very fast (sorry, Haskell, I found no BST gem for Ruby):

deviation :: (Num a, Ord a) => [a] -> Int -> a 
deviation [] _ = 0
deviation xs m = maximum $ [Tree.maximum w - Tree.minimum w | w <- windows]
  where
    windows = scanl shift (Tree.fromList $ take m xs) (zip xs (drop m xs))
    shift window (old, new) = Tree.insert (Tree.delete window old) new

Some notes:

• find_deviation(v, d): Try to write more meaningful names for variables. Specially, I'd give a plurar name to v, since it's a collection.

• max = 0, each, inline if: All of this denote you think in imperative terms. Some notes on functional programming with Ruby.

I'd write, with a functional approach:

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

Now, this function has exactly the same time complexity than yours (though it may be faster or slower depending on how Ruby works). The complexity is: len(values) = n -> O(n*m). Note that you can use Enumerable#minmax to avoid one traversal, but it's still the same complexity.

To make it faster here's an idea, even though it's not trivial to implement: create a binary search tree containing the elements in the sliding window (of length m), this way insertion/deletion operations are O(log m) and the overall complexity is O(nlog m). I guess some of the tests have big values of m so the trivial approach O(nm) is too slow.

[edit] Just for fun, I wrote a O(n log m) implementation, it's pretty fast (sorry, in Haskell, I found no BST gem for Ruby):

deviation :: (Num a, Ord a) => [a] -> Int -> a 
deviation [] _ = 0
deviation xs m = maximum $ [Tree.maximum w - Tree.minimum w | w <- windows]
  where
    windows = scanl shift (Tree.fromList $ take m xs) (zip xs (drop m xs))
    shift window (old, new) = Tree.insert (Tree.delete window old) new