Introduction
A multidimensional array generalizes the single-dimension array into a grid of rows and columns (or more dimensions), commonly used to represent matrices, images, and game boards. In Python, a 2D array is typically represented as a list of lists, where each inner list is a row.
Cricket analogy: A multidimensional array is like a fielding chart laid out as a grid of rows and columns marking each fielder's position, and in Python this grid is stored as a list of row-lists, one inner list per fielding line.
Explanation
A 2D array with R rows and C columns can be visualized as a table where element (i, j) refers to row i, column j. Two common memory layouts exist conceptually: row-major order (each row stored contiguously, used by Python/C) and column-major order (used by Fortran/MATLAB). Row-major order means iterating row by row, then column by column, is more cache-friendly than the reverse. Accessing element grid[i][j] takes O(1) because it is two chained O(1) index lookups. Traversing the entire structure takes O(R * C) since every cell must be visited once. When creating 2D arrays in Python, you must avoid using [[0] * C] * R, because that creates R references to the same inner list, causing unintended shared mutation.
Cricket analogy: A fielding grid with R rings and C sectors lets you find fielder (i, j) instantly, and scanning ring by ring is more efficient than sector by sector since each ring's fielders are noted together; but copying one ring's placeholder list R times by reference would make every ring share the same fielder, a classic setup mistake.
Example
# Correct way to build a 2D array (list of lists) in Python
rows, cols = 3, 4
grid = [[0] * cols for _ in range(rows)]
grid[1][2] = 9
print(grid)
# [[0, 0, 0, 0], [0, 0, 9, 0], [0, 0, 0, 0]]
# Row-major traversal, O(R * C)
def sum_grid(grid):
total = 0
for row in grid:
for value in row:
total += value
return total
print(sum_grid(grid)) # 9
# Transpose a matrix (swap rows and columns)
def transpose(matrix):
return [[matrix[r][c] for r in range(len(matrix))] for c in range(len(matrix[0]))]
matrix = [[1, 2, 3], [4, 5, 6]]
print(transpose(matrix)) # [[1, 4], [2, 5], [3, 6]]
# The common pitfall: aliasing rows
broken = [[0] * cols] * rows
broken[0][0] = 1
print(broken) # every row changes: [[1,0,0,0],[1,0,0,0],[1,0,0,0]]Complexity
Accessing grid[i][j] is O(1). Traversing every cell of an R x C grid is O(R * C), which is O(n) in terms of total elements n = R*C. Creating an R x C grid takes O(R * C) space and time. Row-wise traversal is more cache-efficient than column-wise traversal because rows are stored contiguously in Python's list-of-lists representation.
Cricket analogy: Finding fielder (i, j) on the chart is O(1), but walking every position on an R-ring, C-sector chart is O(R*C) since every cell must be checked; setting up the chart itself takes O(R*C) time and space, and scanning ring by ring is faster than sector by sector due to how the chart is laid out contiguously.
Key Takeaways
- A 2D array in Python is a list of lists; grid[i][j] accesses row i, column j in O(1).
- Traversing an R x C grid costs O(R * C); build it correctly with a list comprehension to avoid row aliasing.
- Row-major traversal (row by row) is more cache-friendly than column-major traversal.
- Multidimensional arrays underlie matrices, images, adjacency matrices for graphs, and dynamic programming tables.
Practice what you learned
1. What is the time complexity of accessing element grid[i][j] in a 2D array?
2. What is the time complexity of visiting every element in an R x C grid?
3. Why does `grid = [[0] * cols] * rows` cause a bug in Python?
4. Which traversal order is more cache-friendly for a Python list-of-lists 2D array?
Was this page helpful?
You May Also Like
Arrays in Data Structures
How arrays store elements in contiguous memory and why that layout drives their performance characteristics.
Common Array and String Problems
Classic array and string interview patterns like two-pointer and sliding window, with worked examples and complexity.
Common Data Structures Interview Questions
A curated set of frequently asked data structures interview questions with technically accurate, concise answers.