Nested list comprehension in Python - Time & Space Complexity

Time Complexity: Nested list comprehension

O(n * m)

Understanding Time Complexity

When we use nested list comprehensions, the computer repeats some steps many times.

We want to know how the time needed grows as the input gets bigger.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

matrix = [[1, 2], [3, 4], [5, 6]]
result = [y * 2 for x in matrix for y in x]

This code multiplies each number inside each inner list by 2 and collects the results in one list.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The inner loop goes through each element inside each inner list.
• How many times: For each inner list, it runs once for every element inside it.

How Execution Grows With Input

Imagine the matrix has n inner lists, each with m elements.

Input Size (n x m)	Approx. Operations
10 x 2	20
100 x 5	500
1000 x 10	10,000

Pattern observation: The total steps grow by multiplying the number of inner lists by the number of elements inside each.

Final Time Complexity

Time Complexity: O(n * m)

This means the time grows in proportion to the total number of elements inside all inner lists combined.

Common Mistake

[X] Wrong: "Nested list comprehensions always mean the time is squared, like O(n²)."

[OK] Correct: The time depends on how many elements are inside each inner list. If inner lists are small or fixed size, the time grows mostly with the outer list size.

Interview Connect

Understanding how nested loops inside list comprehensions affect time helps you explain your code clearly and shows you can think about efficiency.

Self-Check

"What if the inner lists have different lengths? How would the time complexity change?"

Practice

1. What does the following nested list comprehension do?
[[x * 2 for x in range(3)] for _ in range(2)]

easy

A. Creates a list of two lists, each with numbers from 0 to 3

B. Creates a flat list of numbers doubled from 0 to 5

C. Creates a list of three lists, each with numbers doubled from 0 to 1

D. Creates a list of two lists, each with numbers doubled from 0 to 2

Solution

1. Step 1: Understand inner list comprehension

   The inner part [x * 2 for x in range(3)] creates a list by doubling numbers 0, 1, 2 resulting in [0, 2, 4].

2. Step 2: Understand outer list comprehension

   The outer loop runs twice (for _ in range(2)), repeating the inner list twice, making [[0, 2, 4], [0, 2, 4]].

3. Final Answer:

   Creates a list of two lists, each with numbers doubled from 0 to 2 -> Option D

4. Quick Check:

   Nested loops create repeated doubled lists [OK]

Hint: Inner loop builds list, outer repeats it [OK]

Common Mistakes:

• Confusing outer and inner loops
• Thinking it creates a flat list
• Miscounting range values

2. Which of the following is the correct syntax for a nested list comprehension that creates a 3x3 matrix of zeros?

easy

A. [[0] * 3] * 3

B. [0 for _ in range(3) for _ in range(3)]

C. [[0 for _ in range(3)] for _ in range(3)]

D. [0] * 3 for _ in range(3)

Solution

1. Step 1: Identify correct nested comprehension syntax

   [[0 for _ in range(3)] for _ in range(3)] uses two for loops inside list brackets correctly: outer and inner loops create rows and columns.

2. Step 2: Check other options for syntax errors

   [0 for _ in range(3) for _ in range(3)] is flat comprehension, not nested. [[0] * 3] * 3 uses list multiplication but not comprehension. [0] * 3 for _ in range(3) is invalid syntax.

3. Final Answer:

   [[0 for _ in range(3)] for _ in range(3)] -> Option C

4. Quick Check:

   Nested loops inside brackets = correct syntax [OK]

Hint: Nested loops inside brackets create nested lists [OK]

Common Mistakes:

• Using flat comprehension instead of nested
• Incorrect list multiplication for nested lists
• Syntax errors with missing brackets

3. What is the output of this code?

matrix = [[i + j for j in range(3)] for i in range(2)]
print(matrix)

medium

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

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

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

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

Solution

1. Step 1: Understand inner loop values

   For each i, inner loop adds j (0,1,2) to i. For i=0: [0+0, 0+1, 0+2] = [0,1,2]. For i=1: [1+0, 1+1, 1+2] = [1,2,3].

2. Step 2: Combine results into outer list

   The outer loop runs for i in range(2), so final list is [[0,1,2], [1,2,3]].

3. Final Answer:

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

4. Quick Check:

   Sum of i and j in nested loops = output [OK]

Hint: Add outer and inner loop vars for each element [OK]

Common Mistakes:

• Mixing i and j values
• Confusing list dimensions
• Incorrect range usage

4. Find the error in this nested list comprehension:

result = [[x * y for x in range(3)] for y in range(3)]
print(result)

medium

A. No error, code runs correctly

B. Inner loop variable x is undefined

C. Outer loop variable y is used before definition

D. Syntax error due to missing brackets

Solution

1. Step 1: Check variable definitions

   Both x and y are defined in their respective loops: x in inner, y in outer.

2. Step 2: Verify syntax and logic

   Syntax is correct with proper brackets. The code multiplies x and y for each pair in ranges 0 to 2.

3. Final Answer:

   No error, code runs correctly -> Option A

4. Quick Check:

   Variables defined in loops, syntax correct [OK]

Hint: Check variable scopes in nested loops [OK]

Common Mistakes:

• Thinking variables are undefined
• Confusing loop order
• Assuming syntax error without checking

5. Using nested list comprehension, how can you transform this nested list:

data = [[1, 0, 3], [0, 5, 0], [7, 0, 9]]

to replace all zeros with the string 'zero'?

hard

A. [['zero' if row == 0 else x for x in row] for row in data]

B. [['zero' if x == 0 else x for x in row] for row in data]

C. [['zero' if x == 0 else x for row in data] for x in row]

D. [['zero' if x == 0 else x for x in data] for row in data]

Solution

1. Step 1: Use nested loops to access each element

   Outer loop goes through each row, inner loop through each element x in that row.

2. Step 2: Replace zeros with 'zero' using conditional expression

   Use 'zero' if x == 0 else x inside inner loop to transform elements.

3. Step 3: Combine into nested list comprehension

   Putting it together: [[ 'zero' if x == 0 else x for x in row ] for row in data].

4. Final Answer:

   [['zero' if x == 0 else x for x in row] for row in data] -> Option B

5. Quick Check:

   Conditional inside nested comprehension replaces zeros [OK]

Hint: Use if-else inside inner loop for element replacement [OK]

Common Mistakes:

• Mixing loop variables
• Placing condition on wrong variable
• Incorrect loop order or syntax