4.49

Algorithm (order-preserving):
1. Create an empty set seen and an empty list unique.
2. For each element x in the input array:
  a. If x is not in seen:
    • Add x to seen.
    • Append x to unique.
3. Return unique.

Pseudocode

function uniqueElements(arr):
seen = ∅
out = []
for x in arr:
if x ∉ seen:
seen.add(x)
out.append(x)
return out

Reference Python implementation

def unique_elements(arr):
seen = set()
unique = []
for x in arr:
if x not in seen:
seen.add(x)
unique.append(x)
return unique

Complexity
Time: [math]O(n)[/math] where n is the array length (each element is processed once).
Space: [math]O(k)[/math] where k is the number of distinct elements.

Back to Chapter 4