8
\$\begingroup\$

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 , so the shortest code in bytes wins.

\$\endgroup\$
9
  • 1
    \$\begingroup\$ Are the integers bound/small like in your example? E.g. is radixsort or a bitmap possible? \$\endgroup\$
    – Christoph
    Nov 30, 2016 at 6:46
  • 2
    \$\begingroup\$ @Pavel The complexity depends very much on the set implementation, as far as I can tell. O(n log n) is doable in general, but the clarification about only handling native integers means that in some languages with limited integer ranges a linear solution is possible (e.g. by a 2^64 size lookup table) \$\endgroup\$
    – Sp3000
    Nov 30, 2016 at 8:57
  • \$\begingroup\$ By the way, I think that all hash-based solutions with arbitrary precision ranges should have to demonstrate that no collisions are possible or some other property to guarantee satisfaction of the requirement, because I'm not convinced about some of these answers... (with the current rules) \$\endgroup\$
    – Sp3000
    Nov 30, 2016 at 9:18
  • \$\begingroup\$ If the first array (N elements) is sorted it is Nlog(N) if for each element of 2 array search using "binary search" in 1 array it would be nlog(N) so the total is Nlog(N)+nlog(N)=(N+n)log(N) that is > to Nlog(N) claimed from the question ... So would remain "ascii tables"? \$\endgroup\$
    – user58988
    Nov 30, 2016 at 23:31
  • \$\begingroup\$ @RosLuP NLogN+NLogN is still O(NLogN) \$\endgroup\$
    – Pavel
    Nov 30, 2016 at 23:35

16 Answers 16

11
\$\begingroup\$

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

\$\endgroup\$
18
  • 1
    \$\begingroup\$ That's not a ASCII character, takes 3 bytes in UTF-8 \$\endgroup\$
    – Kh40tiK
    Nov 30, 2016 at 7:01
  • 7
    \$\begingroup\$ @Kh40tiK Actually uses CP437 for encoding. \$\endgroup\$
    – user45941
    Nov 30, 2016 at 7:02
  • 3
    \$\begingroup\$ This can't possibly be O(min(N, M)). It takes O(max(M,N)) time simply to read in both arrays! Somehow I doubt set intersection can be done that quickly, either. \$\endgroup\$
    – user62131
    Nov 30, 2016 at 7:05
  • 3
    \$\begingroup\$ Right, I just figured that out too. Set intersection is indeed O(min(N, M)); but converting the arrays to sets takes O(max(N, M)) time. So we were both right. \$\endgroup\$
    – user62131
    Nov 30, 2016 at 7:19
  • 2
    \$\begingroup\$ This is a pretty weird situation, because Python's being penalised for supporting integers. Perl doesn't, so it has a lower complexity for the same algorithm, because the choice of language is redefining what the problem is! We might need some rules on what counts as an integer, in order to make the problem fair. (Also, on whether randomized algorithms count if they run in O(n log n) for very high probability on any input; most languages have hash tables that work like that nowadays.) \$\endgroup\$
    – user62131
    Nov 30, 2016 at 10:48
3
\$\begingroup\$

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

\$\endgroup\$
3
  • 1
    \$\begingroup\$ Yes! that's glorious \$\endgroup\$
    – Nelson
    Nov 30, 2016 at 19:29
  • 1
    \$\begingroup\$ Does the execution plan generated for this query actually have the necessary runtime behavior? \$\endgroup\$ Dec 1, 2016 at 18:24
  • \$\begingroup\$ @user2357112 a valid point. This does not scale well, I had to cut some corners to keep it short. Can we keep it between you and me... and the rest of the world ? \$\endgroup\$ Dec 2, 2016 at 9:05
2
\$\begingroup\$

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.

\$\endgroup\$
3
  • 3
    \$\begingroup\$ Do you have any source to support that Ruby's built-in set intersection runs in O(n log n)? \$\endgroup\$ Nov 30, 2016 at 7:40
  • 1
    \$\begingroup\$ No, but the runtime seems to confirm it. \$\endgroup\$
    – G B
    Nov 30, 2016 at 7:48
  • 1
    \$\begingroup\$ Also, you should count the function, because the other version isn't a valid program, as it doesn't print anything at all. \$\endgroup\$ Nov 30, 2016 at 7:58
2
\$\begingroup\$

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.

\$\endgroup\$
6
  • \$\begingroup\$ perl -apE '$\|=($a{$_}|=$.)==3for@F}{' should have the same behavior for 17 less bytes ;-) \$\endgroup\$
    – Dada
    Nov 30, 2016 at 8:56
  • \$\begingroup\$ I was unaware of the -a flag. That does seem to help here, doesn't it? I think you can save another two bytes, though ($\|=}{ and print are the same length, and the latter allows you to avoid the -p flag and thus a byte of penalties; and ==3 can be replaced by >2 for another byte). Such a pity that $1, etc., are already variables, or we could save another three bytes by using the entire space of variable names as a hash table. \$\endgroup\$
    – user62131
    Nov 30, 2016 at 10:06
  • \$\begingroup\$ -a (and -F) are quite convenient on PPCG (more than on anagolf since over there it costs more)! Since you need a space after the print, it's the same length as -p ... $\=}{, but why not. (yea, it's sad we can't modify $1 etc.) \$\endgroup\$
    – Dada
    Nov 30, 2016 at 10:41
  • \$\begingroup\$ It's a character shorter; you had p$\|=}{ (seven characters, with the p being a penalty); I have print (six characters, including a space). I think you missed the | in your calculation just there. \$\endgroup\$
    – user62131
    Nov 30, 2016 at 10:43
  • 1
    \$\begingroup\$ Hum, you're right, I seem to be unable do count up to 6, such a shame. \$\endgroup\$
    – Dada
    Nov 30, 2016 at 10:46
2
\$\begingroup\$

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=
\$\endgroup\$
6
  • \$\begingroup\$ You can use set(a)&set(b) instead of calling the intersection method. \$\endgroup\$
    – Jakube
    Nov 30, 2016 at 11:50
  • \$\begingroup\$ If you do what Jakube says, remove the function definition and compare the intersection to {0} then you can get it down to 28 bytes: lambda a,b:set(a)&set(b)>{0} \$\endgroup\$
    – Kade
    Nov 30, 2016 at 14:03
  • 1
    \$\begingroup\$ Actually, {1}&{1} is truthy, while {1}&{2} is falsy. You can just do lambda a,b:a&b. \$\endgroup\$ Nov 30, 2016 at 19:07
  • \$\begingroup\$ @SeeOneRhino I would have to take input as sets then, right? Lists do not implement intersection. \$\endgroup\$
    – Yytsi
    Nov 30, 2016 at 20:48
  • \$\begingroup\$ @Kade Doesn't seem to work :/ I tried Python2 and Python3. Removing f= does work though. \$\endgroup\$
    – Yytsi
    Nov 30, 2016 at 20:55
2
\$\begingroup\$

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

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
8
  • 1
    \$\begingroup\$ I also can't comment on complexity, but you can shorten that to 23 bytes: !!(diff -inc -ex $A $B) \$\endgroup\$
    – briantist
    Nov 30, 2016 at 22:30
  • 1
    \$\begingroup\$ If you specifically exclude PowerShell v5, I think you can shave off another 2 bytes bytes by using -i instead of -inc, but in 5+ the -Information* common parameters make -i ambiguous. \$\endgroup\$
    – briantist
    Nov 30, 2016 at 22:32
  • 1
    \$\begingroup\$ My solution was complete; it was not meant to be put inside the if statement; you don't need it at all! Also v5 comes with Windows 10, and v5.1 comes with Server 2016. You can also download and install WMF5 as far back as, I believe, Windows 7/2008R2. It has been released for some time now! \$\endgroup\$
    – briantist
    Nov 30, 2016 at 23:01
  • 1
    \$\begingroup\$ Nice to see another PowerShell user around here. Two things - without some sort of definitive time complexity evaluation for Compare-Object, I'm skeptical that this is O(NlogN). Second, taking input via pre-defined variables is a no-no, so you'd need a param($a,$b) in front or similar. \$\endgroup\$ Dec 1, 2016 at 20:57
  • 1
    \$\begingroup\$ @wubs You shouldn't need the semicolon, so it's just param($A,$B)!!(diff -Inc -Ex $A $B) -- Then, save that as a .ps1 file and call it from the command line with the arrays as arguments, like PS C:\Scripts>.\same-element.ps1 @(1,2) @(2,3) \$\endgroup\$ Dec 2, 2016 at 14:58
2
\$\begingroup\$

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

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
  • 2
    \$\begingroup\$ If this is doing what I think it does (for each element in A, check whether it's in B), this has time complexity of O(n*m). \$\endgroup\$ Nov 30, 2016 at 7:42
1
\$\begingroup\$

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

\$\endgroup\$
2
  • \$\begingroup\$ Do you have any source to support that PHP's built-in set intersection runs in O(n log n)? \$\endgroup\$ Nov 30, 2016 at 8:02
  • \$\begingroup\$ @MartinEnder checking it... \$\endgroup\$
    – Mario
    Nov 30, 2016 at 8:04
1
\$\begingroup\$

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:

Log-log plot of execution time vs. input size

These tests were carried out using the GolfScript program ~2?.2*,/&, which takes an integer k, generates an arithmetic sequence of 2 × 2k elements, split it into two arrays of 2k 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 × 2k, 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 × (2k)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.)

\$\endgroup\$
0
\$\begingroup\$

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

\$\endgroup\$
0
\$\begingroup\$

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 :)

\$\endgroup\$
0
\$\begingroup\$

Python, 11 bytes

set.__and__

Builtin that takes 2 sets and does an intersection on them

\$\endgroup\$
0
\$\begingroup\$

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
\$\endgroup\$
2
  • \$\begingroup\$ This works in O(n*m), doesn't it? \$\endgroup\$
    – Pavel
    Nov 30, 2016 at 17:19
  • \$\begingroup\$ Yes it is O( n*m) but above they use set intersection that is O(n*m) too. Only my algo exit first than intersection... \$\endgroup\$
    – user58988
    Nov 30, 2016 at 17:35
0
\$\begingroup\$

Jelly, 2 bytes

œ&

Try it online!

Explanation

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.