Fancy indexing with integer arrays in NumPy - Time & Space Complexity

Time Complexity: Fancy indexing with integer arrays

O(n)

Understanding Time Complexity

We want to understand how the time needed to pick elements using fancy indexing changes as the size of the index array grows.

How does the work grow when we select many elements at once?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

import numpy as np

arr = np.arange(1000000)
indices = np.array([10, 500, 999999, 12345, 67890])
selected = arr[indices]

This code picks elements from a large array using a smaller array of integer positions.

Identify Repeating Operations

• Primary operation: Accessing elements at each index in the integer array.
• How many times: Once for each index in the indices array.

How Execution Grows With Input

Each element requested requires one access operation, so the total work grows directly with the number of indices.

Input Size (n)	Approx. Operations
10	10 element accesses
100	100 element accesses
1000	1000 element accesses

Pattern observation: Doubling the number of indices doubles the work.

Final Time Complexity

Time Complexity: O(n)

This means the time to select elements grows linearly with the number of indices you use.

Common Mistake

[X] Wrong: "Fancy indexing is instant no matter how many indices I use."

[OK] Correct: Each index requires accessing the array, so more indices mean more work and more time.

Interview Connect

Understanding how indexing scales helps you explain data selection efficiency and choose the right approach when working with large datasets.

Self-Check

What if we changed the indices array to a boolean mask of the same size? How would the time complexity change?

Practice

1. What does fancy indexing with integer arrays in NumPy allow you to do?

easy

A. Create a new array filled with zeros

B. Sort an array in ascending order

C. Select multiple elements from an array using a list of positions

D. Change the data type of an array

Solution

1. Step 1: Understand fancy indexing

   Fancy indexing uses a list or array of integers to pick elements by their positions.

2. Step 2: Identify the correct operation

   It selects multiple elements from the original array based on given indices.

3. Final Answer:

   Select multiple elements from an array using a list of positions -> Option C

4. Quick Check:

   Fancy indexing = select elements by positions [OK]

Hint: Fancy indexing picks elements by position list [OK]

Common Mistakes:

• Confusing fancy indexing with sorting
• Thinking it changes data type
• Assuming it creates arrays of zeros

2. Which of the following is the correct syntax to select elements at positions 0, 2, and 4 from a NumPy array arr using fancy indexing?

easy

A. arr{0, 2, 4}

B. arr(0, 2, 4)

C. arr[0:2:4]

D. arr[[0, 2, 4]]

Solution

1. Step 1: Recall fancy indexing syntax

   Fancy indexing uses double square brackets with a list or array of indices inside.

2. Step 2: Match syntax to options

   Only arr[[0, 2, 4]] uses correct double brackets and list format.

3. Final Answer:

   arr[[0, 2, 4]] -> Option D

4. Quick Check:

   Double brackets with list = correct fancy indexing [OK]

Hint: Use double brackets with list for fancy indexing [OK]

Common Mistakes:

• Using parentheses instead of brackets
• Using curly braces which are invalid
• Using slicing syntax incorrectly

3. What is the output of the following code?

import numpy as np
arr = np.array([10, 20, 30, 40, 50])
indices = np.array([1, 3, 4])
result = arr[indices]
print(result)

medium

A. [20 40 50]

B. [10 30 40]

C. [20 30 40]

D. [50 40 20]

Solution

1. Step 1: Understand the array and indices

   Original array is [10, 20, 30, 40, 50]. Indices are [1, 3, 4].

2. Step 2: Select elements at given indices

   Elements at positions 1, 3, 4 are 20, 40, 50 respectively.

3. Final Answer:

   [20 40 50] -> Option A

4. Quick Check:

   arr[1,3,4] = [20 40 50] [OK]

Hint: Match indices to array positions to get output [OK]

Common Mistakes:

• Mixing up indices and values
• Using wrong positions from array
• Confusing slicing with fancy indexing

4. Identify the error in the following code snippet:

import numpy as np
arr = np.array([5, 10, 15, 20])
indices = [1, 4]
print(arr[indices])

medium

A. IndexError because index 4 is out of bounds

B. SyntaxError due to wrong brackets

C. TypeError because indices is a list

D. No error, prints [10 20]

Solution

1. Step 1: Check array size and indices

   Array length is 4, valid indices are 0 to 3. Index 4 is invalid.

2. Step 2: Understand error type

   Accessing index 4 causes IndexError: index out of bounds.

3. Final Answer:

   IndexError because index 4 is out of bounds -> Option A

4. Quick Check:

   Index 4 invalid for length 4 array [OK]

Hint: Check if all indices are within array length [OK]

Common Mistakes:

• Assuming list indices are always valid
• Confusing syntax errors with index errors
• Thinking list indices cause type errors

5. Given a 2D NumPy array arr = np.array([[1,2,3],[4,5,6],[7,8,9]]), how can you use fancy indexing to select elements at positions (0,2), (1,0), and (2,1) and create a new 1D array with these values?

hard

A. arr[[0,2,1], [2,1,0]]

B. arr[[0,1,2], [2,0,1]]

C. arr[[2,1,0], [0,1,2]]

D. arr[[0,1,2]][[2,0,1]]

Solution

1. Step 1: Understand 2D fancy indexing

   To select elements at (row, col) positions, use two index arrays: one for rows, one for columns.

2. Step 2: Match given positions to index arrays

   Positions are (0,2), (1,0), (2,1), so rows = [0,1,2], cols = [2,0,1].

3. Step 3: Use fancy indexing syntax

   Use arr[[0,1,2], [2,0,1]] to get elements [3,4,8].

4. Final Answer:

   arr[[0,1,2], [2,0,1]] -> Option B

5. Quick Check:

   Rows and cols arrays match positions [OK]

Hint: Use two index arrays: rows and columns [OK]

Common Mistakes:

• Mixing row and column indices order
• Using chained indexing instead of fancy indexing
• Using wrong index arrays for positions