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.

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

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`

.

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