check whether any number in one array is less than some number in the other array

Question

This seems like a pretty common question. Sadly I could not find it on SO. If this is a duplicate question; I apologize for that.

Say I have two integer arrays A and B:

A = [17, 3, 9, 11, 11, 15, 2]
B = [1, 13]

I need to return a true or a false if any element of array A is less than any element of array B.

The trivial way to do this was use 2 each loops (O(n^2) complexity)

def is_greater?(a,b)
  retVal = false
  b.each { |element|
    a.each { |value|
      if (value < element)
        retVal = true
        break
      end
    }
  }
  return retVal
end

is_greater?(A,B) => true

I also sorted out the elements in both the arrays and then used a single while loop to determine whether the element in A is less than that in B.

A.sort!
B.sort!
def is_greater?(a,b)
  retVal = false
  i = 0
  j = 0
  while (i < a.length && j < b.length)
    if (a[i] < b[j])
      retVal = true
      break
    elsif (a[i] == b[j])
      i = i + 1
      j = j + 1
    else
     j = j + 1
    end
  end
  return retVal
end

is_greater?(A,B) => true

I was wondering whether there is an efficient, precise way to do it in terms of lines of code. I was trying to figure out how to use the any? block, but it did not make any sense to me.

Answer 1

Yes, you can use Enumerable methods #any? and #min

For each item in a, return true if it is less than max:

max = b.max
a.any?{|x| x < max}  

Answer 2

It should be enough to just check the minimum of the first array against the maximum of the second.

a.min < b.max

The only way this conditional returns false is if every element is b is less than every element in a.

The complexity is O(m+n) which is the single iteration through both a and b.