Loading learning content...
Now that you understand how matrices are structured, stored, and traversed, it's time to build your operational toolkit—the set of transformations and algorithms that you'll apply repeatedly when working with 2D arrays.
These operations form the foundation of countless practical applications. Image rotation in a photo editor? Matrix rotation. Efficiently searching in a sorted spreadsheet? Searching in sorted matrices. Transforming data layouts? Transposition. Understanding these operations deeply means you can solve entire classes of problems by recognizing which operation applies.
By the end of this page, you will master matrix transposition, 90-degree rotations (clockwise and counterclockwise), searching in row-wise and fully sorted matrices, in-place transformations, and common problem patterns like setting rows/columns to zero and finding islands.
Transposition is one of the most fundamental matrix operations. It converts rows into columns and columns into rows: element [i][j] becomes element [j][i].
Definition:
For a matrix A with dimensions m×n, its transpose Aᵀ has dimensions n×m, where:
Visual Example:
Original Matrix A (2×3): Transpose Aᵀ (3×2): Col0 Col1 Col2 Col0 Col1 ┌─────┬─────┬─────┐ ┌─────┬─────┐R0 │ 1 │ 2 │ 3 │ R0 │ 1 │ 4 │ ├─────┼─────┼─────┤ ├─────┼─────┤R1 │ 4 │ 5 │ 6 │ R1 │ 2 │ 5 │ └─────┴─────┴─────┘ ├─────┼─────┤ R2 │ 3 │ 6 │ └─────┴─────┘ Row 0 of A [1,2,3] becomes Column 0 of AᵀRow 1 of A [4,5,6] becomes Column 1 of Aᵀ1234567891011121314151617181920212223
// Transpose a non-square matrix (creates new matrix)def transpose(matrix): if not matrix or not matrix[0]: return [] rows = len(matrix) cols = len(matrix[0]) // Create new matrix with swapped dimensions transposed = [[0 for _ in range(rows)] for _ in range(cols)] for i in range(rows): for j in range(cols): transposed[j][i] = matrix[i][j] return transposed // Example:original = [[1, 2, 3], [4, 5, 6]]result = transpose(original)// result = [[1, 4], [2, 5], [3, 6]] // Complexity: O(m × n) time, O(m × n) spaceIn-Place Transpose (Square Matrices Only):
For square matrices, we can transpose without extra space by swapping elements across the main diagonal:
12345678910111213141516171819202122232425
// In-place transpose for square matricesdef transpose_inplace(matrix): n = len(matrix) // Only swap elements above the main diagonal // (swapping both above and below would swap twice = no change) for i in range(n): for j in range(i + 1, n): // j starts at i+1 matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j] // Example:matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]] transpose_inplace(matrix)// matrix is now:// [[1, 4, 7],// [2, 5, 8],// [3, 6, 9]] // Note: Elements on the main diagonal (1, 5, 9) don't move// Swaps: (2,4), (3,7), (6,8) // Complexity: O(n²) time, O(1) spaceTransposition is used for: (1) rotating matrices (combined with reversal), (2) converting between row-major and column-major layouts, (3) preparing matrices for algorithms that work better on columns, (4) computing matrix products (Aᵀ × B), and (5) changing data orientation for visualization.
Rotating a matrix by 90 degrees is a common operation in image processing, game development, and puzzle algorithms. There are elegant approaches that combine simpler operations.
Understanding the Rotation:
When we rotate 90° clockwise:
Original: Rotated 90° Clockwise:┌─────┬─────┬─────┐ ┌─────┬─────┬─────┐│ 1 │ 2 │ 3 │ │ 7 │ 4 │ 1 │├─────┼─────┼─────┤ ──▶ ├─────┼─────┼─────┤│ 4 │ 5 │ 6 │ │ 8 │ 5 │ 2 │├─────┼─────┼─────┤ ├─────┼─────┼─────┤│ 7 │ 8 │ 9 │ │ 9 │ 6 │ 3 │└─────┴─────┴─────┘ └─────┴─────┴─────┘ Observations:- Element at [0][0] (1) moves to [0][2]- Element at [0][2] (3) moves to [2][2]- Element at [2][2] (9) moves to [2][0]- Element at [2][0] (7) moves to [0][0] General formula: [i][j] → [j][n-1-i] (for 90° clockwise)The Elegant Approach: Transpose + Reverse
Instead of tracking complex index mappings, we can compose two simpler operations:
123456789101112131415161718192021222324252627282930
// 90° Clockwise = Transpose + Reverse each rowdef rotate_90_clockwise(matrix): n = len(matrix) // Step 1: Transpose (swap across main diagonal) for i in range(n): for j in range(i + 1, n): matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j] // Step 2: Reverse each row for i in range(n): matrix[i].reverse() // Or: matrix[i] = matrix[i][::-1] // Example walkthrough:matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]] // After transpose:// [[1, 4, 7],// [2, 5, 8],// [3, 6, 9]] // After reversing each row:// [[7, 4, 1],// [8, 5, 2],// [9, 6, 3]] // Complexity: O(n²) time, O(1) spaceAll Four Rotation Variants:
| Rotation | Method 1 | Method 2 |
|---|---|---|
| 90° Clockwise | Transpose, then reverse each row | Reverse each column, then transpose |
| 90° Counter-clockwise | Transpose, then reverse each column | Reverse each row, then transpose |
| 180° | Reverse each row, then reverse each column | 90° clockwise twice |
| 270° (= 90° CCW) | Same as 90° counter-clockwise | 90° clockwise three times |
1234567891011121314151617181920212223242526
// 90° Counter-clockwise = Transpose + Reverse each columndef rotate_90_counterclockwise(matrix): n = len(matrix) // Transpose for i in range(n): for j in range(i + 1, n): matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j] // Reverse each column (or equivalently, reverse the order of rows) for col in range(n): top, bottom = 0, n - 1 while top < bottom: matrix[top][col], matrix[bottom][col] = matrix[bottom][col], matrix[top][col] top += 1 bottom -= 1 // 180° Rotationdef rotate_180(matrix): n = len(matrix) // Reverse each row for i in range(n): matrix[i].reverse() // Reverse order of rows matrix.reverse() // Alternatively: rotate 90° twiceThe in-place rotation shown here works only for square matrices. Rotating a non-square matrix (m×n) 90° produces an n×m matrix, which requires creating a new matrix. The formula for 90° clockwise: new_matrix[j][m-1-i] = old_matrix[i][j].
Matrices with sorted properties allow much faster search than the naive O(m×n) scan. There are two common sorted matrix types:
Type 1: Row-wise Sorted
Each row is sorted, but there's no relationship between rows. Example: sorted lists of items per category.
Type 2: Row-wise AND Column-wise Sorted (Young Tableau)
Each row is sorted left-to-right, AND each column is sorted top-to-bottom. This is more restrictive but enables elegant algorithms.
Type 1 - Row-wise Sorted Only:┌─────┬─────┬─────┬─────┐│ 2 │ 5 │ 8 │ 12 │ ← sorted within row├─────┼─────┼─────┼─────┤│ 1 │ 4 │ 9 │ 15 │ ← sorted within row├─────┼─────┼─────┼─────┤│ 3 │ 6 │ 11 │ 18 │ ← sorted within row└─────┴─────┴─────┴─────┘No column ordering guarantee Type 2 - Row-wise AND Column-wise Sorted:┌─────┬─────┬─────┬─────┐│ 1 │ 4 │ 7 │ 11 │ ← sorted within row├─────┼─────┼─────┼─────┤│ 2 │ 5 │ 8 │ 12 │ ← sorted within row├─────┼─────┼─────┼─────┤│ 3 │ 6 │ 9 │ 16 │ ← sorted within row└─────┴─────┴─────┴─────┘ ↑ ↑ ↑ ↑ Each column also sortedSearching Row-wise Sorted Matrix:
Binary search each row for O(m log n) complexity:
123456789101112131415161718192021222324252627
def search_row_sorted(matrix, target): """ Search in a matrix where each row is sorted. Time: O(m log n), Space: O(1) """ def binary_search(row, target): left, right = 0, len(row) - 1 while left <= right: mid = (left + right) // 2 if row[mid] == target: return mid elif row[mid] < target: left = mid + 1 else: right = mid - 1 return -1 for row_idx, row in enumerate(matrix): col_idx = binary_search(row, target) if col_idx != -1: return (row_idx, col_idx) return None // Not found // Example:matrix = [[2, 5, 8, 12], [1, 4, 9, 15], [3, 6, 11, 18]]print(search_row_sorted(matrix, 9)) // (1, 2)Searching Row+Column Sorted Matrix (Staircase Search):
This elegant algorithm achieves O(m + n) by starting from a corner and making decisions based on comparisons:
123456789101112131415161718192021222324252627282930313233343536373839
def search_sorted_matrix(matrix, target): """ Search in a matrix sorted both row-wise and column-wise. Time: O(m + n), Space: O(1) Strategy: Start at top-right (or bottom-left) corner. - If current == target: found - If current > target: move left (eliminate this column) - If current < target: move down (eliminate this row) """ if not matrix or not matrix[0]: return None rows, cols = len(matrix), len(matrix[0]) row, col = 0, cols - 1 // Start at top-right corner while row < rows and col >= 0: current = matrix[row][col] if current == target: return (row, col) elif current > target: col -= 1 // Target is smaller, go left else: row += 1 // Target is larger, go down return None // Not found // Example walkthrough searching for 5:matrix = [[1, 4, 7, 11], [2, 5, 8, 12], [3, 6, 9, 16]] // Start at [0][3] = 11. 11 > 5, go left.// At [0][2] = 7. 7 > 5, go left.// At [0][1] = 4. 4 < 5, go down.// At [1][1] = 5. Found! Return (1, 1) // This took 4 steps for a 3×4 matrix (at most 3+4-1 = 6 steps)The top-right and bottom-left corners are special: from these positions, moving in each direction gives opposite orderings. At top-right, going left decreases values and going down increases them. This property enables eliminating a full row or column with each comparison. The top-left and bottom-right corners don't have this property.
This classic problem demonstrates in-place matrix manipulation: given a matrix, if an element is 0, set its entire row and column to 0.
The Challenge:
We can't set zeros while scanning because that creates new zeros, which cascade incorrectly. We need to first identify which rows and columns contain zeros, then apply the changes.
Naive Approach (O(m + n) extra space):
12345678910111213141516171819202122232425262728293031
def set_zeros_extra_space(matrix): """ Mark rows/columns to zero using separate arrays. Time: O(m × n), Space: O(m + n) """ rows, cols = len(matrix), len(matrix[0]) zero_rows = set() zero_cols = set() // Pass 1: Find all zeros for i in range(rows): for j in range(cols): if matrix[i][j] == 0: zero_rows.add(i) zero_cols.add(j) // Pass 2: Set zeros for i in range(rows): for j in range(cols): if i in zero_rows or j in zero_cols: matrix[i][j] = 0 // Example:matrix = [[1, 1, 1], [1, 0, 1], [1, 1, 1]]set_zeros_extra_space(matrix)// Result:// [[1, 0, 1],// [0, 0, 0],// [1, 0, 1]]Optimal Approach (O(1) extra space):
Use the first row and first column of the matrix itself as markers:
12345678910111213141516171819202122232425262728293031
def set_zeros_constant_space(matrix): """ Use first row/column as markers for O(1) space. Time: O(m × n), Space: O(1) """ rows, cols = len(matrix), len(matrix[0]) first_row_has_zero = any(matrix[0][j] == 0 for j in range(cols)) first_col_has_zero = any(matrix[i][0] == 0 for i in range(rows)) // Pass 1: Use first row/col as markers for rest of matrix for i in range(1, rows): for j in range(1, cols): if matrix[i][j] == 0: matrix[i][0] = 0 // Mark row matrix[0][j] = 0 // Mark column // Pass 2: Zero out cells based on markers for i in range(1, rows): for j in range(1, cols): if matrix[i][0] == 0 or matrix[0][j] == 0: matrix[i][j] = 0 // Pass 3: Handle first row if first_row_has_zero: for j in range(cols): matrix[0][j] = 0 // Pass 4: Handle first column if first_col_has_zero: for i in range(rows): matrix[i][0] = 0By using the first row to track which columns need zeroing and the first column to track which rows need zeroing, we repurpose existing matrix space instead of allocating new arrays. We just need to separately remember if the first row/column themselves contained zeros.
Some operations naturally work on matrix "layers" or "rings"—the concentric rectangular boundaries from outside to inside.
Visualizing Layers:
5×5 Matrix Layers:┌─────────────────────────────────┐│ 0 0 0 0 0 │ Layer 0 (outermost)│ ┌─────────────────────┐ ││ │ 1 1 1 1 │ │ │ Layer 1│ │ ┌─────────────┐ │ │ ││ │ │ 2 (center) │ │ │ │ Layer 2 (innermost)│ │ └─────────────┘ │ │ ││ │ 1 1 1 1 │ │ ││ └─────────────────────┘ ││ 0 0 0 0 0 │└─────────────────────────────────┘ Number of layers = ceil(min(rows, cols) / 2)For 5×5: 3 layersFor 4×4: 2 layersFor 3×3: 2 layers (center is a single cell)Rotating a Layer (Used in 90° Rotation by Layers):
Another approach to 90° rotation processes each layer independently, rotating groups of 4 elements:
1234567891011121314151617181920212223242526272829303132333435
def rotate_90_by_layers(matrix): """ Rotate 90° clockwise by processing each layer. For each position in a layer, rotate 4 elements as a group. """ n = len(matrix) // Process each layer from outside to inside for layer in range(n // 2): first = layer last = n - 1 - layer for i in range(first, last): offset = i - first // Save top element top = matrix[first][i] // Move left to top matrix[first][i] = matrix[last - offset][first] // Move bottom to left matrix[last - offset][first] = matrix[last][last - offset] // Move right to bottom matrix[last][last - offset] = matrix[i][last] // Move saved top to right matrix[i][last] = top // Example: rotating layer 0 of a 4×4 matrix// Positions in layer 0: corners and edges// Rotate groups: (0,0)→(0,3)→(3,3)→(3,0)→(0,0)// (0,1)→(1,3)→(3,2)→(2,0)→(0,1)// (0,2)→(2,3)→(3,1)→(1,0)→(0,2)Layer-based processing is powerful for: (1) rotation by 90° in-place, (2) spiral traversal (as we saw earlier), (3) onion peeling algorithms for optimization problems, (4) border processing that shrinks inward. The transpose+reverse method is often simpler for rotation, but understanding layers deepens your matrix intuition.
A common category of matrix problems involves finding or counting connected regions—often called "islands" when the matrix represents a map with land (1) and water (0).
The Classic Island Problem:
Given a 2D grid of '1's (land) and '0's (water), count the number of islands. An island is a group of adjacent lands connected horizontally or vertically.
Approach: DFS/BFS Flood Fill
12345678910111213141516171819202122232425262728293031323334353637383940414243
def count_islands(grid): """ Count connected components of 1s using DFS. Time: O(m × n), Space: O(m × n) for recursion stack in worst case """ if not grid or not grid[0]: return 0 rows, cols = len(grid), len(grid[0]) island_count = 0 def dfs(row, col): // Base case: out of bounds or water if (row < 0 or row >= rows or col < 0 or col >= cols or grid[row][col] == '0'): return // Mark as visited by changing to water grid[row][col] = '0' // Explore all 4 directions dfs(row - 1, col) // Up dfs(row + 1, col) // Down dfs(row, col - 1) // Left dfs(row, col + 1) // Right for row in range(rows): for col in range(cols): if grid[row][col] == '1': island_count += 1 dfs(row, col) // Explore and mark entire island return island_count // Example:grid = [ ['1', '1', '0', '0', '0'], ['1', '1', '0', '0', '0'], ['0', '0', '1', '0', '0'], ['0', '0', '0', '1', '1']]print(count_islands(grid)) // 3 islandsVariations of Island Problems:
| Problem | Description | Key Modification |
|---|---|---|
| Max Island Size | Find the largest island | Track size during DFS, return max |
| Perimeter | Calculate island boundary length | Count edges adjacent to water/boundary |
| 8-directional Islands | Diagonals count as connected | Use 8-direction neighbor check |
| Distinct Islands | Count unique island shapes | Normalize and hash island patterns |
| Surrounded Regions | Convert surrounded O's to X's | Mark border-connected first, then flip |
| Making Islands Connected | Min 0→1 changes to connect | BFS from each island to find distances |
In the solution above, we mark cells as visited by changing '1' to '0'. This modifies the input. If you need to preserve the original grid, use a separate visited set or matrix. The trade-off is O(m×n) extra space for the visited tracking.
While full matrix multiplication is often left to specialized libraries, understanding the concept is essential for DSA interviews and for grasping algorithms that build on it.
The Rule:
For matrices A (m×k) and B (k×n), the product C = A × B is an m×n matrix where:
Matrix A (2×3): Matrix B (3×2):┌─────┬─────┬─────┐ ┌─────┬─────┐│ 1 │ 2 │ 3 │ × │ 7 │ 8 │├─────┼─────┼─────┤ ├─────┼─────┤│ 4 │ 5 │ 6 │ │ 9 │ 10 │└─────┴─────┴─────┘ ├─────┼─────┤ │ 11 │ 12 │ └─────┴─────┘ Result C (2×2):C[0][0] = 1×7 + 2×9 + 3×11 = 7 + 18 + 33 = 58C[0][1] = 1×8 + 2×10 + 3×12 = 8 + 20 + 36 = 64C[1][0] = 4×7 + 5×9 + 6×11 = 28 + 45 + 66 = 139C[1][1] = 4×8 + 5×10 + 6×12 = 32 + 50 + 72 = 154 ┌─────┬─────┐│ 58 │ 64 │├─────┼─────┤│ 139 │ 154 │└─────┴─────┘123456789101112131415161718192021222324
def matrix_multiply(A, B): """ Naive matrix multiplication. A is m×k, B is k×n, result is m×n. Time: O(m × n × k), Space: O(m × n) for result """ m = len(A) k = len(A[0]) // = len(B) n = len(B[0]) // Initialize result with zeros C = [[0 for _ in range(n)] for _ in range(m)] // Compute each element for i in range(m): for j in range(n): for p in range(k): C[i][j] += A[i][p] * B[p][j] return C // Note: For performance, consider loop order!// The above order (i, j, p) is not cache-optimal.// Better: (i, p, j) for row-major storageIn practice, use optimized libraries like NumPy, BLAS, or GPU-accelerated libraries for matrix multiplication. These employ advanced techniques (blocking, SIMD, parallelism) that can be 100-1000x faster than naive implementations. Understanding the algorithm helps you reason about complexity and debug issues.
Let's consolidate the major patterns you'll encounter in matrix problems:
| Pattern | Example Problems | Key Technique |
|---|---|---|
| Traversal | Print matrix, sum elements | Nested loops, boundary management |
| Search | Find element, find path | Row+col sorted → staircase; Grid → BFS/DFS |
| Transformation | Rotate, transpose, flip | In-place swaps, composition of simpler ops |
| Connected Components | Count islands, fill regions | DFS/BFS flood fill, union-find |
| Path Finding | Shortest path in grid | BFS for unweighted, Dijkstra for weighted |
| Dynamic Programming | Unique paths, min path sum | DP table same shape as grid |
| Simulation | Game of Life, water flow | State tracking, neighbor checks |
| Boundary Conditions | Edge detection, border ops | Special handling for first/last row/col |
Quick Reference: Common Matrix DP Problems:
123456789101112131415161718192021222324252627282930313233
// Pattern: Grid DP with accumulation// Example: Minimum Path Sum def min_path_sum(grid): """Find path from top-left to bottom-right with minimum sum.""" rows, cols = len(grid), len(grid[0]) // DP in-place: grid[i][j] = min cost to reach (i,j) for i in range(rows): for j in range(cols): if i == 0 and j == 0: continue // Starting point elif i == 0: grid[i][j] += grid[i][j-1] // Can only come from left elif j == 0: grid[i][j] += grid[i-1][j] // Can only come from above else: grid[i][j] += min(grid[i-1][j], grid[i][j-1]) return grid[rows-1][cols-1] // Pattern: Grid DP with counting// Example: Unique Paths def unique_paths(m, n): """Count paths from top-left to bottom-right (only right/down moves).""" dp = [[1] * n for _ in range(m)] // First row and col are all 1s for i in range(1, m): for j in range(1, n): dp[i][j] = dp[i-1][j] + dp[i][j-1] return dp[m-1][n-1]Ask: (1) Is this a search problem? → Consider BFS/DFS. (2) Does it ask for count/min/max with subproblem structure? → Consider DP. (3) Does it involve connected regions? → Consider flood fill or union-find. (4) Is it a transformation? → Consider in-place operations with careful swap ordering.
Module Complete:
Congratulations! You've now mastered multi-dimensional arrays from conceptual understanding through practical operations. You understand how 2D arrays model tabular data, how they're stored in memory, how to traverse them efficiently, and how to apply the common operations that appear throughout algorithm problems.
This foundation prepares you for more advanced topics: graph algorithms (where adjacency matrices are a key representation), dynamic programming on grids, image processing algorithms, and game development. The matrix intuition you've built will serve you throughout your computing career.
You've completed Module 9: Multi-Dimensional Arrays. You now possess a comprehensive toolkit for working with matrices—from understanding their memory layout to implementing transformations and solving classic problems. These skills extend your 1D array mastery into the rich world of grid-based computation.