Skip to content

Unique Elements

Find elements that are unique to each of two arrays using Python sets.

Problem Description

Given two arrays, find elements that are unique to each array (elements that appear in one array but not in the other).

Solution Using Sets

def unique_elements(list1, list2):
    set1 = set(list1)
    set2 = set(list2)
    unique_to_1 = sorted(list(set1 - set2))
    unique_to_2 = sorted(list(set2 - set1))
    return (unique_to_1, unique_to_2)

How It Works

  1. Convert to Sets: Convert both lists to sets for efficient operations
  2. Set Difference:
  3. set1 - set2 gives elements unique to list1
  4. set2 - set1 gives elements unique to list2
  5. Sort Results: Convert back to sorted lists for consistent output

Time Complexity Analysis

This solution is considerably more efficient than the naive approach, operating at a time complexity of O(n), or O(max(len(list1), len(list2))) to be more precise.

Space Complexity

  • Space Complexity: O(n) - We need to store the sets and result lists

Example Usage

# Example 1
list1 = [1, 2, 3, 4]
list2 = [3, 4, 5, 6]
unique_1, unique_2 = unique_elements(list1, list2)
print(unique_1)  # [1, 2]
print(unique_2)  # [5, 6]

# Example 2
list1 = [1, 2, 3]
list2 = [1, 2, 3]
unique_1, unique_2 = unique_elements(list1, list2)
print(unique_1)  # []
print(unique_2)  # []

# Example 3
list1 = [1, 2, 3, 4, 5]
list2 = [6, 7, 8, 9, 10]
unique_1, unique_2 = unique_elements(list1, list2)
print(unique_1)  # [1, 2, 3, 4, 5]
print(unique_2)  # [6, 7, 8, 9, 10]

Alternative Approaches

Using List Comprehension (Less Efficient)

def unique_elements_list(list1, list2):
    unique_to_1 = sorted([x for x in list1 if x not in list2])
    unique_to_2 = sorted([x for x in list2 if x not in list1])
    return (unique_to_1, unique_to_2)

Time Complexity: O(nĀ²) - not in operation is O(n) for each element Space Complexity: O(n)

Using Dictionary for Counting

from collections import Counter

def unique_elements_counter(list1, list2):
    counter1 = Counter(list1)
    counter2 = Counter(list2)

    unique_to_1 = sorted([num for num in counter1 if num not in counter2])
    unique_to_2 = sorted([num for num in counter2 if num not in counter1])

    return (unique_to_1, unique_to_2)

Time Complexity: O(n log n) - Due to sorting Space Complexity: O(n)

Key Insights

  1. Set Difference: Using set difference operations (-) for efficient uniqueness checking
  2. Symmetric Operation: The operation is symmetric - we check both directions
  3. Sorting: Results are sorted for consistent output
  4. Efficient Lookups: Set operations provide O(1) average time complexity

Edge Cases

  • Empty Arrays: Returns empty lists for both
  • Identical Arrays: Returns empty lists for both
  • Completely Different: Returns all elements from each array
  • One Empty: Returns all elements from the non-empty array