Arrays in documents in MongoDB - Time & Space Complexity

Time Complexity: Arrays in documents

O(n)

Understanding Time Complexity

When working with arrays inside MongoDB documents, it's important to understand how the time to process these arrays grows as they get bigger.

We want to know how the number of operations changes when we query or update arrays inside documents.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

// Find documents where the array contains a specific value
db.collection.find({ tags: "mongodb" })

// Update: add a new tag to the array
 db.collection.updateOne(
   { _id: 1 },
   { $push: { tags: "database" } }
 )
    

This code searches for documents with a specific value inside an array and adds a new value to an array in a document.

Identify Repeating Operations

Look for repeated steps that take time.

• Primary operation: Scanning the array inside each document to check for the value or to add a new element.
• How many times: For each document, the array elements are checked one by one until the value is found or the end is reached.

How Execution Grows With Input

As the array inside documents grows, the time to check or update grows too.

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

Pattern observation: The time grows roughly in direct proportion to the array size.

Final Time Complexity

Time Complexity: O(n)

This means the time to find or update an element grows linearly with the number of items in the array.

Common Mistake

[X] Wrong: "Searching inside an array in a document is always fast and constant time."

[OK] Correct: MongoDB must check each element until it finds the match, so time grows with array size, not constant.

Interview Connect

Understanding how array size affects query and update time helps you explain real-world database behavior clearly and confidently.

Self-Check

"What if the array is indexed with a multikey index? How would the time complexity change for searching inside the array?"

Practice

1. What is the main purpose of using arrays in MongoDB documents?

easy

A. To index documents automatically

B. To create multiple documents at once

C. To enforce data types on fields

D. To store multiple values in a single field

Solution

1. Step 1: Understand what arrays do in MongoDB

   Arrays allow storing multiple values inside one document field, like a list.

2. Step 2: Compare options with array purpose

   Only To store multiple values in a single field correctly describes storing multiple values in one field.

3. Final Answer:

   To store multiple values in a single field -> Option D

4. Quick Check:

   Arrays = multiple values in one field [OK]

Hint: Arrays hold many values in one field [OK]

Common Mistakes:

• Thinking arrays create multiple documents
• Confusing arrays with indexing
• Believing arrays enforce data types

2. Which of the following is the correct way to define an array field named tags in a MongoDB document?

easy

A. { tags: "mongodb, database" }

B. { tags: { "mongodb", "database" } }

C. { tags: ["mongodb", "database"] }

D. { tags: ("mongodb", "database") }

Solution

1. Step 1: Recall MongoDB array syntax

   Arrays in MongoDB are defined using square brackets [] with comma-separated values.

2. Step 2: Check each option's syntax

   { tags: ["mongodb", "database"] } uses square brackets correctly. Options A, B, and D use incorrect syntax for arrays.

3. Final Answer:

   { tags: ["mongodb", "database"] } -> Option C

4. Quick Check:

   Arrays use [] brackets [OK]

Hint: Arrays use square brackets [] in MongoDB [OK]

Common Mistakes:

• Using quotes instead of brackets for arrays
• Using curly braces {} which define objects
• Using parentheses () which are invalid for arrays

3. Given the document { name: "Alice", scores: [85, 90, 78] }, what will the query db.collection.find({ scores: 90 }) return?

medium

A. Documents where the scores array contains 90

B. Documents where scores equals exactly 90

C. Documents where scores is greater than 90

D. No documents because 90 is inside an array

Solution

1. Step 1: Understand MongoDB array matching

   Querying with { scores: 90 } matches documents where the array contains the value 90.

2. Step 2: Analyze the given document and query

   The scores array includes 90, so the document matches and will be returned.

3. Final Answer:

   Documents where the scores array contains 90 -> Option A

4. Quick Check:

   Query matches array elements directly [OK]

Hint: Query value matches any array element [OK]

Common Mistakes:

• Thinking query matches whole array only
• Assuming query checks for greater than
• Believing arrays block direct value matching

4. What is wrong with this MongoDB update query to add a new tag to the tags array?

db.collection.updateOne({ _id: 1 }, { $push: { tags: "new" } })

medium

A. The query is missing the filter document

B. The $push operator is used correctly; no error

C. The $push operator requires the value to be an array

D. The update document should use $addToSet instead of $push

Solution

1. Step 1: Understand $push operator usage

   $push adds a single value to an array field; it accepts a single value, not necessarily an array.

2. Step 2: Check the query structure

   The filter {_id: 1} is present, and $push is used correctly to add "new" to tags array.

3. Final Answer:

   The $push operator is used correctly; no error -> Option B

4. Quick Check:

   $push adds single values to arrays [OK]

Hint: $push accepts single values, no array needed [OK]

Common Mistakes:

• Thinking $push needs an array value
• Confusing $push with $addToSet for uniqueness
• Missing the filter document in update

5. You have documents with a field comments which is an array of objects like { user: "Bob", text: "Nice!" }. How do you write a query to find documents where comments contains an object with user equal to "Bob" and text containing the word "Nice"?

hard

A. { comments: { $elemMatch: { user: "Bob", text: /Nice/ } } }

B. { "comments.user": "Bob", "comments.text": /Nice/ }

C. { comments: { $all: [ { user: "Bob" }, { text: /Nice/ } ] } }

D. { comments: { $in: [ { user: "Bob", text: /Nice/ } ] } }

Solution

1. Step 1: Understand matching objects inside arrays

   $elemMatch matches array elements that satisfy all conditions inside it.

2. Step 2: Analyze each option for correct syntax

   { comments: { $elemMatch: { user: "Bob", text: /Nice/ } } } uses $elemMatch with both conditions together, correctly matching one object with user "Bob" and text matching /Nice/.

3. Final Answer:

   { comments: { $elemMatch: { user: "Bob", text: /Nice/ } } } -> Option A

4. Quick Check:

   $elemMatch matches array elements with multiple conditions [OK]

Hint: Use $elemMatch for multiple conditions on one array element [OK]

Common Mistakes:

• Using separate field queries (dot notation) which match conditions across different elements
• Using $all which matches separate elements, not one
• Using $in which matches exact elements, not partial fields