$in for matching a set in MongoDB - Time & Space Complexity

Time Complexity: $in for matching a set

O(n)

Understanding Time Complexity

When using $in in MongoDB, we want to know how the time to find matching documents changes as the list of values grows.

We ask: How does the number of operations grow when the set inside $in gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following MongoDB query using $in.

db.collection.find({
  field: { $in: [value1, value2, value3, ..., valueN] }
})
    

This query finds documents where the field matches any value in the given list.

Identify Repeating Operations

Look at what repeats inside the query process.

• Primary operation: Checking if the document's field matches any value in the $in list.
• How many times: Once for each document scanned, checking against the list of values.

How Execution Grows With Input

As the list inside $in grows, the work to check each document grows too.

Input Size (n)	Approx. Operations
10	Checking up to 10 values per document
100	Checking up to 100 values per document
1000	Checking up to 1000 values per document

Pattern observation: The number of checks grows directly with the size of the $in list.

Final Time Complexity

Time Complexity: O(n)

This means the time to match grows linearly with the number of values inside the $in list.

Common Mistake

[X] Wrong: "Using $in with many values is always fast because MongoDB handles it internally."

[OK] Correct: MongoDB checks each value in the list, so a bigger list means more work and slower queries if no index supports it.

Interview Connect

Understanding how $in scales helps you explain query performance clearly and shows you know how database operations grow with input size.

Self-Check

"What if we replaced $in with multiple $or conditions? How would the time complexity change?"

Practice

1.

What does the $in operator do in MongoDB queries?

easy

A. Deletes documents matching a condition

B. Finds documents where a field is greater than a value

C. Updates documents by adding new fields

D. Finds documents where a field matches any value in a given list

Solution

1. Step 1: Understand the purpose of $in

   The $in operator is used to match documents where a field's value is equal to any value in a specified array.

2. Step 2: Compare with other options

   Options B, C, and D describe different MongoDB operations unrelated to $in.

3. Final Answer:

   Finds documents where a field matches any value in a given list -> Option D

4. Quick Check:

   $in matches any value in list [OK]

Hint: Remember: $in checks if field is in a list [OK]

Common Mistakes:

• Confusing $in with comparison operators like $gt
• Thinking $in updates or deletes documents
• Using $in without an array of values

2.

Which of the following is the correct syntax to find documents where the field color is either "red", "blue", or "green"?

{ color: { $in: ["red", "blue", "green"] } }

easy

A. { color: { $in: ["red", "blue", "green"] } }

B. { color: { $in: "red", "blue", "green" } }

C. { color: { $in: "red|blue|green" } }

D. { color: { $in: { "red", "blue", "green" } } }

Solution

1. Step 1: Check the correct use of $in syntax

   The $in operator requires an array of values inside square brackets []. { color: { $in: ["red", "blue", "green"] } } correctly uses an array with strings.

2. Step 2: Identify syntax errors in other options

   { color: { $in: "red", "blue", "green" } } misses brackets for the array. { color: { $in: "red|blue|green" } } uses a string with pipes instead of an array. { color: { $in: { "red", "blue", "green" } } } uses curly braces which is invalid for arrays.

3. Final Answer:

   { color: { $in: ["red", "blue", "green"] } } -> Option A

4. Quick Check:

   $in needs an array [OK]

Hint: Always use square brackets [] for $in values [OK]

Common Mistakes:

• Using strings instead of arrays for $in
• Using curly braces {} instead of square brackets []
• Separating values with commas but missing brackets

3.

Given the collection products with documents:

[{ "name": "Pen", "category": "stationery" }, { "name": "Apple", "category": "fruit" }, { "name": "Notebook", "category": "stationery" }, { "name": "Banana", "category": "fruit" }]

What will be the result of this query?

db.products.find({ category: { $in: ["fruit"] } })

medium

A. [{ "name": "Pen", "category": "stationery" }, { "name": "Notebook", "category": "stationery" }]

B. [{ "name": "Apple", "category": "fruit" }, { "name": "Banana", "category": "fruit" }]

C. []

D. All documents in the collection

Solution

1. Step 1: Understand the query filter

   The query filters documents where the category field is in the array ["fruit"]. This means only documents with category "fruit" will match.

2. Step 2: Identify matching documents

   Documents with "Apple" and "Banana" have category "fruit", so they are returned. Others are excluded.

3. Final Answer:

   [{ "name": "Apple", "category": "fruit" }, { "name": "Banana", "category": "fruit" }] -> Option B

4. Quick Check:

   Filter by category in ["fruit"] returns fruit items [OK]

Hint: Match only documents with field in the given list [OK]

Common Mistakes:

• Expecting documents with other categories to appear
• Confusing $in with $nin (not in)
• Thinking $in matches substrings instead of exact values

4.

What is wrong with this MongoDB query?

db.users.find({ age: { $in: 25, 30, 35 } })

medium

A. The query should use $nin instead of $in

B. The field name age is invalid

C. The $in operator requires an array of values, not separate arguments

D. The query is correct and will return matching documents

Solution

1. Step 1: Check the syntax of $in usage

   The $in operator expects a single array argument containing values to match. Here, values are passed as separate arguments, which is invalid syntax.

2. Step 2: Identify the correct syntax

   The correct syntax is { age: { $in: [25, 30, 35] } } with square brackets around the values.

3. Final Answer:

   The $in operator requires an array of values, not separate arguments -> Option C

4. Quick Check:

   $in needs an array [OK]

Hint: Always wrap $in values in square brackets [OK]

Common Mistakes:

• Passing multiple values without an array
• Confusing $in with other operators
• Assuming query is valid without brackets

5.

You have a collection orders with documents containing a field status. You want to find all orders where the status is either "pending", "shipped", or "delivered" but exclude those with status "cancelled" or "returned". Which query correctly uses $in and $nin to achieve this?

hard

A. { $or: [ { status: { $in: ["pending", "shipped", "delivered"] } }, { status: { $nin: ["cancelled", "returned"] } } ] }

B. { status: { $in: ["pending", "shipped", "delivered"] }, status: { $nin: ["cancelled", "returned"] } }

C. { status: { $in: ["pending", "shipped", "delivered"] }, $nin: ["cancelled", "returned"] }

D. { status: { $in: ["pending", "shipped", "delivered"], $nin: ["cancelled", "returned"] } }

Solution

1. Step 1: Understand the need to combine $in and $nin on the same field

   We want documents where status is in one list but not in another. MongoDB does not allow combining $in and $nin inside the same object for a field. Instead, both conditions must be combined using an implicit AND by specifying both in the query object.

2. Step 2: Analyze each option's structure

   { status: { $in: ["pending", "shipped", "delivered"] }, status: { $nin: ["cancelled", "returned"] } } uses the same field key twice with different operators, which is invalid JSON syntax. { $or: [ { status: { $in: ["pending", "shipped", "delivered"] } }, { status: { $nin: ["cancelled", "returned"] } } ] } uses $or, which applies OR logic, not the required AND. { status: { $in: ["pending", "shipped", "delivered"] }, $nin: ["cancelled", "returned"] } places $nin outside the field, which is invalid. { status: { $in: ["pending", "shipped", "delivered"], $nin: ["cancelled", "returned"] } } tries to combine $in and $nin inside the same object, which is invalid in MongoDB.

3. Step 3: Correct approach

   The correct way is to combine both conditions using $and or by specifying both operators inside an object using $and or by using the implicit AND by combining conditions in the query object like: { status: { $in: [...] }, status: { $nin: [...] } } is invalid JSON because keys repeat. So the correct query is:
   { status: { $in: [...] }, status: { $nin: [...] } } is invalid.
   Instead, use:
   { status: { $in: [...] }, status: { $nin: [...] } } is invalid.
   So the correct way is:
   { status: { $in: [...] }, $nin: [...] } is invalid.
   Therefore, the correct query is:
   { status: { $in: [...] }, $nin: [...] } is invalid.
   Hence, the only valid way is to use $and operator:
   { $and: [ { status: { $in: [...] } }, { status: { $nin: [...] } } ] }

4. Final Answer:

   { $and: [ { status: { $in: ["pending", "shipped", "delivered"] } }, { status: { $nin: ["cancelled", "returned"] } } ] } -> Option A (modified)

5. Quick Check:

   Use $and to combine $in and $nin conditions [OK]

Hint: Use $and to combine multiple conditions on the same field [OK]

Common Mistakes:

• Repeating the same field key multiple times in query
• Placing $nin outside the field object
• Using separate objects for the same field without $and