Indexing with ellipsis in NumPy - Time & Space Complexity

Time Complexity: Indexing with ellipsis

O(1)

Understanding Time Complexity

We want to understand how fast numpy runs when we use ellipsis for indexing.

Specifically, how does the time change when we select parts of big arrays with ellipsis?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

import numpy as np

arr = np.random.rand(1000, 1000, 10)
result = arr[..., 5]

This code selects the 6th element from the last dimension of a 3D array using ellipsis.

Identify Repeating Operations

Look for loops or repeated steps inside the operation.

• Primary operation: Constructing a strided view by adjusting strides, shape, and base pointer.
• How many times: Constant time, O(1), independent of array size.

How Execution Grows With Input

When the array size grows, the execution time remains constant.

Input Size (n x n x 10)	Approx. Operations
10 x 10 x 10	O(1)
100 x 100 x 10	O(1)
1000 x 1000 x 10	O(1)

Pattern observation: The operations are constant regardless of array dimensions, as NumPy slicing creates a view without copying data.

Final Time Complexity

Time Complexity: O(1)

This means the time is constant and independent of the number of elements in the array dimensions, because it creates a lightweight view.

Common Mistake

[X] Wrong: "Using ellipsis takes O(n^2) time proportional to the output size."

[OK] Correct: Ellipsis expands to basic slicing (:, :, 5), which NumPy implements in constant time via views, without accessing or copying elements.

Interview Connect

Understanding how indexing affects performance helps you write efficient data code and explain your choices clearly.

Self-Check

What if we changed the code to select a slice like arr[..., 2:7]? How would the time complexity change?

Practice

1. What does the ellipsis (...) represent when indexing a NumPy array?

easy

A. It selects all remaining dimensions in the array.

B. It selects only the first dimension of the array.

C. It selects the last element of the array.

D. It creates a new axis in the array.

Solution

1. Step 1: Understand ellipsis usage

   The ellipsis (...) is used to replace multiple colons when slicing multi-dimensional arrays.

2. Step 2: Interpret ellipsis effect

   It selects all remaining dimensions not explicitly indexed, making code shorter and clearer.

3. Final Answer:

   It selects all remaining dimensions in the array. -> Option A

4. Quick Check:

   Ellipsis = all remaining dimensions [OK]

Hint: Ellipsis means 'all other dimensions' in slicing [OK]

Common Mistakes:

• Thinking ellipsis selects only one dimension
• Confusing ellipsis with new axis insertion
• Assuming ellipsis selects last element only

2. Which of the following is the correct syntax to select all rows and columns except the last one in a 3D NumPy array arr using ellipsis?

easy

A. arr[:, :, -1]

B. arr[..., :-1]

C. arr[..., -1]

D. arr[:, :-1, :]

Solution

1. Step 1: Understand the array shape and slicing

   For a 3D array, arr[..., :-1] means select all elements in the first two dimensions and slice the last dimension up to but not including the last element.

2. Step 2: Compare options

   arr[..., :-1] uses ellipsis to cover first two dimensions and slices last dimension correctly. arr[:, :, -1] incorrectly selects only the last element in the last dimension. arr[..., -1] selects only the last slice, and D slices the second dimension incorrectly.

3. Final Answer:

   arr[..., :-1] -> Option B

4. Quick Check:

   Ellipsis + slice last dim = arr[..., :-1] [OK]

Hint: Ellipsis covers all but last dim; slice last dim with :-1 [OK]

Common Mistakes:

• Using ellipsis but slicing wrong dimension
• Confusing negative index with slice
• Not using ellipsis and writing long slices

3. Given the code:

import numpy as np
arr = np.arange(24).reshape(2,3,4)
result = arr[1, ..., 2]

What is the value of result?

medium

A. [2 6 10]

B. [10 14 18]

C. [10 11 12]

D. [14 18 22]

Solution

1. Step 1: Understand array shape and indexing

   The array arr has shape (2, 3, 4). Indexing arr[1, ..., 2] means select the second block (index 1) in the first dimension, all elements in the second dimension, and the element at index 2 in the last dimension.

2. Step 2: Extract values

   For arr[1], the 3x4 block is:
   [ [12,13,14,15],
   [16,17,18,19],
   [20,21,22,23] ]
   Selecting all rows and column 2 gives [14, 18, 22]. But since the last dimension index is 2, it picks the third element in each row.
   So the result is [14, 18, 22].

3. Final Answer:

   [14 18 22] -> Option D

4. Quick Check:

   arr[1, :, 2] = [14 18 22] [OK]

Hint: Ellipsis fills middle dims; last index picks element in last dim [OK]

Common Mistakes:

• Confusing dimension order
• Mixing up index 1 and 2
• Assuming ellipsis selects only one dimension

4. Consider the code:

import numpy as np
arr = np.arange(27).reshape(3,3,3)
print(arr[..., 1:])

It raises an error. What is the most likely cause?

medium

A. The code is correct and will not raise an error.

B. Ellipsis cannot be combined with slices.

C. The slice 1: is invalid for the last dimension.

D. The array shape does not support ellipsis indexing.

Solution

1. Step 1: Analyze ellipsis with slice

   Ellipsis (...) can be combined with slices to select parts of the array. Here, arr[..., 1:] means select all elements in the first two dimensions and slice from index 1 to end in the last dimension.

2. Step 2: Check array shape compatibility

   The array shape is (3,3,3), so slicing last dimension from 1 to end is valid (indexes 1 and 2). No error should occur.

3. Final Answer:

   The code is correct and will not raise an error. -> Option A

4. Quick Check:

   Ellipsis + slice = valid syntax [OK]

Hint: Ellipsis works fine with slices; no error here [OK]

Common Mistakes:

• Assuming ellipsis can't be combined with slices
• Thinking slice 1: is out of bounds
• Believing ellipsis changes array shape

5. You have a 4D NumPy array data with shape (5, 4, 3, 2). You want to select the last element in the second dimension, all elements in the third dimension, and the first element in the last dimension, for all elements in the first dimension. Which indexing expression using ellipsis is correct?

hard

A. data[:, -1, :, 0]

B. data[:, ..., :, 0]

C. data[:, -1, ..., 0]

D. data[:, -1, :, 0, ...]

Solution

1. Step 1: Understand the array shape and desired selection

   The array shape is (5, 4, 3, 2). We want:
   - all elements in first dimension (5)
   - last element in second dimension (index -1)
   - all elements in third dimension (3)
   - first element in last dimension (index 0)

2. Step 2: Use ellipsis to simplify indexing

   Using data[:, -1, ..., 0] means:
   - select all in first dim
   - select last in second dim
   - ellipsis covers remaining dims (third and last)
   - then select 0 in last dim
   But ellipsis here covers dims 3 and 4, so 0 applies to last dim.
   data[:, -1, ..., 0] matches this logic correctly.

3. Step 3: Check other options

   data[:, -1, :, 0] is correct but does not use ellipsis.
   data[:, ..., :, 0] uses ellipsis but selects all elements in the second dimension (instead of the last one).
   data[:, -1, :, 0, ...] has too many indices (5) for 4D array.

4. Final Answer:

   data[:, -1, ..., 0] -> Option C

5. Quick Check:

   Ellipsis fills middle dims; index last dim after ellipsis [OK]

Hint: Ellipsis fills middle dims; place indices before and after correctly [OK]

Common Mistakes:

• Using too many indices for array dimensions
• Misplacing ellipsis causing wrong dimension selection
• Not understanding which dims ellipsis covers