Problem

Given an unsorted array of integers, remove all duplicate elements so that each element appears only once, preserving the order of their first occurrence.

Examples

Example 1

1
2
3

Input:  [1, 5, 2, 6, 8, 9, 1, 1, 10, 3, 2, 4, 1, 3, 11, 3]
Output: [1, 5, 2, 6, 8, 9, 10, 3, 4, 11]
Explanation: All duplicates are removed, and the order of first appearance is preserved.

Constraints

  • 1 <= n <= 10^5 (where n is the length of the array)
  • Array elements are integers (may be negative or positive)

Solution

Method 1 – Brute Force (Nested Loops)

Intuition

Check every element against all previous elements to see if it has already appeared. If not, keep it; otherwise, skip it.

Approach

  1. Initialize an empty result array ans.
  2. For each element in the input array:
    • Check if it already exists in ans.
    • If not, append it to ans.
  3. Return ans.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
public:
    vector<int> removeDuplicates(vector<int>& arr) {
        vector<int> ans;
        for (int x : arr) {
            bool found = false;
            for (int y : ans) if (x == y) { found = true; break; }
            if (!found) ans.push_back(x);
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

func removeDuplicates(arr []int) []int {
    ans := []int{}
    for _, x := range arr {
        found := false
        for _, y := range ans {
            if x == y {
                found = true
                break
            }
        }
        if !found {
            ans = append(ans, x)
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

import java.util.*;
class Solution {
    public List<Integer> removeDuplicates(int[] arr) {
        List<Integer> ans = new ArrayList<>();
        for (int x : arr) {
            boolean found = false;
            for (int y : ans) if (x == y) { found = true; break; }
            if (!found) ans.add(x);
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8

from typing import List
class Solution:
    def removeDuplicates(self, arr: list[int]) -> list[int]:
        ans: list[int] = []
        for x in arr:
            if x not in ans:
                ans.append(x)
        return ans

Complexity

  • ⏰ Time complexity: O(n^2), because for each element, we may scan the result array so far.
  • 🧺 Space complexity: O(n), for the result array.

Method 2 – Hash Set (Preserve Order)

Intuition

Use a hash set to track seen elements for O(1) lookups, so we only keep the first occurrence of each element.

Approach

  1. Initialize an empty set seen and an empty result array ans.
  2. For each element in the input array:
    • If it is not in seen, add it to ans and mark it as seen.
  3. Return ans.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

#include <unordered_set>
class Solution {
public:
    vector<int> removeDuplicates(vector<int>& arr) {
        unordered_set<int> seen;
        vector<int> ans;
        for (int x : arr) {
            if (!seen.count(x)) {
                ans.push_back(x);
                seen.insert(x);
            }
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

func removeDuplicates(arr []int) []int {
    seen := make(map[int]bool)
    ans := []int{}
    for _, x := range arr {
        if !seen[x] {
            ans = append(ans, x)
            seen[x] = true
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

import java.util.*;
class Solution {
    public List<Integer> removeDuplicates(int[] arr) {
        Set<Integer> seen = new HashSet<>();
        List<Integer> ans = new ArrayList<>();
        for (int x : arr) {
            if (!seen.contains(x)) {
                ans.add(x);
                seen.add(x);
            }
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

from typing import List
class Solution:
    def removeDuplicates(self, arr: list[int]) -> list[int]:
        seen: set[int] = set()
        ans: list[int] = []
        for x in arr:
            if x not in seen:
                ans.append(x)
                seen.add(x)
        return ans

Complexity

  • ⏰ Time complexity: O(n), since each element is processed once and set lookups are O(1).
  • 🧺 Space complexity: O(n), for the set and result array.

Method 3 – Sort and Remove Duplicates

Intuition

Sorting brings duplicates together, so we can remove them in a single pass. This does not preserve the original order.

Approach

  1. Sort the array.
  2. Initialize an empty result array ans.
  3. For each element, if it is not the same as the previous, add it to ans.
  4. Return ans.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

#include <algorithm>
class Solution {
public:
    vector<int> removeDuplicates(vector<int>& arr) {
        sort(arr.begin(), arr.end());
        vector<int> ans;
        for (int i = 0; i < arr.size(); ++i) {
            if (i == 0 || arr[i] != arr[i-1]) ans.push_back(arr[i]);
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

import "sort"
func removeDuplicates(arr []int) []int {
    sort.Ints(arr)
    ans := []int{}
    for i, x := range arr {
        if i == 0 || x != arr[i-1] {
            ans = append(ans, x)
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

import java.util.*;
class Solution {
    public List<Integer> removeDuplicates(int[] arr) {
        Arrays.sort(arr);
        List<Integer> ans = new ArrayList<>();
        for (int i = 0; i < arr.length; ++i) {
            if (i == 0 || arr[i] != arr[i-1]) ans.add(arr[i]);
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8

class Solution:
    def removeDuplicates(self, arr: list[int]) -> list[int]:
        arr.sort()
        ans: list[int] = []
        for i, x in enumerate(arr):
            if i == 0 or x != arr[i-1]:
                ans.append(x)
        return ans

Complexity

  • ⏰ Time complexity: O(n log n), due to sorting.
  • 🧺 Space complexity: O(n), for the result array (or O(1) extra if allowed to modify in-place).