How to find missing values in a sequence with PHP?

Question

Suppose you have an array "value => timestamp". The values are increasing with the time but they can be reset at any moment.

For example :

$array = array(
1 => 6000,
2 => 7000,
3 => 8000,
7 => 9000,
8 => 10000,
9 => 11000,
55 => 1000,
56 => 2000,
57 => 3000,
59 => 4000,
60 => 5000,
);

I would like to retrieve all the missing values from this array.

This example would return :

array(4,5,6,58)

I don't want all the values between 9 and 55 because 9 is newer than the other higher values.

In real condition the script will deal with thousands of values so it need to be efficient.

Thanks for your help!

UPDATE : The initial array can be ordered by timestamps if it is easier for the algorithm.

UPDATE 2 : In my example the values are UNIX timestamps so they would look more like this : 1285242603 but for readability reason I simplified it.

That's very easy to do... did you try? If so, where did you fail? — o0'.
– o0'., Commented Sep 23, 2010 at 11:28
You need iterate over it and apply your conditions as you get to each element. Seems a strange requirement. — Jake N
– Jake N, Commented Sep 23, 2010 at 11:34
If you can please tell more about why you will require this type of functionality, then it will help the others guide you in the right direction. — Knowledge Craving
– Knowledge Craving, Commented Sep 23, 2010 at 11:38

Gumbo · Accepted Answer · 2010-09-23 11:49:35Z

4

Here’s another solution:

$prev = null;
$missing = array();
foreach ($array as $curr => $value) {
    if (!is_null($prev)) {
        if ($curr > $prev+1 && $value > $array[$prev]) {
            $missing = array_merge($missing, range($prev+1, $curr-1));
        }
    }
    $prev = $curr;
}

answered Sep 23, 2010 at 11:49

Gumbo

657k112 gold badges792 silver badges852 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

codaddict · Accepted Answer · 2010-09-23 11:47:30Z

1

You can do the following:

Keep comparing adjacent array keys. If they are consecutive you do nothing.
If they are not consecutive then you check their values, if the value has dropped from a higher value to a lower value, it means there was a reset so you do nothing.
If the value has not dropped then it is a case of missing key(s). All the numbers between the two keys(extremes not included) are part of the result.

Translated in code:

$array = array( 1 => 6000, 2 => 7000, 3 => 8000, 7 => 9000, 8 => 10000, 
                9 => 11000,55 => 1000, 56 => 2000, 57 => 3000, 59 => 4000, 
                60 => 5000,);

$keys = array_keys($array);
for($i=0;$i<count($array)-1;$i++) {
  if($array[$keys[$i]] < $array[$keys[$i+1]] && ($keys[$i+1]-$keys[$i] != 1) ) {
           print(implode(' ',range($keys[$i]+1,$keys[$i+1]-1)));
           print "\n";
   }   
}

Working link

answered Sep 23, 2010 at 11:47

codaddict

457k83 gold badges501 silver badges537 bronze badges

1 Comment

benjisail Over a year ago

Thanks for ideone.com , I didn't know this website!

Mischa · Accepted Answer · 2010-09-23 12:11:42Z

1

This gives the desired result array(4,5,6,58):

$previous_value = NULL;
$temp_store = array();
$missing = array();
$keys = array_keys($array);

for($i = min($keys); $i <= max($keys); $i++)
{
    if(!array_key_exists($i, $array))
    {
        $temp_store[] = $i;
    }
    else
    {
        if($previous_value < $array[$i])
        {
            $missing = array_merge($missing, $temp_store);
        }
        $temp_store = array();
        $previous_value = $array[$i];
    }
}

var_dump($missing);

Or just use Gumbo's very smart solution ;-)

edited Sep 23, 2010 at 12:11

answered Sep 23, 2010 at 11:58

Mischa

43.4k9 gold badges101 silver badges111 bronze badges

1 Comment

benjisail Over a year ago

This solution seems slow if the gap between the min and the max is very large. This could happen in my case. But Thanks!!

Collectives™ on Stack Overflow

How to find missing values in a sequence with PHP?

3 Answers 3

Comments

1 Comment

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

1 Comment

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related