Find Duplicate of Lowest Comparing Index

[waslsdnowlds]

This code is functioning but the execution time limit exceeds what is requested. I've downed it a little bit but it seems it needs to be even faster. Any ideas?

 

function firstDuplicate($array){
		
	$stored_value = -1;
	$stored_index = count($array);

    for($current_index = 0; $current_index < count($array); $current_index++){
		
	$current_value = $array[$current_index];
        $comparing_index = $current_index+1;
        
        for($comparing_index; $comparing_index < count($array); $comparing_index++){
           
            $comparing_value = $array[$comparing_index];
            
            if ($current_value === $comparing_value && $comparing_index < $stored_index){
				
				$stored_value = $current_value;
				$stored_index = $comparing_index;
					
            }

      }
        
 }
	
	if ($stored_index != count($array)){
	
		return $stored_value;
	
	} else {
		
		return -1;
		
	}
	
}

$a = array(8, 4, 6, 2, 6, 4, 7, 9, 5, ;

firstDuplicate($a);

Results

6

Edited October 4, 2017 by waslsdnowlds

[archive]

I'm not really sure what you are trying to achieve since you haven't explained what you want in any great detail such as how big the array will actually be and if the elements will be purely numeric. I can however point you to a few things which may improve performance.

 

Why create a variable which is hardly used?

 

$stored_index = count($array);

for($current_index = 0; $current_index < count($array); $current_index++)

 

Do you really need to test type as well as value? and have a look at your second test and decide if you really need it?

 

if ($current_value === $comparing_value && $comparing_index < $stored_index)

 

And have a look at break

 

This is by no means an exhaustive analysis, but should shave some time off execution.

[Barand]

perhaps

function firstDuplicate($arr)
{
    foreach ($arr as $k=>$n) {
        $subarr = array_slice($arr,0,$k);
        if (in_array($n, $subarr)) return $n;
    }
}

[waslsdnowlds]

Nice, Barand. That works. One of the requirements is to have return a -1 if nothing is found. I did just that.
 

function firstDuplicate($arr){
    foreach ($arr as $k=>$n) {
        $subarr = array_slice($arr,0,$k);
        if (in_array($n, $subarr)) return $n;
    }
    return -1;
}

The issue is I'm still getting the following issue: Program exceeded the execution time limit. Make sure that it completes execution in a few seconds for any possible input. Any ideas on that?

[waslsdnowlds]

function firstDuplicate($a){

    $duplicates = array_diff_assoc($a, array_unique($a));

    return count($duplicates) > 0 ? array_shift($duplicates) : -1;

}

[requinix]

Please no more free code, folks. This is a programming challenge.

 

Barand's code will run quickly. What's the entire thing you have? It should be running in a fraction of a second so I don't know what's taking it so long.

[Barand]

Using that data you provided it took

 

0.000122 seconds

 

on a sluggish android tablet.