np.intersect1d() for intersection in NumPy - Time & Space Complexity

Time Complexity: np.intersect1d() for intersection

O(n log n)

Understanding Time Complexity

We want to understand how the time to find common elements between two arrays grows as the arrays get bigger.

How does the work increase when the input arrays grow in size?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

import numpy as np

arr1 = np.array([1, 2, 3, 4, 5])
arr2 = np.array([3, 4, 5, 6, 7])

common = np.intersect1d(arr1, arr2)
print(common)

This code finds the common elements between two arrays using np.intersect1d.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Sorting both input arrays and then scanning them to find common elements.
• How many times: Each array is processed once during sorting (which involves multiple comparisons), then a single pass through both arrays to find intersections.

How Execution Grows With Input

As the size of the input arrays grows, the sorting step takes more time, and the scanning step grows linearly.

Input Size (n)	Approx. Operations
10	About 10 * log(10) operations for sorting, plus 10 operations for scanning
100	About 100 * log(100) operations for sorting, plus 100 operations for scanning
1000	About 1000 * log(1000) operations for sorting, plus 1000 operations for scanning

Pattern observation: The sorting dominates and grows a bit faster than the input size, while scanning grows directly with input size.

Final Time Complexity

Time Complexity: O(n log n)

This means the time to find the intersection grows a bit faster than the size of the input arrays because of sorting.

Common Mistake

[X] Wrong: "Finding common elements is just a simple loop, so it must be O(n)."

[OK] Correct: The function sorts the arrays first, which takes more time than just looping, so the overall time is more than just O(n).

Interview Connect

Understanding how sorting affects performance helps you explain and improve data operations in real projects.

Self-Check

"What if the input arrays were already sorted? How would the time complexity change?"

Practice

1. What does the function np.intersect1d() do in NumPy?

easy

A. Finds common elements between two arrays

B. Combines two arrays into one

C. Sorts an array in descending order

D. Removes duplicates from an array

Solution

1. Step 1: Understand the function purpose

   np.intersect1d() is designed to find elements that appear in both input arrays.

2. Step 2: Compare with other options

   Options A, B, and D describe different functions: sorting descending, combining arrays, and removing duplicates, which are not the purpose of np.intersect1d().

3. Final Answer:

   Finds common elements between two arrays -> Option A

4. Quick Check:

   Intersection = common elements [OK]

Hint: Think 'intersection' means shared items [OK]

Common Mistakes:

• Confusing intersection with concatenation
• Thinking it sorts descending
• Mixing with duplicate removal

2. Which of the following is the correct syntax to find the intersection of arrays a and b using NumPy?

easy

A. np.intersect(a, b)

B. np.intersection(a, b)

C. np.intersect1d(a, b)

D. np.intersect1d([a, b])

Solution

1. Step 1: Recall the correct function name and parameters

   The correct function is np.intersect1d() and it takes two arrays as separate arguments.

2. Step 2: Check each option

   np.intersect1d(a, b) uses the correct function and syntax. Options B and C use incorrect function names. np.intersect1d([a, b]) incorrectly passes a list of arrays instead of two separate arguments.

3. Final Answer:

   np.intersect1d(a, b) -> Option C

4. Quick Check:

   Correct function and parameters [OK]

Hint: Use exact function name and separate arrays as arguments [OK]

Common Mistakes:

• Using wrong function names
• Passing arrays inside a list
• Missing one argument

3. What is the output of the following code?

import numpy as np
x = np.array([3, 1, 4, 1, 5])
y = np.array([5, 9, 2, 6, 5])
print(np.intersect1d(x, y))

medium

A. [1 5]

B. [3 5]

C. [1 5 9]

D. [5]

Solution

1. Step 1: Identify unique elements in both arrays

   Array x has elements {1, 3, 4, 5} (1 appears twice but counted once). Array y has elements {2, 5, 6, 9} (5 appears twice but counted once).

2. Step 2: Find common elements

   The only common element between x and y is 5.

3. Final Answer:

   [5] -> Option D

4. Quick Check:

   Common elements = [5] [OK]

Hint: Look for numbers appearing in both arrays [OK]

Common Mistakes:

• Including duplicates
• Adding elements not in both arrays
• Confusing order of output

4. The following code throws an error. What is the problem?

import numpy as np
arr1 = [1, 2, 3]
arr2 = [2, 3, 4]
result = np.intersect1d(arr1 arr2)
print(result)

medium

A. Missing comma between arguments in np.intersect1d()

B. Arrays must be NumPy arrays, not lists

C. np.intersect1d() does not accept two arguments

D. print() function is used incorrectly

Solution

1. Step 1: Check the function call syntax

   The call np.intersect1d(arr1 arr2) is missing a comma between the two arguments.

2. Step 2: Verify other parts

   Passing lists is allowed because NumPy converts them internally. The function accepts two arguments. The print statement is correct.

3. Final Answer:

   Missing comma between arguments in np.intersect1d() -> Option A

4. Quick Check:

   Arguments must be separated by commas [OK]

Hint: Check commas between function arguments [OK]

Common Mistakes:

• Forgetting commas
• Thinking lists are invalid inputs
• Misreading error source

5. You have two arrays representing product IDs sold in two stores:

store1 = np.array([101, 102, 103, 104, 105])
store2 = np.array([104, 105, 106, 107])

How can you find the sorted list of product IDs sold in both stores using np.intersect1d()?

hard

A. np.union1d(store1, store2)

B. np.intersect1d(store1, store2)

C. np.setdiff1d(store1, store2)

D. np.concatenate((store1, store2))

Solution

1. Step 1: Understand the problem

   We want product IDs common to both stores, which means intersection.

2. Step 2: Choose the correct function

   np.intersect1d(store1, store2) returns sorted common elements. Other options return union, difference, or concatenation, which are not correct here.

3. Final Answer:

   np.intersect1d(store1, store2) -> Option B

4. Quick Check:

   Intersection = common products [OK]

Hint: Use intersect1d for common elements between arrays [OK]

Common Mistakes:

• Using union instead of intersection
• Using difference or concatenation
• Not sorting output