CODEWITHSUNDEEP
phparraysduplicates
Roman
Roman

Reputation: 1168

Find first duplicate in an array

Given an array a that contains only numbers in the range from 1 to a.length, find the first duplicate number for which the second occurrence has the minimal index. In other words, if there are more than 1 duplicated numbers, return the number for which the second occurrence has a smaller index than the second occurrence of the other number does. If there are no such elements, return -1.

My code: 

function firstDuplicate($a) {
    $unique = array_unique($a);

    foreach ($a as $key => $val) {
        if ($unique[$key] !== $val){
            return $key;
        }else{
            return -1;
        }
    }
}

The code above will be OK when the input is [2, 4, 3, 5, 1] but if the input is [2, 1, 3, 5, 3, 2] the output is wrong. The second duplicate occurrence has a smaller index. The expected output should be 3.

How can I fix my code to output the correct result?

Upvotes: 1

Views: 1687

Answers (5)

uchenna
uchenna

Reputation: 1

function firstDuplicate($a) {
    $indexNumber = -1;
    for($i = count($a); $i >= 1 ; --$i){
        for($k = 0; $k < $i; $k++){
          if(isset($a[$i]) && ($a[$i] === $a[$k]) ){
          $indexNumber = $a[$k]; 
        }   
        }
    }
    return $indexNumber;
}

Remove error from undefined index array.

Upvotes: 0

Ahmed Sayed Sk
Ahmed Sayed Sk

Reputation: 684

function firstDuplicate($a) {    
    foreach($a as $index => $value) {
        $detector[] = $value;
        $counter = 0;
        foreach($detector as $item) {
            if($item == $value) {
                $counter++;
                if($counter >= 2) {
                    return $value;
                    break;
                }
            }
        }
    }
    return -1;
}

It's easy to just get the first number that will be checked as duplicated, but unfortunately, this function exceeded 4 seconds with a large array of data, so please using it with a small scale of array data.

EDIT

I have new own code fixes execution time for large array data

function firstDuplicate($a) {
    $b = [];
    $counts = array_count_values($a);
    foreach($counts as $num => $duplication) {
        if($duplication > 1) {
            $b[] = $num;
        }
    }
    foreach($a as $value) {
        if(in_array($value, $b)) {
            $detector[] = $value;
            $counter = 0;
            foreach($detector as $item) {
                if($item == $value) {
                    $counter++;
                    if($counter >= 2) {
                        return $value;
                        break;
                    }
                }
            }
        }
    }
    return -1;
}

The new code target the current numbers having a reputation only by using array_count_values()

Upvotes: 0

Shyambeer Singh
Shyambeer Singh

Reputation: 328

Python3 Solution:

def firstDuplicate(a):
    mySet = set()
    for i in range(len(a)):
        if a[i] in mySet:
            return a[i]
        else:
            mySet.add(a[i])
    return -1

Upvotes: 0

Mingo
Mingo

Reputation: 36

$arr = array(2,1,3,5,3,2);
function firstDuplicate($a) {
    $res = -1;
    for ($i = count($a); $i >= 1; --$i) {
        for ($j = 0; $j < $i; ++$j) {
            if ($a[$j] === $a[$i]) {
                $res = $a[$j];
            }
        }
    }
    return $res;
}
var_dump(firstDuplicate($arr));

By traversing the array backwards, you will overwrite any previous duplicates with the new, lower-indexed one.

Note: this returns the value (not index), unless no duplicate is found. In that case, it returns -1.

Upvotes: 2

Danny
Danny

Reputation: 1185

// Return index of first found duplicate value in array
function firstDuplicate($a) {
    $c_array = array_count_values($a);
    foreach($c_array as $value=>$times)
    {
        if($times>1)
        {
            return array_search($value, $array);
        }
    }
    return -1;
}

array_count_values() will count the duplicate values in the array for you then you just iterate over that until you find the first result with more then 1 and search for the first key in the original array matching that value.

Upvotes: 1

Related Questions