$min and $max accumulators in MongoDB - Time & Space Complexity

Time Complexity: $min and $max accumulators

O(n)

Understanding Time Complexity

When using $min and $max accumulators in MongoDB aggregation, it's important to know how the time to find minimum or maximum values grows as data grows.

We want to understand how the work changes when the number of documents increases.

Scenario Under Consideration

Analyze the time complexity of the following aggregation pipeline using $min and $max.

    db.sales.aggregate([
      {
        $group: {
          _id: "$store",
          minSale: { $min: "$amount" },
          maxSale: { $max: "$amount" }
        }
      }
    ])
    

This groups sales by store and finds the smallest and largest sale amount per store.

Identify Repeating Operations

Look for repeated work done by the query.

• Primary operation: Scanning each document once to compare its amount value.
• How many times: Once per document in the collection.

How Execution Grows With Input

As the number of documents grows, the number of comparisons grows roughly the same.

Input Size (n)	Approx. Operations
10	10 comparisons
100	100 comparisons
1000	1000 comparisons

Pattern observation: The work grows directly with the number of documents.

Final Time Complexity

Time Complexity: O(n)

This means the time to find minimum and maximum values grows linearly with the number of documents.

Common Mistake

[X] Wrong: "Using $min and $max is instant no matter how many documents there are."

[OK] Correct: MongoDB must check each document's value to find the min or max, so more documents mean more work.

Interview Connect

Understanding how accumulators like $min and $max scale helps you explain query performance clearly and shows you grasp how databases process data.

Self-Check

"What if we added an index on the amount field? How would that affect the time complexity of finding $min and $max?"

Practice

1. What do the $min and $max accumulators do in a MongoDB aggregation pipeline?

easy

A. $min and $max sort documents in ascending and descending order respectively.

B. $min and $max both find the average value in a group.

C. $min finds the first document and $max finds the last document in a group.

D. $min finds the smallest value and $max finds the largest value in a group.

Solution

1. Step 1: Understand the purpose of $min and $max

   $min returns the smallest value from the grouped documents, while $max returns the largest value.

2. Step 2: Compare with other options

   The other options describe different operations like average, first/last document, or sorting, which are not what $min and $max do.

3. Final Answer:

   $min finds the smallest value and $max finds the largest value in a group. -> Option D

4. Quick Check:

   $min = smallest, $max = largest [OK]

Hint: Remember: min = smallest, max = largest value [OK]

Common Mistakes:

• Confusing $min and $max with average functions
• Thinking they return documents instead of values
• Mixing accumulators with sorting operators

2. Which of the following is the correct syntax to use $max in a $group stage to find the highest score from a field named score?

easy

A. { $group: { _id: null, maxScore: { $max: "$score" } } }

B. { $group: { _id: null, maxScore: { max: "$score" } } }

C. { $group: { _id: null, maxScore: { $max: score } } }

D. { $group: { _id: null, maxScore: { $max: "score" } } }

Solution

1. Step 1: Check the correct use of $max accumulator

   The correct syntax requires $max as the operator and the field name as a string with a $ prefix inside quotes: "$score".

2. Step 2: Identify syntax errors in other options

   { $group: { _id: null, maxScore: { max: "$score" } } } misses the $ before max, { $group: { _id: null, maxScore: { $max: score } } } lacks quotes around field name, and { $group: { _id: null, maxScore: { $max: "score" } } } uses quotes without $ prefix, all invalid.

3. Final Answer:

   { $group: { _id: null, maxScore: { $max: "$score" } } } -> Option A

4. Quick Check:

   Use $max: "$field" syntax [OK]

Hint: Always prefix field names with $ and use quotes inside accumulators [OK]

Common Mistakes:

• Omitting $ before accumulator name
• Not quoting the field name with $
• Using field name without $ or quotes

3. Given the collection documents:

{ "name": "Alice", "score": 85 }, { "name": "Bob", "score": 92 }, { "name": "Charlie", "score": 78 }

What will be the output of this aggregation?

[{ $group: { _id: null, minScore: { $min: "$score" }, maxScore: { $max: "$score" } } }]

medium

A. { "_id": null, "minScore": 85, "maxScore": 85 }

B. { "_id": null, "minScore": 78, "maxScore": 92 }

C. { "_id": null, "minScore": 78, "maxScore": 78 }

D. { "_id": null, "minScore": 92, "maxScore": 85 }

Solution

1. Step 1: Identify minimum and maximum scores from documents

   The scores are 85, 92, and 78. The smallest is 78 and the largest is 92.

2. Step 2: Understand the aggregation output

   The $group stage groups all documents (_id: null) and calculates minScore as 78 and maxScore as 92.

3. Final Answer:

   { "_id": null, "minScore": 78, "maxScore": 92 } -> Option B

4. Quick Check:

   Min = 78, Max = 92 [OK]

Hint: Scan values, pick smallest for $min and largest for $max [OK]

Common Mistakes:

• Mixing up min and max values
• Assuming $min or $max returns documents instead of values
• Forgetting to use $ before field names

4. Consider this aggregation pipeline:

[{ $group: { _id: "$category", minPrice: { $min: price }, maxPrice: { $max: "$price" } } }]

What is the error in this pipeline?

medium

A. Field name 'price' in $min is missing quotes and $ prefix.

B. Using $max and $min together is not allowed.

C. The _id field cannot be a field name.

D. The pipeline is correct and has no errors.

Solution

1. Step 1: Check syntax of $min and $max usage

   The $min accumulator uses price without quotes and $ prefix, which is incorrect. It should be "$price".

2. Step 2: Verify other parts of the pipeline

   $max is correctly used with "$price". Grouping by "$category" is valid. Using both accumulators together is allowed.

3. Final Answer:

   Field name 'price' in $min is missing quotes and $ prefix. -> Option A

4. Quick Check:

   Field names need "$" prefix inside accumulators [OK]

Hint: Always quote and prefix field names with $ inside accumulators [OK]

Common Mistakes:

• Omitting $ before field names inside accumulators
• Thinking $min and $max cannot be used together
• Misunderstanding _id field usage in $group

5. You have a collection of sales documents with fields region and amount. You want to find the smallest and largest sale amounts per region, but only for regions where the smallest sale is above 100. Which aggregation pipeline correctly achieves this?

hard

A. [{ $group: { _id: "$region", minSale: { $min: "$amount" }, maxSale: { $max: "$amount" }, filter: { $gt: ["$minSale", 100] } } }]

B. [{ $match: { amount: { $gt: 100 } } }, { $group: { _id: "$region", minSale: { $min: "$amount" }, maxSale: { $max: "$amount" } } }]

C. [{ $group: { _id: "$region", minSale: { $min: "$amount" }, maxSale: { $max: "$amount" } } }, { $match: { minSale: { $gt: 100 } } }]

D. [{ $group: { _id: "$region", minSale: { $min: "$amount" }, maxSale: { $max: "$amount" } } }, { $match: { maxSale: { $gt: 100 } } }]

Solution

1. Step 1: Group by region and calculate min and max sales

   The $group stage groups documents by region and calculates minSale and maxSale using $min and $max on amount.

2. Step 2: Filter groups where minSale is greater than 100

   The $match stage after grouping filters groups where minSale is greater than 100, exactly as required.

3. Final Answer:

   [{ $group: { _id: "$region", minSale: { $min: "$amount" }, maxSale: { $max: "$amount" } } }, { $match: { minSale: { $gt: 100 } } }] -> Option C

4. Quick Check:

   Group first, then filter on aggregated minSale [OK]

Hint: Filter after grouping to use aggregated fields in conditions [OK]

Common Mistakes:

• Filtering before grouping, which filters documents not groups
• Trying to filter inside $group stage incorrectly
• Filtering on maxSale instead of minSale