A Set is a collection data structure that stores unique elements with no duplicates allowed. Sets are typically implemented using hash tables, providing O(1) average time complexity for insertion, deletion, and membership testing. Unlike arrays, sets are unordered and focus on efficient lookups and set-theoretic operations.
Sets support mathematical operations like union (combining two sets), intersection (common elements), difference (elements in one but not the other), and symmetric difference (elements in either set but not both). These operations make sets powerful for tasks like removing duplicates, membership testing, and finding relationships between collections.
Add Elements: Enter values and add them to Set A or Set B. Duplicates are automatically rejected.
Remove Elements: Click the ✕ button on any element to remove it from its set.
Check Membership: Enter a value and check if it exists in Set A or Set B.
Union (A ∪ B): Combines all elements from both sets (no duplicates).
Intersection (A ∩ B): Returns elements that exist in both sets.
Difference (A - B): Returns elements in Set A but not in Set B.
Symmetric Difference (A Δ B): Returns elements in either set but not in both.
Subset (A ⊆ B): Checks if all elements of A exist in B.
Superset (A ⊇ B): Checks if A contains all elements of B.
Add: O(1) average - Hash table insertion with collision handling.
Remove: O(1) average - Direct deletion via hash lookup.
Contains: O(1) average - Hash table lookup, much faster than array search O(n).
Union: O(m + n) - Iterate through both sets and add all elements.
Intersection: O(min(m, n)) - Check each element of smaller set in larger set.
Difference: O(m) - Iterate through first set and check membership in second.
Subset/Superset: O(m) or O(n) - Check if all elements of one set exist in the other.
Duplicate Removal: Converting arrays to sets automatically removes duplicates from data.
Database Operations: SQL UNION, INTERSECT, and EXCEPT operations use set theory.
Access Control: User permissions represented as sets (read, write, execute).
Tag Systems: Blog posts, products with multiple tags stored as sets for efficient filtering.
Social Networks: Finding mutual friends (intersection of two friend sets).
Recommendation Systems: Finding users with similar interests by comparing item sets.
Spell Checking: Dictionary stored as set for O(1) word validation.
Graph Algorithms: Visited nodes tracking in DFS/BFS using sets.
vs Array: Sets guarantee uniqueness and have O(1) lookup vs O(n); arrays maintain order and allow duplicates.
vs Object/Map: Sets only store keys (no values); objects/maps store key-value pairs.
vs List: Sets have no index access, no order; lists allow duplicates and positional access.
Ordered Set: Some languages provide ordered sets (TreeSet) maintaining sorted order with O(log n) operations.
Best Use Case: When you need unique elements, fast membership testing, or mathematical set operations.
Add: Insert element if not already present - O(1) average.
Remove: Delete element if present - O(1) average.
Contains: Check if element exists - O(1) average.
Union: Combine all elements from two sets - O(m + n).
Intersection: Find elements common to both sets - O(min(m, n)).
Difference: Elements in first set but not second - O(m).
Remove Duplicates: Convert array to set and back; simple O(n) duplicate removal.
Two Sum: Use set to check if complement (target - current) exists in O(1).
Contains Duplicate: Add elements to set; if size differs from array length, duplicates exist.
Intersection of Arrays: Convert smaller to set, filter larger array by set membership.
Longest Consecutive Sequence: Use set for O(1) lookup; start sequences only from elements without predecessor.
Happy Number: Use set to detect cycles in digit square sum sequence.
Valid Sudoku: Use sets for rows, columns, and boxes to check uniqueness.
// Set implementation in C (using simple array-based approach)
#include <stdio.h>
#include <stdbool.h>
#define MAX_SIZE 100
typedef struct {
int elements[MAX_SIZE];
int size;
} Set;
void init(Set *s) { s->size = 0; }
bool contains(Set *s, int val) {
for (int i = 0; i < s->size; i++)
if (s->elements[i] == val) return true;
return false;
}
bool add(Set *s, int val) {
if (contains(s, val) || s->size >= MAX_SIZE) return false;
s->elements[s->size++] = val;
return true;
}
bool removeVal(Set *s, int val) {
for (int i = 0; i < s->size; i++) {
if (s->elements[i] == val) {
s->elements[i] = s->elements[--s->size];
return true;
}
}
return false;
}
Set unionSets(Set *a, Set *b) {
Set result; init(&result);
for (int i = 0; i < a->size; i++) add(&result, a->elements[i]);
for (int i = 0; i < b->size; i++) add(&result, b->elements[i]);
return result;
}
Set intersection(Set *a, Set *b) {
Set result; init(&result);
for (int i = 0; i < a->size; i++)
if (contains(b, a->elements[i])) add(&result, a->elements[i]);
return result;
}