Reduce/inject for accumulation in Ruby - Time & Space Complexity

Time Complexity: Reduce/inject for accumulation

O(n)

Understanding Time Complexity

We want to understand how the time to add up values using reduce or inject changes as the list gets bigger.

How does the number of steps grow when we accumulate many items?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

numbers = [1, 2, 3, 4, 5]
sum = numbers.reduce(0) do |acc, num|
  acc + num
end
puts sum

This code adds all numbers in the array using reduce, starting from zero.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Adding each number to the accumulator inside the reduce loop.
• How many times: Once for each item in the array.

How Execution Grows With Input

Each new number means one more addition step.

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

Pattern observation: The steps grow directly with the number of items.

Final Time Complexity

Time Complexity: O(n)

This means the time to add all numbers grows in a straight line as the list gets bigger.

Common Mistake

[X] Wrong: "Reduce runs in constant time no matter how many items there are."

[OK] Correct: Reduce must visit each item once, so time grows with the list size.

Interview Connect

Understanding how reduce works helps you explain how simple loops add up values efficiently in real tasks.

Self-Check

"What if we used reduce to multiply all numbers instead of adding? How would the time complexity change?"

Practice

1. What does the Ruby method inject do when used on an array?

easy

A. It combines all elements into a single value using a block.

B. It sorts the array in ascending order.

C. It removes duplicate elements from the array.

D. It returns the first element of the array.

Solution

1. Step 1: Understand the purpose of inject

   The inject method takes all elements of an array and combines them into one value using the block provided.

2. Step 2: Compare with other options

   Sorting, removing duplicates, or returning the first element are different methods like sort, uniq, or first.

3. Final Answer:

   It combines all elements into a single value using a block. -> Option A

4. Quick Check:

   inject combines elements = C [OK]

Hint: Remember: inject reduces many to one value [OK]

Common Mistakes:

• Confusing inject with sorting methods
• Thinking inject returns an array
• Assuming inject removes duplicates

2. Which of the following is the correct syntax to sum all elements in an array arr using inject?

easy

A. arr.inject { |sum, n| sum / n }

B. arr.inject(0) { |sum, n| sum + n }

C. arr.inject(1) { |sum, n| sum * n }

D. arr.inject { |sum, n| sum - n }

Solution

1. Step 1: Identify the correct initial value and operation

   To sum elements, start with 0 and add each element: inject(0) { |sum, n| sum + n }.

2. Step 2: Check other options

   arr.inject { |sum, n| sum - n } subtracts, C multiplies starting at 1, A divides. Only D sums correctly.

3. Final Answer:

   arr.inject(0) { |sum, n| sum + n } -> Option B

4. Quick Check:

   Sum with inject = D [OK]

Hint: Sum needs 0 start and + inside block [OK]

Common Mistakes:

• Starting sum with 1 instead of 0
• Using wrong operation like subtraction
• Omitting initial value causing errors

3. What is the output of this Ruby code?

numbers = [2, 3, 4]
result = numbers.inject(1) { |product, n| product * n }
puts result

medium

A. Error

B. 9

C. 10

D. 24

Solution

1. Step 1: Understand the initial value and operation

   The initial value is 1, and each element multiplies the accumulator: 1*2=2, 2*3=6, 6*4=24.

2. Step 2: Calculate the final product

   The final result after all multiplications is 24.

3. Final Answer:

   24 -> Option D

4. Quick Check:

   2*3*4 = 24 [OK]

Hint: Multiply with inject starts at 1 [OK]

Common Mistakes:

• Adding instead of multiplying
• Starting with 0 causing zero result
• Confusing output with sum

4. Identify the error in this code snippet:

arr = [1, 2, 3]
sum = arr.inject { |total, n| total + n }
puts sum

medium

A. No error; code works fine.

B. Missing initial value causes incorrect sum.

C. Block parameters are reversed.

D. inject cannot be used without a symbol.

Solution

1. Step 1: Check if initial value is required

   When no initial value is given, inject uses the first element as the start and iterates from the second element.

2. Step 2: Verify the sum calculation

   It correctly sums 1 + 2 + 3 = 6 without error.

3. Final Answer:

   No error; code works fine. -> Option A

4. Quick Check:

   inject without initial value sums correctly = A [OK]

Hint: inject uses first element as start if no initial value [OK]

Common Mistakes:

• Assuming initial value is always required
• Thinking block parameters order is wrong
• Believing inject needs symbol argument

5. Given an array of hashes representing products with keys :name and :price, how can you use inject to find the total price of all products?

products = [
  { name: "Book", price: 12 },
  { name: "Pen", price: 3 },
  { name: "Notebook", price: 7 }
]

hard

A. products.inject { |total, product| total + product.name }

B. products.inject(1) { |total, product| total * product[:price] }

C. products.inject(0) { |total, product| total + product[:price] }

D. products.inject(0) { |total, product| total + product.price }

Solution

1. Step 1: Access the price key correctly

   Each product is a hash, so access price with product[:price].

2. Step 2: Sum prices starting at 0

   Start with 0 and add each price to get total price.

3. Step 3: Check other options

   products.inject { |total, product| total + product.name } uses dot notation which is invalid for hashes, C multiplies prices, D uses dot notation again.

4. Final Answer:

   products.inject(0) { |total, product| total + product[:price] } -> Option C

5. Quick Check:

   Sum prices with inject and hash keys = B [OK]

Hint: Use hash keys with [:key] inside inject block [OK]

Common Mistakes:

• Using dot notation for hash keys
• Multiplying prices instead of summing
• Starting sum at 1 instead of 0