Jump to content

Find Duplicate of Lowest Comparing Index


waslsdnowlds

Recommended Posts

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

Link to comment
Share on other sites

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.

Link to comment
Share on other sites

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?

Link to comment
Share on other sites

Archived

This topic is now archived and is closed to further replies.

×
×
  • Create New...

Important Information

We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.