Find all duplicates and missing values in a sorted array

Question

Suppose you have a sorted range (x to y) of values in an array.

x = 3;
y = 11;

array == 3, 4, 5, 6, 7, 8, 9, 10, 11

But it is possible that some values are duplicated and some are missing, so you might have:

array == 4, 5, 5, 5, 7, 8, 9, 10, 10

What's the best way in your language to find all duplicates and missing values so you get:

resultMissingValuesArray == 3, 6, 11
resultDuplicatesArray == 5, 5, 10

Here's some C++ code to get you started:

#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

const int kLastNumber = 50000; // last number expected in array
const int kFirstNumber = 3; // first number expected in array

int main()
{
    vector<int> myVector;

    // fill up vector, skip values at the beginning and end to check edge cases
    for(int x = kFirstNumber + 5; x < kLastNumber - 5; x++)
    { 
     if(x % 12 != 0 &&  x % 13 != 0 && x % 17 != 0)
      myVector.push_back(x); // skip some values

     else if(x % 9 == 0)
     {
      myVector.push_back(x); // add duplicates
      myVector.push_back(x); 
     }

     else if(x % 16 == 0)
     {
      myVector.push_back(x); // add multiple duplicates
      myVector.push_back(x); 
      myVector.push_back(x); 
      myVector.push_back(x); 
     }
    }

    // put the results in here
    vector<int> missingValues;
    vector<int> duplicates;

    //  YOUR CODE GOES HERE         

    // validate missingValues for false positives
    for(int x = 0; x < (int) missingValues.size(); ++x)
    {
     if(binary_search(myVector.begin(), myVector.end(), missingValues.at(x)))
      cout << "Oh noes! You missed an unmissed value. Something went horribly, horribly wrong.";
    }

    // validate duplicates (I think... errr)
    vector<int>::iterator vecItr = myVector.begin();
    vector<int>::iterator dupItr = duplicates.begin();

    while(dupItr < duplicates.end())
    {
     vecItr = adjacent_find(vecItr, myVector.end());  

     if(*vecItr != *dupItr)
      cout << "Oh noes! Something went horribly, horribly wrong.";

        // oh god
     while(++dupItr != duplicates.end() && *(--dupItr) == *(++dupItr) && *vecItr == *(++vecItr));   

     ++vecItr;
    }

    return 0;
}

I didn't test the validation parts much, so there may be be something wrong with them (especially with the duplicates one).

I will post my own solution as an answer.

Answer 1

if(myVector.front() > kFirstNumber)
 for(int x = kFirstNumber; x < myVector.at(0); ++x)
  if(x >= kFirstNumber && x <= kLastNumber)
   missingValues.push_back(x);

for(int x = 1; x < (int) myVector.size(); ++x)
{
 if(myVector.at(x) == myVector.at(x - 1))
  if(x >= kFirstNumber && x <= kLastNumber)
   duplicates.push_back(myVector.at(x));

 if(myVector.at(x) != myVector.at(x - 1) + 1)
  for(int y = myVector.at(x - 1) + 1; y <= myVector[x] - 1; y++)
   if(y >= kFirstNumber && y <= kLastNumber)
    missingValues.push_back(y);
} 

if(myVector.back() < kLastNumber)
 for(int x = myVector.back() + 1; x <= kLastNumber; ++x)
  if(x >= kFirstNumber && x <= kLastNumber)
   missingValues.push_back(x);

(My solution was pretty ugly, so I replaced it with a C++ implementation of Pax's algorithm.)

Answer 2

Since you've marked it language-agnostic, here's the algorithm I'd use.

# Get numbers and sort them in ascending order.

input x,y;
input number[1..n];
sort number[1..n];

# Set dups and missing to empty sets.

dups = [];
missing = [];

# Get edge cases.

if number[1] > x:
    foreach i x .. number[1] - 1:
        missing.add(i)
if number[n] < y:
    foreach i number[n] + 1 .. y:
        missing.add(i)

# Process all numbers starting at second one.

foreach i 2 .. n:
    # If number same as last and not already in dups set, add it.

    if number[i] == number[i-1] and not dups.contains(number[i]):
        if number[i] >= x and number[i] <= y:
            dups.add(number[i])

    # If number not last number plus one, add all between the two
    #   to missing set.

    if number[i] != number[i-1] + 1:
        foreach j number[i-1] + 1 .. number[i] - 1:
            if j >= x and j <= y:
                missing.add(j)

Answer 3

my favourite - Python, very simple:

x = 3
y = 11
array = [ 3, 4, 5, 6, 7, 8, 9, 10, 11 ]
test  = [ 4, 5, 5, 5, 7, 8, 9, 10, 10 ]

resultMissingValuesArray = set(range(x,y+1)).difference(test)        
resultDuplicatesArray = reduce(lambda i,j: i+j, [[n]*(test.count(n)-1) for n in set(test) if test.count(n)>1], [])

duplicates can be more easily found by this line:

resultDuplicatesArray = [n for n in set(test) if test.count(n)>1]
# [5, 10] - just numbers, that have duplicates
# you can use test.count(5) for number of duplicates

Answer 4

Ruby:

x = 3
y = 11
array  = [ 4, 5, 5, 5, 7, 8, 9, 10, 10 ]

resultMissingValuesArray = (x..y).to_a - array
resultDuplicatesArray = array.delete_if { |e| array.index(e) == array.rindex(e) }.uniq

Answer 5

in python

consecutive=zip(l[0:-1],l[1:])
duplicate=[ a for (a,b) in consecutive if a==b]
missing=reduce(lambda u,v:u+v, [range(a+1,b) for (a,b) in consecutive])

Answer 6

I think that you can do this fast in C++ by setting up a second array that acts as a check to see which elements have been found and then incrementing its elements by one each time an element is found. So:

int array = [3,4,5,6,7,8,9,10,11];
unsigned array_size = 9;
int test = [4,5,5,5,7,8,9,10,10];

// Find the maximum element in array
// This might not be necessary if it's given somewhere
unsigned max = 0;
unsigned min = -1;
for(unsigned i = 0; i < array_size; i++){
    if(array[i] > max)    max = array[i];
    if(array[i] < min)    min = array[i];
}

// Go make a counts vector to store how many examples of each value there are
vector< unsigned > counts(max+1, 0);
for(unsigned i = 0; i < array_size; i++)
    counts[test[i]]++;

// Gather the unique elements, duplicates and missing elements
vector< unsigned > unique;
vector< unsigned > duplicates;
vector< unsigned > missing;
for(unsigned i = min; i < max + 1; i++){
    switch(counts[i]){
        case 0 : missing.push_back(i);    break;
        case 1 : unique.push_back(i);     break;
        default: duplicates.push_back(i);
    }
}

This only works if you have numbers bigger than 0 in your array, which is often the case. The bonus is that it scales linearly in the number of elements, which is useful :-)