Remove Duplicates from an Unsorted Array (Hash Table)
Remove duplicates from an unsorted array in place, keeping the first occurrence of each value and the original order. Return the new length, or -1 if memory allocation fails.
Use a hash table so the whole operation runs in O(n) average time. Values can be any int, including negative numbers.
Example: {5, 3, 1, 3, 9, 5, 6} → length 5, array starts {5, 3, 1, 9, 6}.
Write your code on the right and press Run (or Ctrl + Enter). Hidden tests check your functions and print the result below the editor.
Allocate an open-addressing table with about twice as many slots as elements, each slot holding a value and a "used" flag. For each element, hash it, then probe linearly until you find either the same value (a duplicate: skip it) or an empty slot (new: insert it and keep the element).
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct {
int value;
unsigned char used;
} slot_t;
int remove_duplicates_hash(int *a, int n)
{
if (n <= 0) return 0;
size_t cap = 2 * (size_t)n + 1; /* load factor < 0.5 */
slot_t *tab = calloc(cap, sizeof *tab);
if (!tab) return -1;
int w = 0;
for (int r = 0; r < n; r++) {
size_t k = (unsigned int)a[r] % cap; /* negatives handled by the cast */
while (tab[k].used && tab[k].value != a[r])
k = (k + 1) % cap; /* linear probing */
if (!tab[k].used) { /* first time we see this value */
tab[k].used = 1;
tab[k].value = a[r];
a[w++] = a[r];
}
}
free(tab);
return w;
}
The sorted-array trick does not work here because duplicates can be anywhere. A hash table remembers every value seen so far, so each lookup is O(1) on average and the whole pass is O(n) average time, O(n) memory. Writing kept elements through w preserves the order of first occurrence.
Design choices worth explaining in the interview:
- Open addressing with linear probing: one
calloc, no per-node allocation, cache friendly. - Capacity
2n + 1: keeps the load factor below 50%, so probe sequences stay short and an empty slot always exists (the probe loop always terminates). (unsigned int)a[r] % cap:%on a negativeintgives a negative result in C, which would index outside the table. Casting to unsigned first maps every value to a valid slot.- The
usedflag: you cannot use 0 as "empty", because 0 is a valid value. - Check
callocand free the table on every path.
Walk-through: {5, 3, 1, 3, 9, 5, 6}, cap = 15
| r | value | slot | result |
|---|---|---|---|
| 0 | 5 | 5 empty | keep → 5 |
| 1 | 3 | 3 empty | keep → 5 3 |
| 2 | 1 | 1 empty | keep → 5 3 1 |
| 3 | 3 | 3 holds 3 | duplicate, skip |
| 4 | 9 | 9 empty | keep → 5 3 1 9 |
| 5 | 5 | 5 holds 5 | duplicate, skip |
| 6 | 6 | 6 empty | keep → 5 3 1 9 6 |
Trade-offs: if you may reorder, sorting then using the sorted-array method is O(n log n) with O(1) extra memory, which is often preferred on a microcontroller with no heap. If the value range is small and known (e.g. 8-bit sensor readings), a 256-bit bitmap replaces the hash table entirely.
Show the hidden tests
/* ---- tests ---- */
static int fails;
#define CHECK(c) do { if (!(c)) { printf("FAIL line %d: %s\n", __LINE__, #c); fails++; } } while (0)
int main(void)
{
int a[] = { 5, 3, 1, 3, 9, 5, 6 };
const int ea[] = { 5, 3, 1, 9, 6 };
CHECK(remove_duplicates_hash(a, 7) == 5 && memcmp(a, ea, sizeof ea) == 0);
int b[] = { -1, 7, -1, -8, 7, 0, -8 };
const int eb[] = { -1, 7, -8, 0 };
CHECK(remove_duplicates_hash(b, 7) == 4 && memcmp(b, eb, sizeof eb) == 0);
int c[] = { 4, 4, 4 };
CHECK(remove_duplicates_hash(c, 3) == 1 && c[0] == 4);
int d[] = { -2147483647 - 1, 2147483647, -2147483647 - 1, 0 };
CHECK(remove_duplicates_hash(d, 4) == 3);
CHECK(remove_duplicates_hash(NULL, 0) == 0);
int big[1000];
for (int i = 0; i < 1000; i++) big[i] = (i * 7919) % 100; /* only 100 distinct values */
CHECK(remove_duplicates_hash(big, 1000) == 100 && big[0] == 0 && big[1] == 19);
puts(fails ? "Some tests failed" : "All tests passed");
return fails != 0;
}