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

5

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.

2012-04-04 18:04
by chaitanya

18

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}
``````
2012-04-04 18:16
by joelparkerhenderson
thanks! i used this solution with the max value storing advice given by @TCoppl - chaitanya 2012-04-04 18:45

5

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`.

2012-04-04 18:31
by TCopple
atleast its linear rather than O(nlogn) and O(n^2) solutions which I proposed. Thanks for the max value caching ti - chaitanya 2012-04-04 18:44
It is actually `O(2n) = O(n)` (Product rule with constant) when `m ~= n`, not `O(n logn)`. It is the same as the other solution - texasbruce 2012-04-04 18:54
I like this one : - fl00r 2012-04-04 19:22
@texasbruce I don't know if you're talking about my solution, but if you are I agree it reduces to the same complexity as the other answer. But.... m = len(a) and n = len(b), which is not O(2n) cause n can only represent the length of one array - TCopple 2012-04-04 20:44
@texasbruce The O(n logn) was the complexity of the sorting solution which I gave, TCopple's solution has the complexity O(m+n).. essentially its linea - chaitanya 2012-04-04 20:59
@TCopple well the problem is that any element and not every element is required to be less tha - chaitanya 2012-04-04 22:57
Yeah that's why I said m ~= n, meaning approximately equal, and yes it is linear - texasbruce 2012-04-04 23:54
The algorithm complexity is O(m+n). O(m+n) = O(2n) = O(n) if and only if m = - texasbruce 2012-04-04 23:58