$addToSet accumulator for unique arrays in MongoDB - Time & Space Complexity

Time Complexity: $addToSet accumulator for unique arrays

O(n)

Understanding Time Complexity

When using the $addToSet accumulator in MongoDB, it is important to understand how the time it takes grows as the input data grows.

We want to know how the operation of adding unique items to an array scales with more data.

Scenario Under Consideration

Analyze the time complexity of the following MongoDB aggregation snippet using $addToSet.

db.collection.aggregate([
  { $group: {
      _id: "$category",
      uniqueItems: { $addToSet: "$item" }
  }}
])

This groups documents by category and collects unique items into an array for each group.

Identify Repeating Operations

Look at what repeats as data grows:

• Primary operation: Checking if an item is already in the unique array before adding.
• How many times: For each document in a group, this check happens once.

How Execution Grows With Input

As the number of documents in a group grows, the number of checks to keep items unique grows too.

Input Size (n)	Approx. Operations
10	About 10 checks
100	About 100 checks
1000	About 1000 checks

Pattern observation: The number of operations grows roughly in direct proportion to the number of documents.

Final Time Complexity

Time Complexity: O(n)

This means the time to build the unique array grows linearly with the number of documents processed.

Common Mistake

[X] Wrong: "$addToSet adds items instantly without checking duplicates, so time stays constant."

[OK] Correct: The operation must check if each item is already in the set to keep it unique, so time grows as more items are processed.

Interview Connect

Understanding how MongoDB handles uniqueness with $addToSet helps you explain data aggregation efficiency clearly and confidently.

Self-Check

"What if we replaced $addToSet with $push and then removed duplicates later? How would the time complexity change?"

Practice

1. What does the $addToSet accumulator do in a MongoDB aggregation pipeline?

easy

A. Counts the total number of documents in a group

B. Adds all values including duplicates into an array

C. Sorts the array elements in ascending order

D. Collects unique values into an array, avoiding duplicates

Solution

1. Step 1: Understand $addToSet purpose

   $addToSet collects values but only keeps unique ones, no duplicates.

2. Step 2: Compare with other accumulators

   Unlike $push which adds all values, $addToSet ensures uniqueness.

3. Final Answer:

   Collects unique values into an array, avoiding duplicates -> Option D

4. Quick Check:

   $addToSet = unique array [OK]

Hint: Remember: $addToSet means add unique only [OK]

Common Mistakes:

• Confusing $addToSet with $push
• Thinking it sorts the array
• Assuming it counts documents

2. Which of the following is the correct syntax to use $addToSet in a MongoDB aggregation $group stage?

easy

A. { $group: { _id: "$category", uniqueItems: { $addToSet: "$item" } } }

B. { $group: { _id: "$category", uniqueItems: { $push: "$item" } } }

C. { $group: { _id: "$category", uniqueItems: { $addToSet: ["$item"] } } }

D. { $group: { _id: "$category", uniqueItems: { $addToSet: { $item } } } }

Solution

1. Step 1: Identify correct $addToSet usage

   The correct syntax uses $addToSet with a field path as a string, like "$item".

2. Step 2: Check other options for errors

   { $group: { _id: "$category", uniqueItems: { $push: "$item" } } } uses $push, not $addToSet. { $group: { _id: "$category", uniqueItems: { $addToSet: ["$item"] } } } wrongly wraps field in array. { $group: { _id: "$category", uniqueItems: { $addToSet: { $item } } } } uses braces incorrectly.

3. Final Answer:

   { $group: { _id: "$category", uniqueItems: { $addToSet: "$item" } } } -> Option A

4. Quick Check:

   Correct syntax = { $group: { _id: "$category", uniqueItems: { $addToSet: "$item" } } } [OK]

Hint: Use field path as string inside $addToSet [OK]

Common Mistakes:

• Wrapping field in array inside $addToSet
• Using $push instead of $addToSet
• Using braces {} incorrectly around field

3. Given the collection documents:

{ "category": "fruit", "item": "apple" }

{ "category": "fruit", "item": "banana" }

{ "category": "fruit", "item": "apple" }

What will be the result of this aggregation?

[{ $group: { _id: "$category", uniqueItems: { $addToSet: "$item" } } }]

medium

A. { "_id": "fruit", "uniqueItems": ["apple", "banana"] }

B. { "_id": "fruit", "uniqueItems": ["apple", "apple", "banana"] }

C. { "_id": "fruit", "uniqueItems": ["banana"] }

D. { "_id": "fruit", "uniqueItems": [] }

Solution

1. Step 1: Group by category and collect unique items

   All documents have category "fruit". $addToSet collects unique "item" values.

2. Step 2: Identify unique items

   Items are "apple", "banana", and another "apple" (duplicate). Unique set is ["apple", "banana"].

3. Final Answer:

   { "_id": "fruit", "uniqueItems": ["apple", "banana"] } -> Option A

4. Quick Check:

   Unique items = ["apple", "banana"] [OK]

Hint: Duplicates removed, only unique values remain [OK]

Common Mistakes:

• Expecting duplicates in result array
• Confusing $addToSet with $push
• Ignoring grouping key

4. You wrote this aggregation but it throws an error:

[{ $group: { _id: "$category", uniqueItems: { $addToSet: item } } }]

What is the error and how to fix it?

medium

A. Wrong accumulator; use $push instead of $addToSet

B. Missing quotes around field path; fix by using "$item"

C. Missing $unwind stage before $group

D. Cannot use $addToSet inside $group

Solution

1. Step 1: Identify syntax error in field reference

   Field paths must be strings with "$" prefix inside accumulators. Here, item is missing quotes and $.

2. Step 2: Correct the syntax

   Change item to "$item" to fix the error.

3. Final Answer:

   Missing quotes around field path; fix by using "$item" -> Option B

4. Quick Check:

   Field path needs "$" and quotes [OK]

Hint: Always quote field paths with $ inside accumulators [OK]

Common Mistakes:

• Forgetting $ before field name
• Not quoting field path as string
• Assuming $unwind is always required

5. You have documents with a field tags as arrays, some with duplicates:

{ "_id": 1, "tags": ["red", "blue", "red"] }

{ "_id": 2, "tags": ["blue", "green"] }

Which aggregation pipeline will produce a single array of all unique tags across documents?

hard

A. [{ $project: { uniqueTags: { $addToSet: "$tags" } } }]

B. [{ $group: { _id: null, allTags: { $addToSet: "$tags" } } }]

C. [{ $unwind: "$tags" }, { $group: { _id: null, allTags: { $addToSet: "$tags" } } }]

D. [{ $unwind: "$tags" }, { $group: { _id: "$tags", count: { $sum: 1 } } }]

Solution

1. Step 1: Use $unwind to flatten tags arrays

   $unwind breaks each array element into separate documents, allowing unique collection.

2. Step 2: Group all tags into a unique set

   Grouping by null collects all tags into one array with $addToSet ensuring uniqueness.

3. Final Answer:

   [{ $unwind: "$tags" }, { $group: { _id: null, allTags: { $addToSet: "$tags" } } }] -> Option C

4. Quick Check:

   Unwind then addToSet = unique combined array [OK]

Hint: Unwind arrays before addToSet to get unique elements [OK]

Common Mistakes:

• Trying to addToSet whole arrays without unwind
• Using $project instead of $group for aggregation
• Grouping by tags instead of null for combined result