Remove duplicates from array in linear time and without extra arrays

Question

We have an array and it is unsorted. We know the range is [0,n].

We want to remove duplicates but we cannot use extra arrays and it must run in linear time.

Any ideas? Just to clarify, this is not for homework!

I'm not entirely sure you can do this to be honest. I mean there is counting sort, but that requires additional space. — zellio
– zellio, Commented Mar 24, 2011 at 4:46
I'm with Mimisbrunnr -- I'm not sure this can be done. Googling suggests that using a hashmap (which probably isn't allowed, here) is the fastest, easiest way to do it; If there were a clever, linear-time algorithm that didn't require extra memory it would be easy to find. — Haldean Brown
– Haldean Brown, Commented Mar 24, 2011 at 4:53
Yes, it is an array of ints. You can reorder the array as long as you finish with O(n) running time. — Geoff C.
– Geoff C., Commented Mar 24, 2011 at 4:55

Jeff · Accepted Answer · 2011-03-24 05:31:31Z

13

If the integers are limited 0 to n, you can move through the array, placing numbers by their indices. Every time you replace a number, take the value that used to be there and move it to where it should be. For instance, let's say we have an array of size 8:

-----------------
|3|6|3|4|5|1|7|7|
-----------------
 S

Where S is our starting point, and we'll use C to keep track of our "current" index below. We start with index 0, and move 3 to the 3 index spot, where 4 is. Save 4 in a temp var.

-----------------
|X|6|3|3|5|1|7|7|   Saved 4 
-----------------  
 S     C

We then put 4 in the index 4, saving what used to be there, 5.

-----------------
|X|6|3|3|4|1|7|7|   Saved 5
-----------------
 S       C

Keep going

-----------------
|X|6|3|3|4|5|7|7|   Saved 1
-----------------
 S         C

-----------------
|X|1|3|3|4|5|7|7|   Saved 6
-----------------
 S C

-----------------
|X|1|3|3|4|5|6|7|   Saved 7    
-----------------
 S           C

When we try to replace 7, we see a conflict, so we simply don't place it. We then continue from the starting index S, increment it by 1:

-----------------
|X|1|3|3|4|5|6|7| 
-----------------  
   S

1 is fine here, 3 needs to move

-----------------
|X|1|X|3|4|5|6|7|
-----------------
     S

But 3 is a duplicate, so we throw it away and keep iterating through the rest of the array.

So basically, we move each entry at most 1 time, and iterate through the entire array. That's O(2n) = O(n)

edited Mar 24, 2011 at 5:31

answered Mar 24, 2011 at 5:23

Jeff

1,8671 gold badge15 silver badges18 bronze badges

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

7 Comments

zellio Over a year ago

This requires additional space in some cases. What if you have { 0, 1, 20 } as your array? then you need an array of size 20.

Alexei Levenkov Over a year ago

You probably also need to do compression of the array at the end by removing items that are marked with X above (i.e. -1 could be used to mark missing items). To remove items just go through all elements once and copy to last free space O(n) again.

Jeff Over a year ago

@Mimisbrunnr Integers are limited from 0..n, where n is the size of the array

Jeff Over a year ago

Or did I misread? I agree this won't work if n > the size of the array.

Joel Lee Over a year ago

@Mimisbrunnr - If I understand problem correctly, for an array of size 3, you can only have values in range [0,3].

|

Pradhan · Accepted Answer · 2011-10-02 06:16:54Z

3

    void printRepeating(int arr[], int size)
{
  int i;
  printf("The repeating elements are: \n");
  for(i = 0; i < size; i++)
  {
    if(arr[abs(arr[i])] >= 0)
      arr[abs(arr[i])] = -arr[abs(arr[i])];
    else
      printf(" %d ", abs(arr[i]));
  }
}

answered Oct 2, 2011 at 6:16

Pradhan

4115 silver badges17 bronze badges

Comments

Joel Lee · Accepted Answer · 2013-05-22 23:36:42Z

3

Assume int a[n] is an array of integers in the range [0,n-1]. Note that this differs slightly from the stated problem, but I make this assumption to make clear how the algorithm works. The algorithm can be patched up to work for integers in the range [0,n].

for (int i=0; i<n; i++)
{
    if (a[i] != i)
    {
         j = a[i];
         k = a[j];
         a[j] = j;  // Swap a[j] and a[i]
         a[i] = k;
     }
 }

 for (int i=0; i<n; i++)
 {
     if (a[i] == i)
     {
        printf("%d\n", i);
     }
 }

edited May 22, 2013 at 23:36

answered Mar 24, 2011 at 5:27

Joel Lee

3,9041 gold badge20 silver badges21 bronze badges

1 Comment

Eugene Gordin Over a year ago

in the second if it's an assignment operator instead of comparison

Alexei Levenkov · Accepted Answer · 2011-03-24 05:33:04Z

0

Can you sort? Sort with Radix Sort - http://en.wikipedia.org/wiki/Radix_sort with complexity O(arraySize) for given case and then remove duplicates from sorted array O(arraySize).

edited Mar 24, 2011 at 5:33

answered Mar 24, 2011 at 5:24

Alexei Levenkov

101k15 gold badges138 silver badges189 bronze badges

Comments

nmd · Accepted Answer · 2012-07-02 05:11:04Z

0

Walk through the array assign array[array[i]] = -array[array[i]]; if not negative; if its already negative then its duplicate, this will work since all values are within 0 and n.

answered Jul 2, 2012 at 5:11

nmd

8431 gold badge7 silver badges17 bronze badges

Comments

B Jacob · Accepted Answer · 2016-09-17 21:16:49Z

0

Extending @Joel Lee's code for completion.

#include <iostream>
void remove_duplicates(int *a, int size)
{
  int i, j, k;
  bool swap = true;

   while(swap){
    swap = false;
    for (i=0; i<size; i++){
        if(a[i] != i && a[i] != a[a[i]]){
            j = a[i];
            k = a[j];
            a[i] = k;
            a[j] = j;
            swap = true;      
        }

    }
    }
}

int main()
{
    int i;
    //int array[8] = {3,6,3,4,5,1,7,7};
    int array[8] = {7,4,6,3,5,4,6,2};

    remove_duplicates(array, sizeof(array)/sizeof(int));

    for (int i=0; i<8; i++)
        if(array[i] == i)
            std::cout << array[i] << " ";

    return 0;
}

answered Sep 17, 2016 at 21:16

B Jacob

4095 silver badges9 bronze badges

Comments

Patric Höhn · Accepted Answer · 2020-08-06 09:18:00Z

0

With ES6 I think this can be solved with only a few lines reducing the array into an object and then using object.keys to get array without duplicates. This probably takes more memory. I'm not sure.

I did it like this:

var obj = array.reduce(function (acc, elem) {
      acc[elem] = true;
      return acc;
    },{});
var uniqueArray = Object.keys(obj);

This has the added bonus (or disadvantage) of sorting the array. It works with strings too.

answered Aug 6, 2020 at 9:18

Patric Höhn

1

1 Comment

juanpa.arrivillaga Over a year ago

This definitely uses linear auxilliary space, which the questions asks not to

Vaibhav Tiwari · Accepted Answer · 2022-02-13 19:41:31Z

0

Use the array a a container with negative sign as an indicator, this will corrupt the input though.

answered Feb 13, 2022 at 19:41

Vaibhav Tiwari

1

1 Comment

Community Over a year ago

As it’s currently written, your answer is unclear. Please edit to add additional details that will help others understand how this addresses the question asked. You can find more information on how to write good answers in the help center.

Collectives™ on Stack Overflow

Remove duplicates from array in linear time and without extra arrays

8 Answers 8

7 Comments

Comments

1 Comment

Comments

Comments

Comments

1 Comment

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

8 Answers 8

7 Comments

Comments

1 Comment

Comments

Comments

Comments

1 Comment

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related