Complexity with Array.min

I have an array:

[0, 0, 0, 0, 0, 0, 0, 1, 2, 3]

I need to figure out index of the minimal element which is not zero. How do I do that?

From stackoverflow

• I don't know Ruby, so I can't offer code, but the process that immediately springs to my mind is:

  1. Create a copy of the array (if needed)
  2. Remove all the 0 entries
  3. Check the minimum value in the new array
  JacobM : That won't determine the index (in the original array) unless you add step 4 where you go back to the original array and search for the value you found in step 3. Not the most efficient approach.

  Matthew Scharley : Good point Jacob.

• For ruby 1.8.7+:

  >> [0,0,2,0,1,3].each_with_index.reject {|(e, i)| e == 0}
  => [[2, 2], [1, 4], [3, 5]]
  >> [0,0,2,0,1,3].each_with_index.reject {|(e, i)| e == 0}.min
  => [1, 4]
  >> [0,0,2,0,1,3].each_with_index.reject {|(e, i)| e == 0}.min[1]
  => 4
  

  For ruby 1.8.6:

  a.zip((0...a.size).to_a).reject {|(e, i)| e == 0}.min[1]
  

  (solution by chuck)

  gmile : what's the difference between `inject` and `reject`?

  Chuck : @gmile: They're completely unrelated. `inject` reduces the array to a single accumulated value while `reject` returns a version of the array that doesn't include objects for which the given block returns true.

  sepp2k : reject deletes elements which meet a certain condition (well, actually reject returns an array containing the elements of the original array that do not meet the condition - it does not actually affect the original array). inject, which is quite different, creates an object by basically performing obj = f(obj, element) for each element of the array given a function f (the block) and a starting object. Most other enumerable operations can be expressed in terms of inject, but that doesn't mean they should be ;-)

  Chuck : Incidentally, this implementation has the (IMO desirable) property that if the minimum value occurs more than once, it will always return the first occurrence.

  glenn jackman : `reject` being the opposite of `select`

  gmile : shoot... i've just figured out that i'm on 1.8.6 (because of it's only compatibility with Qt) :(

  Chuck : For 1.8.6 compatibility, you should be able to replace the `each_with_index` call with `zip((0...a.size).to_a)`. So in all, `a.zip((0...a.size).to_a).reject {|(e, i)| e == 0}.min[1]`.

  gmile : Great Thanks, Chuck!

• Simplest way: check each element of the array, keep a variable that is the minimum, set it equal to the first number you come across (unless 0, then discard and use next number). Any time you come across a number smaller than your minimum, set it to your minimum. And, of course, discard any zero rather than setting your minimum.

  More efficient: It appears we have a sorted array, if we can use that to our advantage, we can use a better search mechanism, such as quick-search or binary-search. I will describe binary search as it is easy to understand.

  Our array is in ascending order. Check the middle most element, set it equal to your minimum (unless 0). Split the array in half on this middle element. Since the array is ascending, check the middle point of the left half (unless element was 0, then check right). Continue until there is only one element to the left when you split. That is your minimum.

  Pesto : +1: This process is faster than going through the array, generating a new array, and then finding the min on that array as proposed in the accepted answer.

• a=[0, 0, 0, 0, 0, 0, 0, 1, 2, 3]
  i=a.index a.reject{|x|x==0}.min
  

  (i=7)