Find/detect for first match in Ruby - Time & Space Complexity

Time Complexity: Find/detect for first match

O(n)

Understanding Time Complexity

When we look for the first item that matches a condition, we want to know how long it takes as the list grows.

We ask: How does the time to find the first match change when the list gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

numbers = [1, 3, 5, 8, 10]
result = numbers.find { |num| num.even? }
puts result

This code looks through the list to find the first even number and stops once it finds it.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Checking each number one by one to see if it is even.
• How many times: Up to the first even number found, or the whole list if none found.

How Execution Grows With Input

As the list gets bigger, the time depends on where the first match is.

Input Size (n)	Approx. Operations
10	Checks 1 to 10 items depending on first match
100	Checks 1 to 100 items depending on first match
1000	Checks 1 to 1000 items depending on first match

Pattern observation: The time grows with the position of the first match, up to the full list size.

Final Time Complexity

Time Complexity: O(n)

This means the time to find the first match grows linearly with the list size in the worst case.

Common Mistake

[X] Wrong: "Finding the first match always takes the same time no matter the list size."

[OK] Correct: If the match is near the start, it's fast, but if it's near the end or missing, it takes longer as the list grows.

Interview Connect

Understanding how searching stops early helps you explain efficient code and shows you know how loops behave with different inputs.

Self-Check

"What if we changed find to select to get all matches? How would the time complexity change?"

Practice

1.

What does the Ruby method find (also known as detect) do when called on an array?

easy

A. It removes the first element that matches the condition in the block.

B. It returns all elements that match the condition in the block.

C. It returns the first element that matches the condition in the block.

D. It sorts the array based on the block's condition.

Solution

1. Step 1: Understand the purpose of find

   The find method searches through the array elements one by one.

2. Step 2: Identify what find returns

   It returns the first element for which the block condition is true, then stops searching.

3. Final Answer:

   It returns the first element that matches the condition in the block. -> Option C

4. Quick Check:

   find = first matching element [OK]

Hint: Remember: find returns only the first match, not all matches [OK]

Common Mistakes:

• Thinking find returns all matches
• Confusing find with methods that modify the array
• Assuming find sorts the array

2.

Which of the following is the correct syntax to find the first even number in an array nums using find?

nums = [1, 3, 4, 6]

easy

A. nums.find { |n| n.even? }

B. nums.find(n.even?)

C. nums.find => n.even?

D. nums.find |n| n.even?

Solution

1. Step 1: Recall the block syntax for find

   The block must be passed with curly braces or do-end and use a block variable with pipes.

2. Step 2: Check each option's syntax

   nums.find { |n| n.even? } uses correct block syntax: { |n| n.even? }. Others have syntax errors.

3. Final Answer:

   nums.find { |n| n.even? } -> Option A

4. Quick Check:

   Correct block syntax = nums.find { |n| n.even? } [OK]

Hint: Use curly braces and pipes for blocks with find [OK]

Common Mistakes:

• Missing pipes around block variable
• Passing condition without a block
• Using wrong arrow or syntax for block

3.

What is the output of the following Ruby code?

words = ["apple", "banana", "cherry", "date"]
result = words.find { |w| w.length > 5 }
puts result

medium

A. "cherry"

B. nil

C. "apple"

D. "banana"

Solution

1. Step 1: Check each word's length

   "apple" (5), "banana" (6), "cherry" (6), "date" (4).

2. Step 2: Find first word with length > 5

   "banana" is the first word longer than 5 characters.

3. Final Answer:

   "banana" -> Option D

4. Quick Check:

   First word with length > 5 = "banana" [OK]

Hint: Check elements in order; find stops at first match [OK]

Common Mistakes:

• Choosing the last matching word instead of first
• Confusing length condition
• Assuming find returns all matches

4.

Identify the error in this Ruby code that tries to find the first negative number:

numbers = [3, 5, -2, 7]
result = numbers.find do |n|
  n < 0
end
puts result

medium

A. There is no error; the code works correctly.

B. The variable n is not defined in the block.

C. The block syntax is incorrect; should use curly braces.

D. The method find does not accept a block.

Solution

1. Step 1: Check block syntax

   The do...end block with variable n is valid syntax for find.

2. Step 2: Confirm method usage

   find accepts a block and returns the first element matching n < 0.

3. Final Answer:

   There is no error; the code works correctly. -> Option A

4. Quick Check:

   Valid block syntax and method usage = There is no error; the code works correctly. [OK]

Hint: Remember: do-end blocks are valid for find [OK]

Common Mistakes:

• Thinking only curly braces work for blocks
• Assuming variable must be declared outside block
• Believing find can't take blocks

5.

You have an array of hashes representing people:

people = [
  {name: "Alice", age: 18},
  {name: "Bob", age: 17},
  {name: "Carol", age: 22}
]

Which code finds the first person who is an adult (age 18 or older) and returns their name?

hard

A. people.detect { |p| p[:age] > 18 }[:name]

B. people.find { |p| p[:age] >= 18 }[:name]

C. people.find { |p| p[:age] > 18 }[:name]

D. people.detect { |p| p[:age] >= 18 }[:age]

Solution

1. Step 1: Understand the condition for adult

   Adult means age 18 or older, so condition is p[:age] >= 18.

2. Step 2: Find first matching person and get name

   Use find or detect with condition, then access [:name].

3. Step 3: Check options carefully

   people.find { |p| p[:age] >= 18 }[:name] uses correct condition and returns name. people.detect { |p| p[:age] >= 18 }[:age] returns age, not name. Options A and C use > 18, excluding age 18.

4. Final Answer:

   people.find { |p| p[:age] >= 18 }[:name] -> Option B

5. Quick Check:

   Correct condition and return name = people.find { |p| p[:age] >= 18 }[:name] [OK]

Hint: Use >= 18 to include age 18, then get [:name] [OK]

Common Mistakes:

• Using > 18 excludes age 18
• Returning age instead of name
• Confusing find and detect (both work but check return)