dines dines - 1 month ago 6
Ruby Question

Advice needed with optimization when solving Kata's

I'm doing Katas at codewars and I on occasion pass all the tests but fail due to timeout reasons. Could you please help with comments on how to improve my code by refactoring the code below.

arrA
and
arrB
are arrays,
rng
is a range and
wanted
is either "odd" or "even". I need to return an array that holds numbers that exists more than once in each array, and is within the range and is either odd or even.

def find_arr(arrA, arrB, rng, wanted)
common = arrA && arrB

range = (rng[0]..rng[1]).to_a.select {|num| common.include?(num)}

range_wanted = range.select {|num| wanted == "odd" ? num.odd? : num.even?}

numbers_twice = range_wanted.select {|num| arrA.count(num) > 1 && arrB.count(num) > 1}
end

Answer

There is a lot of issues here, mainly time complexity is O(n^2) because of the last line which counts number occurrences in both arrays. For each number in range_wanted it needs to iterate over all elements of both arrays. This is highly inefficient.

Try to run your code in irb with those arguments find_arr([], [], [1, 10_000_000], "odd") or bigger range.

Here are some suggestions how to improve this code:

  1. Count occurrences yourself by storing them in a hash
  2. When counting you can skip those numbers that don't meet requirements, range and odd/even
  3. If you want to check if value is in a range, you should use cover? method from Range class. Do not change range into array and iterate over it.
  4. In this line range_wanted = range.select {|num| wanted == "odd" ? num.odd? : num.even?} you are testing wanted == "odd" in every iteration, but this won't ever change as it is passed as argument. You can move this condition outside of loop

Here is refactored code. I wrote it out of my head, so there may be some issues but it should give you an idea on how to write your own solution.

def find_arr(arrA, arrB, rng, wanted)
  countA = Hash.new(0)
  countB = Hash.new(0)

  # If wanted == "odd" we want to test elem % 2 == 1, otherwise elem % 2 == 0
  remainder = wanted == "odd" ? 1 : 0
  range = (rng[0]..rng[1])

  arrA.each do |elem|
    if range.cover?(elem) && (elem % 2 == remainder)
      countA[elem] += 1
    end
  end

  arrB.each do |elem|
    if range.cover?(elem) && (elem % 2 == remainder)
      countB[elem] += 1
    end
  end

  result = []

  countA.each do |elem, count|
    if count > 1 && countB[elem] > 1
      result.push(elem)
    end
  end

  result
end