CODEWITHSUNDEEP
phparrays
Fero
Fero

Reputation: 13315

Best way to return the first repeated element of array

This is an interview question:

What is the best way to return the first repeated element out of the array of integers?

Example:

Given an array [12, 46, 244, 0, 12, 83, 48, 98, 233, 83, 26, 91, 119, 148, 98].

The return value in this case is 12.

How can this be done?

Upvotes: 8

Views: 6247

Answers (13)

kapa
kapa

Reputation: 78731

This will give you all the duplicate values and their original positions:

$diff = array_diff_assoc($array, array_unique($array));
var_dump($diff);

result:

array(3) { 
  [4]=> int(12) 
  [9]=> int(83)
  [14]=> int(98) 
}

Upvotes: 9

Syed Sharique
Syed Sharique

Reputation: 56

Or you could use array_count_values() function to fetch that.

    $arr = array(12, 46, 244, 0, 12, 83, 48, 98, 233, 83, 26, 91, 119, 148, 98);
    $freq_arr = array_count_values($arr);

    echo $freq_arr[0];

See here on PHP Manual.

Upvotes: -1

Shivendra
Shivendra

Reputation: 1558

        here N is size of array and A is array,
        step1:add N to index of the value
        step2:traverse the array and find the first number which has frequency 
              greater than 1 break there.

O(n) with O(1) size complexity!

                for(int i=0;i<N;++i)
                        A[A[i]%N]+=N;

                    int val,freq;
                    for(int i=0;i<N;++i)
                    {
                        val=A[i]%N;
                        freq=A[val]%N;
                        if(freq>1)
                        {
                            cout<<val;
                            break;
                        }
                    }

Upvotes: 0

johnlemon
johnlemon

Reputation: 21489

$arr = array(12, 46, 244, 0, 12, 83, 48, 98, 233, 83, 26, 91, 119, 148, 98);
$arrHelp = array();
foreach($arr as $int) {
    if (in_array($int, $arrHelp)) {
        echo $int;
        break;
    }
    else {
        array_push($arrHelp, $int);
    }
}

Upvotes: 0

Haim Evgi
Haim Evgi

Reputation: 125564

i think that if you look of performance, foreach loop is the faster

# temp array
$array_help = array();

# run over the array
foreach ($array as $val) {

    if (isset($array_help[$val]))
     # found if is set already !
        return $val;

    else
       # its the first time this value appear
       $array_help[$val] = 1;
}

Upvotes: 11

Nilesh Dharmik
Nilesh Dharmik

Reputation: 9

$array = array(12, 46, 46, 0, 18, 83, 48, 98, 233, 83, 26, 91, 119, 148, 98);
$count_array = array_count_values($array);
foreach($count_array as $key=>$value)
{
    if($value>=2)
    {
       echo $key;
       break;
    }

}

Upvotes: 0

richard
richard

Reputation: 21

$arrs = array(12, 46, 244, 0, 12, 83, 48, 98, 233, 83, 26, 91, 119, 148, 98);

// or a associate array like as $arrs = array('a'=>12, 'b'=>46, 'c'=>244, 'd'=>0, 'e'=>12, 'f'=>83, 'g'=>48, 'h'=>98, 'i'=>233, 'j'=>83, 'k'=>26, 'l'=>91, 'm'=>119, 'n'=>148, 'o'=>98);

$data = "12, 46, 244, 0, 12, 83, 48, 98, 233, 83, 26, 91, 119, 148, 98";

static $repeat  = '';

foreach($arrs as $arr){

   if (substr_count($data,$arr)>1) {

     $repeat = $arr;
     break; 
  }

}

if ($repeat) echo 'The first repeated element out of the array of integers is '.$repeat;

Upvotes: 2

richard
richard

Reputation: 21

$arrs = array(12, 46, 244, 0, 12, 83, 48, 98, 233, 83, 26, 91, 119, 148, 98);

static $repeat  = '';

foreach($arrs as $arr) {

   if ((count(array_keys($arrs,$arr))) > 1) {

        $repeat = $arr;
        break;

   }

}

if ($repeat) echo 'The first repeated element out of the array of integers is '.$repeat;


//This solution is working for associate array too, for example:

// $arrs = array('a'=>12, 'b'=>46, 'c'=>244, 'd'=>0, 'e'=>12, 'f'=>83, 'g'=>48, 'h'=>98, 'i'=>233, 'j'=>83, 'k'=>26, 'l'=>91, 'm'=>119, 'n'=>148, 'o'=>98);

Upvotes: 0

Mr Coder
Mr Coder

Reputation: 8186

a loopless solution using recursion . I think it will be fastest but take more memory. Fast because size of array keep on decreasing as we move ahead hence less workload on cpu. 

 $data = array(46, 12, 244, 0, 12, 83, 48, 98, 233, 83, 26, 91, 119, 148, 98);


    function find(&$input)
    {
    $current = array_shift($input);
    if(in_array($current,$input))
    {
    return $current;
    }
    return find($input);
    }

    echo find($data);

Upvotes: 0

Mark Baker
Mark Baker

Reputation: 212452

$testData = array(46, 12, 244, 0, 12, 83, 48, 98, 233, 83, 26, 91, 119, 148, 98);

function repeated($val) {
    return $val > 1;
}

$firstRepeatedElement = array_shift(array_keys(array_filter(array_count_values($testData),'repeated')));

Upvotes: 1

Andy E
Andy E

Reputation: 344675

You could use array_unique to remove all the duplicate values, then iterate over the original and resulting arrays and return the first value that doesn't appear in the resulting array. Something like this:

$arr = array(12, 46, 244, 0, 12, 83, 48, 98, 233, 83, 26, 91, 119, 148, 98);

function first_dupe($arr) {
    $res = array_unique($arr);

    foreach ($arr as $key => $val) {
        if ($res[$key] !== $val)
            return $val;
    }
}

echo first_dupe($arr);

Working demo: http://codepad.org/atFMrhLW.

Upvotes: 3

alex
alex

Reputation: 490423

function getFirstRepetition($array) {
    $prev = array();
    foreach($array as $value) {

        if (in_array($value, $prev)) {
            return $value;
        }

        $prev[] = $value;
    }
    return FALSE;
}

CodePad.

Upvotes: 0

KingCrunch
KingCrunch

Reputation: 132011

function findDuplicate ($array) {
  while (($item = array_shift($array)) !== null) {
    if (in_array($item, $array)) return $item;
  }
}

Upvotes: 3

Related Questions