Removing Duplicates in C++

Why set / unordered_set Works — and When to Think Beyond STL

While solving a problem to remove duplicates from an array in C++, my first instinct was to use STL containers like set and unordered_set.
This works well — but only under certain conditions.

This article explains:

why this approach is correct and its limitations and what other ways of thinking exist.

🔹 My Initial Approach

Given an array:

vector<int> v = {1, 2, 2, 3, 4, 4, 5};

Using set

set<int> s;
for (int x : v) {
    s.insert(x);
}

Using unordered_set

unordered_set<int> os;
for (int x : v) {
    os.insert(x);
}

Both approaches successfully remove duplicates.

⏱ Time & Space Complexity (Corrected)

set

Time: O(n log n)
Space: O(n)

Internally uses a self-balancing BST
Output is sorted

unordered_set

Time: O(n) average, O(n) worst case
Space: O(n)

Uses hashing
Output order is not guaranteed

⚠ Important Limitation

This approach does NOT preserve original order.

Input:

[5, 1, 2, 1, 5, 3]

Output:

set → 1 2 3 5

unordered_set → random order

So this solution is:

✅ Correct when order doesn’t matter

❌ Incorrect when order must be preserved

🧠 Is There Another Way to Think?

Yes — and this is the key learning.

Different thinking based on constraints:
1️⃣** Extra Space Allowed → STL Containers**

✔ Simple
✔ Clean
✔ Interview-acceptable

2️⃣ No Extra Space (In-place)

Works when array is sorted

Uses index-based logic

Common in product-company interviews

3️⃣ Frequency-Based Thinking

When counts matter

Uses maps or counting arrays

4️⃣ Pure Logical / Brute Force

No STL, no extra space

Slower but tests reasoning

🎯 The Real Insight

My thinking wasn’t wrong.

I recognized:

Duplicate → Uniqueness → Use a Set

That’s good problem-solving.

But interviews push further to test:

space optimization

control over indices

constraint-based decision making

✅ Final Takeaway

There is no single “best” solution.

The right approach depends on:

Is extra space allowed?

Does order matter?

Is the array sorted?

What are the constraints?

Learning when to use STL — and when not to — is what turns a beginner into an interview-ready developer.