Check if 2 arrays contain the same element

Question

Write a program which will take for input 2 integer arrays and return a truthy value if there exists an element which is present in both of arrays, or a falsy one otherwise. The obvious solution to this problem would be to iterate through each element in the first array and compare it against each element in the second, but here's the catch: Your program must have an algorithmic complexity of at most, in the worst case, O(NlogN), where N is the length of the longer array,

Test cases:

 {1,2,3,4,-5},{5,7,6,8} -> false
 {},{0}                 -> false
 {},{}                  -> false
 {1,2},{3,3}            -> false
 {3,2,1},{-4,3,5,6}     -> true
 {2,3},{2,2}            -> true

This is code-golf, so the shortest code in bytes wins.

Answer 1

Actually, 1 byte

∩

Try it online!

This is merely the set intersection built-in. The resultant value is the intersection of the two sets - a non-empty list (which is a truthy value) if there is an intersection, and an empty list (which is a falsey value) otherwise.

Complexity

According to the Python Wiki, set intersection has a worst-case time complexity of O(N*M) (where N and M are the lengths of the two sets). However, the time complexity is only that bad when the two sets contain distinct objects that all have the same hash value (for example, {"some string"} & {hash("some string")}). Since the set elements are only integers in this case (and no two integers hash to the same value unless they are equal), the actual worst-case complexity is O(min(N, M)) (linear in the length of the smaller of the two sets). The construction of each set is O(N) (linear in the number of elements), so the overall complexity is O(max(N, M)) (the complexity is dominated by the construction of the larger set).

Answer 2

TSQL, 40 37 36 bytes

SQL doesn't have arrays, it is using tables instead

Returns -1 for true or 0 for false

DECLARE @ table(a INT)
DECLARE @2 table(b INT)

INSERT @ values(1),(2),(3),(4),(-5)
INSERT @2 values(5),(6),(7),(8)

SELECT~-sign(min(abs(a-b)))FROM @,@2

Try it out

Answer 3

Perl, 25+1 = 26 bytes in collaboration with Dada

print 2<($a{$_}|=$.)for@F

Run with -a (1 byte penalty).

An improved version of the program below (which is kept around to see the history of the solution, and to show the solution I found by myself; it also has more explanation). The -a option reads space-separated arrays as the input, storing them in @F. We use the %a dictionary (accessed as $a{$_}) to store a bitmask of which input arrays the input is in, and print 1 every time we see an element in both arrays, i.e. a value higher than 2 inside the resulting bitmask (fortunately, a failing comparison returns the null string, so the print does nothing). We can't use say because a newline is truthy in Perl. Performance is asymptotically the same as the older version of the program (but faster in terms of constant factors).

Perl, 44+1 = 45 bytes

$a{"+$_"}|=$.for split}{$_={reverse%a}->{3}

Run with -p (1 byte penalty). Input one array per line, separating the elements by spaces.

This works via creating a hash table %a that stores a bitmask of the input arrays that a value has been seen in. If it's been seen in both the array on line 1 and on line 2, the bitmask will therefore store the value 3. Reversing the hash and seeing if 3 has a corresponding key lets us know if there are any values in common.

The complexity of this algorithm is O(n) if you consider hash creation to be constant time (it is, if you have bounded integers, like Perl does). If using bignum integers (which could be input into this program, as it leaves the input as a string), the complexity of the algorithm itself would nominally be O(n log n) for each hash creation, and O(n) for the hash reversal, which adds up to O(n log n). However, Perl's hashing algorithm suffers from potential O(n²) performance with maliciously selected input; the algorithm is randomized, though, to make it impossible to determine what that input is (and it's possible that it can't be triggered simply with integers), so it's debatable what complexity class it "morally" counts with. Luckily, this doesn't matter in the case where there's only finitely many possible distinct elements in the array.

This code will work for input other than integers, but it won't work for more than two arrays (because the 3 is hardcoded and because input on the third line wouldn't bitmask correctly, as it isn't a power of 2). Rather annoyingly, the code naturally returns one of the duplicate elements, which is truthy in almost all cases, but "0" is falsey in Perl and a valid duplicate element in the array. As such, I had to waste three bytes prepending a + to the output, which is the cheapest way I found to give a truthy output in the edge case of the arrays overlapping at 0. If I'm allowed to use notions of truthy and falsey from a language other than Perl (in which any nonempty string is truthy), you can change "+$_" to $_ to save three bytes.

Answer 4

Ruby, 37 bytes:

exit ($*.map{|x|eval x}.reduce:&)!=[]

As in the definition: "program which will take for input 2 integer arrays and return a truthy value if...", this is a program, accepts 2 arrays as strings in input, returns true or false.

as a function - 14 bytes:

->a,b{a&b!=[]}

Complexity:

The ruby documentation of the itnersection (&) operator says "It compares elements using their hash and eql? methods for efficiency.", which I suppose is exactly what we are looking for.

Empirically:

$ time ruby a.rb "[*1..1000001]" "[*1000001..2000000]"

real    0m0.375s
user    0m0.340s
sys 0m0.034s

$ time ruby a.rb "[*1..2000001]" "[*2000001..4000000]"

real    0m0.806s
user    0m0.772s
sys 0m0.032s

$ time ruby a.rb "[*1..4000001]" "[*4000001..8000000]"

real    0m1.932s
user    0m1.857s
sys 0m0.073s

$ time ruby a.rb "[*1..8000001]" "[*8000001..16000000]"

real    0m4.464s
user    0m4.336s
sys 0m0.119s

Which seems to confirm it.

Answer 5

Python2 - 41 30 bytes

lambda a,b:bool(set(a)&set(b))

Set intersection: O(min(N,M)) where N and M are the length of the sets.

Conversion from a list to a set: O(max(N,M))

• Thanks to Jakube for saving 9 bytes! set(a).intersection(b) -> set(a)&set(b)
• Thanks to Kade for saving 2 bytes! -> removed f=

Answer 6

PowerShell, 88 78 77 23 bytes

!!(diff -Inc -Ex $A $B)

Thanks to @briantist for shaving off a whopping 54 bytes from my original, more verbose answer by shortening -IncludeEqual, -ExcludeDifferent, and -Not!

if(-Not(diff -IncludeEqual -ExcludeDifferent $A $B)){("false")}else{("true")}

I can't find the source for Compare-Object (diff is an alias for Compare-Object), so I'm not certain on the time complexity.

Answer 7

Axiom, 439 bytes

c:=0;s(x,y)==(free c;if x.1=%i and y.2=%i then(x.2<y.1=>return true;x.2>y.1=>return false;c:=1;return false);if x.2=%i and y.1=%i then(x.1<y.2=>return true;x.1>y.2=>return false;c:=1;return false);if x.1=%i and y.1=%i then(x.2<y.2=>return true;x.2>=y.2=>return false);if x.2=%i and y.2=%i then(x.1<y.1=>return true;x.1>=y.1=>return false);false);r(a,b)==(free c;c:=0;m:=[[%i,j] for j in a];n:=[[i,%i] for i in b];r:=merge(m,n);sort(s,r);c)

this convert the first list in a list as [[i,1], [i,2]...] the second list in a list as [[1,i], [0,i]...] where i is the variable imaginary than merge the 2 list, and make one sort that would find if there is one element of list 1 in the list 2 so it is at last O(N log N) where N=lenght list 1 + lenght list 2

ungolfed

-- i get [0,0,1,2,3] and [0,4,6,7]  and build [[%i,0],[%i,0],[%i,1],[%i,2] [%i,3],[0,%i],..[7,%i]]
c:=0
s(x:List Complex INT,y:List Complex INT):Boolean==
  free c  -- [%i,n]<[n,%i]
  if x.1=%i and y.2=%i then
    x.2<y.1=> return true 
    x.2>y.1=> return false
    c:=1
    return false
  if x.2=%i and y.1=%i then
    x.1<y.2=>return true
    x.1>y.2=>return false
    c:=1
    return false
  if x.1=%i and y.1=%i then
    x.2< y.2=>return true
    x.2>=y.2=>return false
  if x.2=%i and y.2=%i then
    x.1< y.1=>return true
    x.1>=y.1=>return false
  false


r(a,b)==
  free c
  c:=0
  m:=[[%i, j]  for j in a]
  n:=[[ i,%i]  for i in b]
  r:=merge(m,n)
  sort(s, r)
  c

results

(12) -> r([1,2,3,4,-5], [5,7,6,8]), r([],[0]), r([],[]), r([1,2],[3,3]), r([3,2,1],[-4,3,5,6]), r([2,3],[2,2])
   Compiling function r with type (List PositiveInteger,List Integer)
       -> NonNegativeInteger
   Compiled code for r has been cleared.
   Compiled code for s has been cleared.
   Compiling function r with type (List PositiveInteger,List
  PositiveInteger) -> NonNegativeInteger
   Compiled code for r has been cleared.
   Compiling function s with type (List Complex Integer,List Complex
      Integer) -> Boolean
   Compiled code for s has been cleared.

   (12)  [0,0,0,0,1,1]
                                           Type: Tuple NonNegativeInteger

i dont understand why it "clears" code for r and s...

Answer 8

PHP, 15 bytes

array_intersect

Try it online!

A PHP built-in, as a callable/lambda function. Return is a PHP truthy/falsey testable value. Also, per the other PHP submission, this implementation should meet the challenge complexity requirements (StackExchange).

Answer 9

R, 23 bytes

sum(scan()%in%scan())>0

If we assume that there will always be one and only one element matching and that 1 is a truthy value (which it is in R), then we can write :

sum(scan()%in%scan())

which is 21 bytes.

Answer 10

PHP, 55 51 bytes

<?=count(array_intersect($_GET[a],$_GET[b]))<1?0:1;

Usage: save in a file and call from browser:

intersect.php?a[]=1&a[]=2&a[]=3&b[]=0&b[]=4&b[]=5 outputs 0 for false.

intersect.php?a[]=1&a[]=2&a[]=3&b[]=0&b[]=4&b[]=1 outputs 1 for true.

About complexity, I couldn't find references but according to this StackOverflow's post the script should be OK

Answer 11

GolfScript, 1 byte

If taking the input directly as arrays on the stack is allowed, this one-byte GolfScript solution should meet the spec:

&

If text-based I/O is required, the input needs to be evaluated first, pushing the length up to two bytes:

~&

Both of these solutions use the GolfScript array intersection operator, which is implemented using the corresponding operator in Ruby. They return an empty array (which is falsy) if the arrays contain no matching elements, or a non-empty array (which is truthy) containing all the matching elements otherwise.

I have so far not been able to find any documentation on the internal implementation or asymptotic complexity of the Ruby array intersection operator, beyond the brief statement that "It compares elements using their hash and eql? methods for efficiency." However, a reasonable implementation using hash tables would run in O(n) time (assuming that hashing and comparisons are O(1)), and some quick performance testing suggests that this is indeed the case:

These tests were carried out using the GolfScript program ~2?.2*,/&, which takes an integer k, generates an arithmetic sequence of 2 × 2^k elements, split it into two arrays of 2^k elements and computes their (obviously empty) intersection. The red stars show the measured execution time t in seconds (on a logarithmic scale) for various values of k, while the green line plots the function t = c × 2^k, where the scaling constant c ≈ 2^−17.075 was chosen to best fit the measured data.

(Note that, on a log-log plot like this, any polynomial function of the form t = c × (2^k)^a would yield a straight line. However, the slope of the line depends on the exponent a, and the data is certainly consistent with a = 1 as shown by the green line above. FWIW, the numerical best-fit exponent for this data set was a ≈ 1.00789.)

Answer 12

JavaScript (ES6), 39 bytes

(a,b,c=new Set(b))=>a.some(e=>c.has(e))

Will be worse than O(n+m) but hopefully not as bad as O(n*m).

Answer 13

Rust, 103 bytes

|a:&[i32],b:&[i32]|!b.iter().collect::<std::collections::HashSet<_>>().is_disjoint(&a.iter().collect())

Takes two array slices (or references to full arrays, they dereference to slices automatically), bundles them up into sets, and checks for non-disjointness. I'm not quite sure how set union is implemented in the Rust standard library, but it should be O(n + m) at worst.

Without using collections, the easiest alternative I see is to sort both arrays, then step over them carefully to look for duplicates. Something like this

fn overlapping(a: &Vec<i32>, b: &Vec<i32>) -> bool{
    let mut sa = a.clone();
    sa.sort();
    let mut sb = b.clone();
    sb.sort();
    let mut ai = 0;
    let mut bi = 0;
    while ai < a.len() && bi < b.len() {
        if sa[ai] < sb[bi] {
            ai += 1;
        } else if sa[ai] > sb[bi] {
            bi += 1;
        } else{
            return true;
        }
    }
    false
}

But that requires too much mutation to be fun to golf in Rust IMO :)

Answer 14

Axiom, 50 221 bytes

binSearch(x,v)==(l:=1;h:=#v;repeat(l>h=>break;m:=(l+h)quo 2;x<v.m=>(h:=m-1);x>v.m=>(l:=m+1);return m);0);g(a,b)==(if #a>#b then(v:=a;w:=b)else(v:=b;w:=a);c:=sort(v);for x in w repeat(if binSearch(x,c)~=0 then return 1);0)

ungolfed

--suppose v.1<=v.2<=....<=v.#v
--   binary serch of x in v, return the index i with v.i==x
--   return 0 if that index not exist
--traslated in Axiom from C  book
--Il Linguaggio C, II Edizione 
--Brian W.Kerninghan, Dennis M.Ritchie
binSearch(x,v)==
    l:=1;h:=#v  --1  4
    repeat
       l>h=>break
       m:=(l+h)quo 2   --m=(4+1)/2=5/2=2
                       --output [l,m,h]
       x<v.m=>(h:=m-1) --l x m  h =>  
       x>v.m=>(l:=m+1)
       return m
    0


g(a,b)==   
  if #a>#b then (v:=a;w:=b)
  else          (v:=b;w:=a)
  c:=sort(v)
  --output c
  for x in w repeat(if binSearch(x,c)~=0 then return 1)
  0

g(a,b) gets the more big array beetwin a and b; suppose it has N elements: sort that array, do binary search with elements that other array. This would be O(Nlog(N)). It return 0 for no element of a in b, 1 otherwise.

results

(6) ->  g([1,2,3,4,-5], [5,7,6,8]), g([],[0]), g([],[]), g([1,2],[3,3]), g([3,2,1],[-4,3,5,6]), g([2,3],[2,2])
   Compiling function binSearch with type (PositiveInteger,List Integer
      ) -> NonNegativeInteger

   (6)  [0,0,0,0,1,1]
                                           Type: Tuple NonNegativeInteger

Answer 15

Python, 11 bytes

set.__and__

Builtin that takes 2 sets and does an intersection on them

Answer 16

Jelly, 2 bytes

œ&

Try it online!

Explanation

 œ&  Main link. Arguments: x y
⁸    (implicit) x
   ⁹ (implicit) y
 œ&  Intersection of x and y