Array comparison and set operations in Ruby - Time & Space Complexity

Time Complexity: Array comparison and set operations

O(n + m)

Understanding Time Complexity

When we compare arrays or perform set operations, we want to know how the time needed grows as the arrays get bigger.

We ask: How does the work change when the input arrays grow in size?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

arr1 = [1, 2, 3, 4, 5]
arr2 = [4, 5, 6, 7, 8]

# Find common elements
common = arr1 & arr2

# Find elements in arr1 but not in arr2
diff = arr1 - arr2

# Check if arr1 includes all elements of arr2
includes_all = (arr2 - arr1).empty?
    

This code finds common elements, differences, and checks inclusion between two arrays.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Building a hash from one array and performing constant-time lookups for elements of the other.
• How many times: Hash construction takes O(m) time, then O(n) lookups, total O(n + m).

How Execution Grows With Input

As the arrays get bigger, the number of operations grows linearly because Ruby uses hash tables for efficient lookups.

Input Size (n)	Approx. Operations
10	About 20 operations
100	About 200 operations
1000	About 2000 operations

Pattern observation: The work grows linearly with the input size.

Final Time Complexity

Time Complexity: O(n + m)

This means the time needed grows proportionally to the sum of the sizes of the two arrays.

Common Mistake

[X] Wrong: "Array set operations like & and - take O(n * m) time with linear scans."

[OK] Correct: Ruby uses hash tables internally for O(1) average-case lookups after O(m) preprocessing, for total O(n + m).

Interview Connect

Understanding how array comparisons scale helps you explain your code choices clearly and shows you know how to handle bigger data efficiently.

Self-Check

What if we implemented these operations using nested loops instead? How would the time complexity change?

Practice

1.

Which operator in Ruby returns the common elements between two arrays?

[1, 2, 3] ? [2, 3, 4]

easy

A. & (intersection)

B. | (union)

C. - (difference)

D. == (equality)

Solution

1. Step 1: Understand the operators

   The & operator returns elements common to both arrays.

2. Step 2: Apply to example arrays

   For arrays [1, 2, 3] and [2, 3, 4], common elements are 2 and 3.

3. Final Answer:

   & (intersection) -> Option A

4. Quick Check:

   Common elements = & [OK]

Hint: Use & for common items between arrays [OK]

Common Mistakes:

• Confusing union (|) with intersection (&)
• Using - for common elements
• Thinking == compares elements regardless of order

2.

Which of the following is the correct syntax to find the difference between two arrays a and b in Ruby?

easy

A. a == b

B. a - b

C. a | b

D. a & b

Solution

1. Step 1: Recall difference operator

   The - operator returns elements in a not in b.

2. Step 2: Confirm syntax correctness

   Using a - b is the correct Ruby syntax for difference.

3. Final Answer:

   a - b -> Option B

4. Quick Check:

   Difference = - [OK]

Hint: Use a - b to get items in a but not in b [OK]

Common Mistakes:

• Using & instead of - for difference
• Using | which is union
• Using == which checks equality

3.

What is the output of the following Ruby code?

a = [1, 2, 3, 4]
b = [3, 4, 5, 6]
result = a | b
puts result.inspect

medium

A. [1, 2, 3, 4, 5, 6]

B. [3, 4]

C. [1, 2]

D. [1, 2, 3, 4]

Solution

1. Step 1: Understand the union operator

   The | operator combines all unique elements from both arrays.

2. Step 2: Apply union to arrays

   Arrays a and b combined uniquely are [1, 2, 3, 4, 5, 6].

3. Final Answer:

   [1, 2, 3, 4, 5, 6] -> Option A

4. Quick Check:

   Union = | [OK]

Hint: Use | to combine unique elements from both arrays [OK]

Common Mistakes:

• Confusing union with intersection
• Expecting duplicates in output
• Using - which removes elements

4.

Identify the error in the following Ruby code snippet:

a = [1, 2, 3]
b = [2, 3, 4]
result = a & b
puts result

What is the problem?

medium

A. Syntax error due to missing parentheses

B. Outputs all elements from both arrays

C. Runtime error because & is not defined for arrays

D. No error; code runs and outputs common elements

Solution

1. Step 1: Check syntax and operators

   The & operator is valid for arrays to find intersection.

2. Step 2: Verify output behavior

   The code outputs common elements [2, 3] without error.

3. Final Answer:

   No error; code runs and outputs common elements -> Option D

4. Quick Check:

   Intersection & works fine [OK]

Hint: & works for arrays to find common items without syntax errors [OK]

Common Mistakes:

• Thinking & causes syntax error
• Expecting union instead of intersection
• Confusing output with difference

5.

You have two arrays representing user IDs:

active_users = [101, 102, 103, 104, 105]
inactive_users = [103, 105, 107]

Which Ruby expression gives you the list of users who are active but not inactive?

hard

A. active_users | inactive_users

B. active_users & inactive_users

C. active_users - inactive_users

D. active_users == inactive_users

Solution

1. Step 1: Understand the problem

   We want users in active_users but not in inactive_users.

2. Step 2: Use difference operator

   The - operator returns elements in first array not in second.

3. Step 3: Apply to given arrays

   active_users - inactive_users = [101, 102, 104]

4. Final Answer:

   active_users - inactive_users -> Option C

5. Quick Check:

   Difference = - [OK]

Hint: Use - to exclude inactive from active users [OK]

Common Mistakes:

• Using & which gives only common users
• Using | which combines all users
• Using == which checks equality