Multi-dimensional fancy indexing in NumPy - Time & Space Complexity

Time Complexity: Multi-dimensional fancy indexing

O(r * c)

Understanding Time Complexity

We want to understand how the time needed to pick elements from a multi-dimensional array changes as the array grows.

Specifically, how does fancy indexing with multiple index arrays affect the work done?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

import numpy as np

arr = np.arange(10000).reshape(100, 100)
rows = np.array([1, 3, 5, 7])
cols = np.array([2, 4, 6, 8])
result = arr[rows[:, None], cols]

This code selects elements from a 2D array using two index arrays for rows and columns, creating a new array of selected elements.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Accessing elements for each pair of row and column indices.
• How many times: For each row index, it accesses all column indices, so total accesses = number of rows in index array x number of columns in index array.

How Execution Grows With Input

As the size of the index arrays grows, the number of element accesses grows by multiplying their lengths.

Input Size (rows x cols)	Approx. Operations
10 x 10	100
100 x 100	10,000
1000 x 1000	1,000,000

Pattern observation: The operations grow by multiplying the sizes of the row and column index arrays, so doubling both quadruples the work.

Final Time Complexity

Time Complexity: O(r * c)

This means the time grows proportionally to the product of the lengths of the row and column index arrays.

Common Mistake

[X] Wrong: "The time depends only on the size of the original array, not on the index arrays."

[OK] Correct: The original array size does not affect how many elements are picked; the work depends on how many indices we use to select elements.

Interview Connect

Understanding how fancy indexing scales helps you reason about data selection performance in real projects, making your code efficient and clear.

Self-Check

"What if we used a single 1D index array instead of two 1D arrays for rows and columns? How would the time complexity change?"

Practice

1. What does multi-dimensional fancy indexing in NumPy allow you to do?

easy

A. Change the shape of the array without copying data.

B. Sort the array elements in ascending order.

C. Calculate the sum of all elements in the array.

D. Select specific elements from an array using lists of row and column indices.

Solution

1. Step 1: Understand the concept of fancy indexing

   Fancy indexing uses arrays or lists of indices to select elements from an array.

2. Step 2: Apply to multi-dimensional arrays

   In multi-dimensional fancy indexing, you provide lists of row and column indices to pick specific elements scattered in the array.

3. Final Answer:

   Select specific elements from an array using lists of row and column indices. -> Option D

4. Quick Check:

   Fancy indexing = element selection by index lists [OK]

Hint: Fancy indexing picks elements by matching row and column lists [OK]

Common Mistakes:

• Confusing fancy indexing with sorting
• Thinking it reshapes arrays
• Assuming it sums elements

2. Which of the following is the correct syntax for multi-dimensional fancy indexing in NumPy to select elements at rows [0, 2] and columns [1, 3] from array arr?

easy

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

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

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

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

Solution

1. Step 1: Recall fancy indexing syntax

   Multi-dimensional fancy indexing uses two lists inside square brackets: one for rows, one for columns.

2. Step 2: Match given indices

   To select elements at rows 0 and 2, columns 1 and 3, syntax is arr[[0, 2], [1, 3]].

3. Final Answer:

   arr[[0, 2], [1, 3]] -> Option A

4. Quick Check:

   Two index lists inside brackets = correct fancy indexing [OK]

Hint: Use two lists inside brackets for rows and columns [OK]

Common Mistakes:

• Using slicing instead of lists
• Mixing row and column indices in one list
• Using incorrect bracket placement

3. Given the array arr = np.array([[10, 20, 30, 40], [50, 60, 70, 80], [90, 100, 110, 120]]), what is the output of arr[[0, 2], [1, 3]]?

medium

A. [20 120]

B. [20 40]

C. [10 120]

D. [50 110]

Solution

1. Step 1: Identify indices from fancy indexing

   Rows are [0, 2], columns are [1, 3]. So elements are arr[0,1] and arr[2,3].

2. Step 2: Find elements at these positions

   arr[0,1] = 20, arr[2,3] = 120, so output is [20 120].

3. Final Answer:

   [20 120] -> Option A

4. Quick Check:

   Elements at (0,1) and (2,3) = [20 120] [OK]

Hint: Match row and column indices element-wise [OK]

Common Mistakes:

• Selecting entire rows or columns instead of elements
• Mixing up row and column indices
• Expecting a 2D array output

4. What error will occur when running the code below?

import numpy as np
arr = np.array([[1,2,3],[4,5,6]])
rows = [0,1]
cols = [1]
print(arr[rows, cols])

medium

A. ValueError because arr is 2D

B. SyntaxError because of wrong brackets

C. IndexError due to mismatched index array shapes

D. No error, prints [2 5]

Solution

1. Step 1: Check shapes of index arrays

   rows has length 2, cols has length 1; shapes differ.

2. Step 2: Understand fancy indexing requirements

   Fancy indexing requires index arrays to have the same shape for element-wise selection.

3. Final Answer:

   IndexError due to mismatched index array shapes -> Option C

4. Quick Check:

   Index arrays must match shape [OK]

Hint: Index arrays must be same shape for fancy indexing [OK]

Common Mistakes:

• Assuming different length index lists work
• Confusing syntax error with runtime error
• Expecting partial output without error

5. You have a 3x4 array data representing sales for 3 stores (rows) over 4 months (columns). You want to select sales for store 0 in month 1, store 2 in month 3, and store 1 in month 0 using multi-dimensional fancy indexing. Which code correctly extracts these values?

hard

A. data[[0, 1, 2], [1, 3, 0]]

B. data[[0, 2, 1], [1, 3, 0]]

C. data[[1, 3, 0], [0, 2, 1]]

D. data[[0, 2, 1]][[1, 3, 0]]

Solution

1. Step 1: Match stores and months as row and column indices

   Stores: 0, 2, 1 correspond to rows; months: 1, 3, 0 correspond to columns.

2. Step 2: Use multi-dimensional fancy indexing syntax

   Use data[[0, 2, 1], [1, 3, 0]] to select elements at these positions element-wise.

3. Final Answer:

   data[[0, 2, 1], [1, 3, 0]] -> Option B

4. Quick Check:

   Row and column lists match stores and months [OK]

Hint: Pair store and month indices in two lists for fancy indexing [OK]

Common Mistakes:

• Swapping row and column lists
• Using chained indexing instead of fancy indexing
• Mismatching lengths of index lists