Find duplicates in an array, without using any extra space

algorithm

Given an array of n integer elements how will you find whether there are duplicates in the array in O(n) time without using any extra space.

With extra space it means extra space of order O(n).

Does the Xor operator help in any way.

If there is no additional information, this question seems to be unsolveable, as this is the Element Distinctness Problem, which is unsolveable with the restrictions you provided, in the required time.

you can allow:

(1) more memory and use a hashtable / hashset and meet the O(n) time criteria. [iterate the array, check if an element is in the hash table, if it is you have dupes, otherwise - insert the element into the table and continue].

(2) more time, sort the array [O(nlogn)] and meet the sub-linear space criteria. [After sorting, iterate over the array, and for each a[i] , a[i+1] , check if they are identical. If you did not find an identical pair, you have no dupes]

EDIT: The proof for this claim is a bit lengthy, and needs mathematical notation that are not supported here (sidenote: we really need tex support), but the idea is if we model our problem as an Algebraic Computation Tree (which is a fair assumption when no hashing is allowed, and constant space at out disposal), then, Ben Or proved in his article Lower Bounds For Algebraic Computation Trees (1983) (published in prestiged ACM), that element distinctness is Omega(nlogn) problem under this model. Lubiw showed that the same conclusion also applies when limiting ourselves to integers in 1991: A Lower Bound for the Integer Element Distinctness Problem, but these articles conclude that under the algebraic tree computation model - Integer Distinctness Problem is Omega(nlogn) Problem.

In-place Radix Sort followed by Linear Scan

In place radix sort algorithm

Depending on what you actually consider the time complexity of a Radix sort to be, this solution is O(N) time, although my personal opinion is not so. I think that if you don't make the linear-time assumption on the integer sort, then the problem is unsolvable.

Due to the fact that the sort is in-place, there's only O(1) additional storage required.

Code is all C++11

Step 1: Radix Sort in place

template<typename T, typename std::enable_if<std::is_integral<T>::value>::type* = nullptr>
void RecurseOnRadixSort(std::vector<T>& myArray, T mask, int zerosEnd, int onesBegin)
{
    if (zerosEnd+1 >= onesBegin-1 || mask == 0) 
        return;

    int zerosEnd2 = zerosEnd;
    int onesBegin2 = onesBegin;
    while(zerosEnd2+1 <= onesBegin2-1)
    {
        // swap ones to the right
        if ((myArray[zerosEnd2+1] & mask) != 0)
        {
            std::swap(myArray[zerosEnd2+1], myArray[onesBegin2-1]);
            --onesBegin2;
        }
        else
            ++zerosEnd2;
    }

    mask >>= 1;

    //recurse on lhs
    RecurseOnRadixSort(myArray, mask, zerosEnd, zerosEnd2+1);

    //recurse on rhs
    RecurseOnRadixSort(myArray, mask, onesBegin2-1, onesBegin);
}

template <typename T, typename std::enable_if<std::is_integral<T>::value>::type* = nullptr>
void InPlaceRadixSort(std::vector<T>& myArray)
{
    int zerosEnd = -1;
    int onesBegin = static_cast<int>(myArray.size());
    T mask = static_cast<T>(1) << sizeof(T)*8-1;
    while(zerosEnd+1 <= onesBegin-1)
    {
        if ( (myArray[zerosEnd+1] & mask) != 0)
        {
            std::swap(myArray[zerosEnd+1], myArray[onesBegin-1]);
            --onesBegin;
        }
        else
            ++zerosEnd;
    }

    mask = static_cast<T>(1) << sizeof(T)*8-2; // need to reassign in case of signed datatype
    //recurse on lhs
    RecurseOnRadixSort(myArray, mask, -1, zerosEnd+1);
    //recurse on rhs
    RecurseOnRadixSort(myArray, mask, onesBegin-1, static_cast<int>(myArray.size()));

    // swap negatives to the front
    auto iterSmallest = std::min_element(myArray.begin(), myArray.end());
    if (*iterSmallest < 0)
    {
        std::reverse(myArray.begin(), myArray.end());
        iterSmallest = std::min_element(myArray.begin(), myArray.end());
        std::reverse(myArray.begin(), iterSmallest+1);
        std::reverse(iterSmallest+1, myArray.end());
    }
}

Step 2: Linear scan for duplicate elements

for (size_t i=0, j=1; j<myArray.size(); ++i,++j)
{
    if (myArray[i] == myArray[j])
    {
        std::cout << "Found duplicate element " << myArray[i];
    }
}

Complete Code

#include <iostream>
#include <string>
#include <vector>
#include <iostream>
#include <vector>
#include <algorithm>
#include <ctime>
#include <type_traits>
using namespace std;
#define N 10

template <typename T>
void PrintArray(const std::vector<T>& myArray)
{
    for (auto&& element : myArray)
    {
        std::cout << element << std::endl;
    }
}

template<typename T, typename std::enable_if<std::is_integral<T>::value>::type* = nullptr>
void RecurseOnRadixSort(std::vector<T>& myArray, T mask, int zerosEnd, int onesBegin)
{
    if (zerosEnd+1 >= onesBegin-1 || mask == 0) 
        return;

    int zerosEnd2 = zerosEnd;
    int onesBegin2 = onesBegin;
    while(zerosEnd2+1 <= onesBegin2-1)
    {
        // swap ones to the right
        if ((myArray[zerosEnd2+1] & mask) != 0)
        {
            std::swap(myArray[zerosEnd2+1], myArray[onesBegin2-1]);
            --onesBegin2;
        }
        else
            ++zerosEnd2;
    }

    mask >>= 1;

    //recurse on lhs
    RecurseOnRadixSort(myArray, mask, zerosEnd, zerosEnd2+1);

    //recurse on rhs
    RecurseOnRadixSort(myArray, mask, onesBegin2-1, onesBegin);
}

template <typename T, typename std::enable_if<std::is_integral<T>::value>::type* = nullptr>
void InPlaceRadixSort(std::vector<T>& myArray)
{
    int zerosEnd = -1;
    int onesBegin = static_cast<int>(myArray.size());
    T mask = static_cast<T>(1) << sizeof(T)*8-1;
    while(zerosEnd+1 <= onesBegin-1)
    {
        if ( (myArray[zerosEnd+1] & mask) != 0)
        {
            std::swap(myArray[zerosEnd+1], myArray[onesBegin-1]);
            --onesBegin;
        }
        else
            ++zerosEnd;
    }

    mask = static_cast<T>(1) << sizeof(T)*8-2; // need to reassign in case of signed datatype
    //recurse on lhs
    RecurseOnRadixSort(myArray, mask, -1, zerosEnd+1);
    //recurse on rhs
    RecurseOnRadixSort(myArray, mask, onesBegin-1, static_cast<int>(myArray.size()));

    // swap negatives to the front
    auto iterSmallest = std::min_element(myArray.begin(), myArray.end());
    if (*iterSmallest < 0)
    {
        std::reverse(myArray.begin(), myArray.end());
        iterSmallest = std::min_element(myArray.begin(), myArray.end());
        std::reverse(myArray.begin(), iterSmallest+1);
        std::reverse(iterSmallest+1, myArray.end());
    }
}

int main() {
    srand(time(NULL));
    std::vector<int> myArray(N);
    for (size_t i=0;i<myArray.size();++i)
    {
        myArray[i] = rand() % 100 * (rand() % 2 == 1?-1:1);
    }

    std::cout << "Vector before radix sort: " << std::endl;
    PrintArray(myArray);
    InPlaceRadixSort(myArray);
    std::cout << "Vector after radix sort: " << std::endl;
    PrintArray(myArray);

    for (size_t i=0, j=1; j<myArray.size(); ++i,++j)
    {
        if (myArray[i] == myArray[j])
        {
            std::cout << "Found duplicate element " << myArray[i];
        }
    }
    return 0;
}

Live Demo

Here's an interesting solution to this problem with a single constraints that the elements should range between 0 to n-2(inclusive) where n is the number of elements.

This works in O(n) time with an O(1) space complexity.

Here is solution with O(n) time usage and O(1) space usage!

Traverse the array. Do following for every index i of A[].
{
    check for sign of A[abs(A[i])] ;
    if positive then        make it negative by   A[abs(A[i])]=-A[abs(A[i])];
    else  // i.e., A[abs(A[i])] is negative
    this   element (ith element of list) is a repetition
}

Credits: Method 5 Geek for Geeks