Best way to return the first repeated element of a

Question

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?

Answer 1

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.

Answer 2

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

Answer 3

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

Answer 4

$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')));

Answer 5

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

Answer 6

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