Jump to content
#FlattenTheCurve ×
waslsdnowlds

Find Duplicate of Lowest Comparing Index

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

Edited by waslsdnowlds

Share this post


Link to post
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.

Share this post


Link to post
Share on other sites

perhaps

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

Share this post


Link to post
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?

Share this post


Link to post
Share on other sites
function firstDuplicate($a){

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

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

}

Share this post


Link to post
Share on other sites

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.

Share this post


Link to post
Share on other sites

Using that data you provided it took

 

0.000122 seconds

 

on a sluggish android tablet.

Share this post


Link to post
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Restore formatting

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.


×
×
  • 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.