1

Given two arrays of strings, A and B.

B contains every element in A, and has one additional member, for example:

A = ['dog', 'cat', 'monkey]
B = ['cat', 'rat', 'dog', 'monkey']

I need to write a function to find the extra string in B using O(n). Please help!

UPDATE: I know the difference can be achieved using PHP in-built function array_diff().

Undo
  • 25,519
  • 37
  • 106
  • 129
Anup Khandelwal
  • 365
  • 2
  • 6
  • 23

2 Answers2

1

You're looking for the built-in function array_diff:

$A = array('dog', 'cat', 'monkey');
$B = array('cat', 'rat', 'dog', 'monkey');
$difference = array_diff($B, $A);

Test here

Official documentation

Joren
  • 3,068
  • 25
  • 44
  • I don't want built-in PHP function. I did mention using big-O notation. – Anup Khandelwal Oct 27 '13 at 11:02
  • 1
    Why reinvent the wheel? This is the most efficient solution since built-in PHP functions are heavily tested and optimized. – Joren Oct 27 '13 at 11:04
  • 1
    @Joren clearly it's a learning exercise. `array_diff` isn't something that is available out of the box across all languages - people these days use existing code too readily without understanding the implementation. Yes, using the internal functionality will be faster and best-practice but asking *how* it works and what the alternatives are surely can't be a bad thing! – Emissary Oct 27 '13 at 11:50
  • 1
    Here is the C implementation used by PHP: http://lxr.php.net/xref/PHP_5_5/ext/standard/array.c#3441 – ComFreek Oct 27 '13 at 12:14
1

I hope it can help you

$A = array('dog', 'cat', 'monkey');
$B = array('cat', 'rat', 'dog', 'monkey');

function arrayDiff($A, $B) {
    $out = array();
    foreach($B as $b) $out[$b] = 1;
    foreach($A as $a) unset($out[$a]);
    return array_keys($out);
}

print_r(arrayDiff($A, $B));

If you do not want to use array_keys() change function as following

function arrayDiff($A, $B) {
    $res = $out = array();
    foreach($A as $a) $out[$a] = 1;
    foreach($B as $b) if(!isset($out[$b])) $res[] = $b;
    return $res;
}
MD SHAHIDUL ISLAM
  • 14,325
  • 6
  • 82
  • 89