Managing Matrix Operations
1. Implementing Matrix Traversal
Example: Spiral Matrix Traversal
function spiralOrder(matrix) {
if (!matrix || matrix.length === 0 || matrix[0].length === 0) return [];
const result = [];
let top = 0;
let bottom = matrix.length - 1;
let left = 0;
let right = matrix[0].length - 1;
while (top <= bottom && left <= right) {
// Traverse right
for (let i = left; i <= right; i++) {
result.push(matrix[top][i]);
}
top++;
// Traverse down
for (let i = top; i <= bottom; i++) {
result.push(matrix[i][right]);
}
right--;
// Traverse left (if row still exists)
if (top <= bottom) {
for (let i = right; i >= left; i--) {
result.push(matrix[bottom][i]);
}
bottom--;
}
// Traverse up (if column still exists)
if (left <= right) {
for (let i = bottom; i >= top; i--) {
result.push(matrix[i][left]);
}
left++;
}
}
return result;
}
// Example usage:
const matrix = [
[1, 2, 3],
[4, 5, 6],
[7, 8, 9]
];
console.log(spiralOrder(matrix)); // [1, 2, 3, 6, 9, 8, 7, 4, 5]
| Traversal Type | Description | Time Complexity | Space Complexity |
|---|---|---|---|
| Spiral Order | Traverses elements in a spiral pattern starting from top-left | O(m * n) |
O(1) (excluding output array) |
| Row-wise | Traverses elements row by row from left to right | O(m * n) |
O(1) |
| Column-wise | Traverses elements column by column from top to bottom | O(m * n) |
O(1) |
| Diagonal | Traverses elements along diagonals (top-left to bottom-right) | O(m * n) |
O(1) |
Note: Spiral traversal requires careful boundary management to avoid revisiting elements.
Example: Diagonal Matrix Traversal
function diagonalTraversal(matrix) {
const result = [];
const rows = matrix.length;
const cols = matrix[0].length;
for (let d = 0; d < rows + cols - 1; d++) {
const temp = [];
let r, c;
if (d < cols) {
r = 0;
c = d;
} else {
r = d - cols + 1;
c = cols - 1;
}
while (r < rows && c >= 0) {
temp.push(matrix[r][c]);
r++;
c--;
}
if (d % 2 === 0) {
result.push(...temp.reverse());
} else {
result.push(...temp);
}
}
return result;
}
// Example usage:
const matrix2 = [
[1, 2, 3],
[4, 5, 6],
[7, 8, 9]
];
console.log(diagonalTraversal(matrix2)); // [1, 2, 4, 7, 5, 3, 6, 8, 9]
2. Rotating Matrix 90 Degrees
| Operation | Description | Time Complexity | Space Complexity |
|---|---|---|---|
| In-Place Rotation | Rotate matrix 90 degrees clockwise by transposing and reversing rows | O(n²) |
O(1) |
| New Matrix | Create a new matrix with rotated elements | O(n²) |
O(n²) |
Example: In-Place 90° Clockwise Rotation
function rotateMatrix(matrix) {
const n = matrix.length;
// Transpose the matrix
for (let i = 0; i < n; i++) {
for (let j = i + 1; j < n; j++) {
[matrix[i][j], matrix[j][i]] = [matrix[j][i], matrix[i][j]];
}
}
// Reverse each row
for (let i = 0; i < n; i++) {
matrix[i].reverse();
}
}
// Example usage:
const matrix = [
[1, 2, 3],
[4, 5, 6],
[7, 8, 9]
];
rotateMatrix(matrix);
console.log(matrix);
// Output:
// [
// [7, 4, 1],
// [8, 5, 2],
// [9, 6, 3]
// ]
Example: New Matrix 90° Clockwise Rotation
function rotateMatrixNew(matrix) {
const n = matrix.length;
const rotated = Array(n).fill().map(() => Array(n).fill(0));
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
rotated[j][n - 1 - i] = matrix[i][j];
}
}
return rotated;
}
// Example usage:
const matrix = [
[1, 2, 3],
[4, 5, 6],
[7, 8, 9]
];
const rotated = rotateMatrixNew(matrix);
console.log(rotated);
// Output:
// [
// [7, 4, 1],
// [8, 5, 2],
// [9, 6, 3]
// ]
3. Implementing Spiral Matrix Traversal
| Operation | Description | Time Complexity | Space Complexity |
|---|---|---|---|
| Spiral Traversal | Traverses matrix elements in spiral order starting from top-left | O(m*n) |
O(1) |
Example: Spiral Matrix Traversal
function spiralOrder(matrix) {
if (!matrix || matrix.length === 0 || matrix[0].length === 0) return [];
const result = [];
let top = 0;
let bottom = matrix.length - 1;
let left = 0;
let right = matrix[0].length - 1;
while (top <= bottom && left <= right) {
// Traverse right
for (let i = left; i <= right; i++) {
result.push(matrix[top][i]);
}
top++;
// Traverse down
for (let i = top; i <= bottom; i++) {
result.push(matrix[i][right]);
}
right--;
// Traverse left (if row still exists)
if (top <= bottom) {
for (let i = right; i >= left; i--) {
result.push(matrix[bottom][i]);
}
bottom--;
}
// Traverse up (if column still exists)
if (left <= right) {
for (let i = bottom; i >= top; i--) {
result.push(matrix[i][left]);
}
left++;
}
}
return result;
}
// Example usage:
const matrix = [
[1, 2, 3],
[4, 5, 6],
[7, 8, 9]
];
console.log(spiralOrder(matrix)); // [1, 2, 3, 6, 9, 8, 7, 4, 5]
Note: Spiral traversal works for both square and rectangular matrices.
4. Setting Matrix Zeros
When working with matrices, setting all elements to zero is a common operation. This can be achieved through various methods depending on the programming language or library being used.
| Method | Description | Code Example |
|---|---|---|
| Manual Initialization | Initialize a matrix with all zeros using nested loops. | |
| Using Array.fill() | Use the fill method to initialize a matrix with zeros. |
let matrix = Array(rows).fill().map(() => Array(cols).fill(0)); |
| Using Math.js | Utilize the zeros function from the Math.js library. |
const matrix = math.zeros(rows, cols); |
Note: The choice of method depends on the specific requirements and performance considerations of your application.
5. Searching in Row-Column Sorted Matrix
Searching in a row-column sorted matrix involves finding an element in a matrix where each row and column is sorted in ascending order. The key insight is to leverage the sorted property to eliminate search space efficiently.
| Approach | Description | Time Complexity | Space Complexity |
|---|---|---|---|
| Start from Top-Right Corner | Begin at the top-right element. If target is less than current, move left. If target is greater, move down. | O(m + n) |
O(1) |
| Start from Bottom-Left Corner | Begin at the bottom-left element. If target is less than current, move up. If target is greater, move right. | O(m + n) |
O(1) |
Example: Searching in Row-Column Sorted Matrix
function searchMatrix(matrix, target) {
if (!matrix || matrix.length === 0 || matrix[0].length === 0) return false;
let row = 0;
let col = matrix[0].length - 1;
while (row < matrix.length && col >= 0) {
if (matrix[row][col] === target) return true;
else if (matrix[row][col] > target) col--;
else row++;
}
return false;
}
// Example usage:
const matrix = [
[1, 4, 7, 11],
[2, 5, 8, 12],
[3, 6, 9, 16],
[10, 13, 14, 17]
];
console.log(searchMatrix(matrix, 5)); // true
console.log(searchMatrix(matrix, 15)); // false
Note: This approach works because the matrix is sorted both row-wise and column-wise. Starting from top-right or bottom-left ensures that we can eliminate either a row or a column in each step.
6. Finding Diagonal Traverse
| Property | Description | Example |
|---|---|---|
| matrix | Input 2D array representing the matrix | [[1, 2, 3], [4, 5, 6], [7, 8, 9]] |
| direction | Traversal direction: 0 for top-left to bottom-right, 1 for bottom-right to top-left | 0 |
Example: Traverse Matrix Diagonally
function diagonalTraverse(matrix) {
if (!matrix || matrix.length === 0 || matrix[0].length === 0) return [];
const result = [];
const rows = matrix.length;
const cols = matrix[0].length;
for (let d = 0; d < rows + cols - 1; d++) {
const temp = [];
let r = d < cols ? 0 : d - cols + 1;
let c = d < cols ? d : cols - 1;
while (r < rows && c >= 0) {
temp.push(matrix[r][c]);
r++;
c--;
}
if (d % 2 === 0) {
result.push(...temp.reverse());
} else {
result.push(...temp);
}
}
return result;
}
const matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]];
console.log(diagonalTraverse(matrix)); // [1, 2, 4, 7, 5, 3, 6, 8, 9]
7. Transposing Matrix
| Operation | Description | Time Complexity | Space Complexity |
|---|---|---|---|
| Transpose | Convert rows to columns and vice versa | O(m × n) |
O(m × n) |
Example: Transpose a 3x3 Matrix
const matrix = [
[1, 2, 3],
[4, 5, 6],
[7, 8, 9]
];
const transposed = matrix[0].map((_, colIndex) =>
matrix.map(row => row[colIndex])
);
console.log(transposed);
// Output:
// [
// [1, 4, 7],
// [2, 5, 8],
// [3, 6, 9]
// ]
Note: For in-place transpose of square matrices, use a nested loop to swap elements at
(i, j) and (j, i).
8. Finding Kth Smallest in Sorted Matrix
| Approach | Description | Time Complexity | Space Complexity |
|---|---|---|---|
| Binary Search on Values | Use binary search to find the kth smallest element by counting elements <= mid in each row | O(m * n * log(max - min)) |
O(1) |
| Min-Heap (Priority Queue) | Start with top-left element, keep extracting min and adding neighbors | O(k * log(min(m,n))) |
O(min(m,n)) |
Example: Binary Search Approach
function kthSmallest(matrix, k) {
const m = matrix.length;
const n = matrix[0].length;
let left = matrix[0][0];
let right = matrix[m - 1][n - 1];
function countLessOrEqual(target) {
let count = 0;
let j = n - 1;
for (let i = 0; i < m; i++) {
while (j >= 0 && matrix[i][j] > target) j--;
count += j + 1;
}
return count;
}
while (left < right) {
const mid = Math.floor((left + right) / 2);
const count = countLessOrEqual(mid);
if (count < k) left = mid + 1;
else right = mid;
}
return left;
}
// Example usage:
const matrix = [
[1, 5, 9],
[10, 11, 13],
[12, 13, 15]
];
console.log(kthSmallest(matrix, 8)); // Output: 13Example: Min-Heap Approach
function kthSmallest(matrix, k) {
const m = matrix.length;
const n = matrix[0].length;
// Min-heap to store [value, row, col]
const minHeap = new MinHeap();
const visited = Array(m).fill().map(() => Array(n).fill(false));
minHeap.push([matrix[0][0], 0, 0]);
visited[0][0] = true;
for (let i = 0; i < k; i++) {
const [val, row, col] = minHeap.pop();
if (row + 1 < m && !visited[row + 1][col]) {
minHeap.push([matrix[row + 1][col], row + 1, col]);
visited[row + 1][col] = true;
}
if (col + 1 < n && !visited[row][col + 1]) {
minHeap.push([matrix[row][col + 1], row, col + 1]);
visited[row][col + 1] = true;
}
}
return minHeap.peek()[0];
}
// Example usage:
const matrix = [
[1, 5, 9],
[10, 11, 13],
[12, 13, 15]
];
console.log(kthSmallest(matrix, 8)); // Output: 13
Note: The binary search approach is more efficient for large matrices, while the heap approach is simpler to understand and implement.
9. Implementing Matrix Multiplication
| Operation | Description | Time Complexity | Space Complexity |
|---|---|---|---|
| Standard Multiplication | Multiplies two matrices by computing dot products of rows and columns. | O(n³) |
O(n²) |
| Strassen's Algorithm | Divide-and-conquer approach reducing time complexity to O(n^2.807). |
O(n^2.807) |
O(n²) |
| Simplified Loop | Naive triple nested loop implementation for clarity. | O(n³) |
O(n²) |
Example: Standard Matrix Multiplication
function multiplyMatrices(A, B) {
const rowsA = A.length;
const colsA = A[0].length;
const colsB = B[0].length;
const result = Array(rowsA)
.fill()
.map(() => Array(colsB).fill(0));
for (let i = 0; i < rowsA; i++) {
for (let j = 0; j < colsB; j++) {
for (let k = 0; k < colsA; k++) {
result[i][j] += A[i][k] * B[k][j];
}
}
}
return result;
}
// Example usage:
const A = [[1, 2], [3, 4]];
const B = [[5, 6], [7, 8]];
console.log(multiplyMatrices(A, B)); // [[19, 22], [43, 50]]
Example: Strassen's Matrix Multiplication
function strassenMultiply(A, B) {
const n = A.length;
// Base case for small matrices
if (n <= 2) {
return multiplyMatrices(A, B);
}
const mid = Math.floor(n / 2);
// Partition matrices into quadrants
const A11 = A.slice(0, mid).map(row => row.slice(0, mid));
const A12 = A.slice(0, mid).map(row => row.slice(mid));
const A21 = A.slice(mid).map(row => row.slice(0, mid));
const A22 = A.slice(mid).map(row => row.slice(mid));
const B11 = B.slice(0, mid).map(row => row.slice(0, mid));
const B12 = B.slice(0, mid).map(row => row.slice(mid));
const B21 = B.slice(mid).map(row => row.slice(0, mid));
const B22 = B.slice(mid).map(row => row.slice(mid));
// Strassen's recurrence relations
const M1 = strassenMultiply(addMatrices(A11, A22), addMatrices(B11, B22));
const M2 = strassenMultiply(addMatrices(A21, A22), B11);
const M3 = strassenMultiply(A11, subtractMatrices(B12, B22));
const M4 = strassenMultiply(A22, subtractMatrices(B21, B11));
const M5 = strassenMultiply(addMatrices(A11, A12), B22);
const M6 = strassenMultiply(subtractMatrices(A21, A11), addMatrices(B11, B12));
const M7 = strassenMultiply(subtractMatrices(A12, A22), addMatrices(B21, B22));
// Combine results
const C11 = addMatrices(subtractMatrices(addMatrices(M1, M4), M5), M7);
const C12 = addMatrices(M3, M5);
const C21 = addMatrices(M2, M4);
const C22 = addMatrices(subtractMatrices(addMatrices(M1, M3), M2), M6);
// Reassemble the result matrix
const result = [];
for (let i = 0; i < mid; i++) {
result.push([...C11[i], ...C12[i]]);
}
for (let i = 0; i < mid; i++) {
result.push([...C21[i], ...C22[i]]);
}
return result;
}
function addMatrices(A, B) {
return A.map((row, i) => row.map((val, j) => val + B[i][j]));
}
function subtractMatrices(A, B) {
return A.map((row, i) => row.map((val, j) => val - B[i][j]));
}
Note: Strassen's algorithm is more efficient for large matrices but has higher constant factors and is less stable numerically than standard multiplication.
10. Finding Number of Islands
Given a 2D binary grid representing land (1) and water (0), find the number of distinct islands. An island is a group of connected 1s that are connected horizontally or vertically.
| Property | Description | Example |
|---|---|---|
| Input | 2D binary grid of size m x n |
|
| Output | Integer representing number of islands | 1 |
Example: Counting Islands
function numIslands(grid) {
if (!grid || grid.length === 0) return 0;
let count = 0;
const rows = grid.length;
const cols = grid[0].length;
for (let i = 0; i < rows; i++) {
for (let j = 0; j < cols; j++) {
if (grid[i][j] === "1") {
count++;
dfs(grid, i, j);
}
}
}
return count;
}
function dfs(grid, row, col) {
const rows = grid.length;
const cols = grid[0].length;
if (row < 0 || row >= rows || col < 0 || col >= cols || grid[row][col] === "0") {
return;
}
grid[row][col] = "0"; // Mark as visited
dfs(grid, row + 1, col); // Down
dfs(grid, row - 1, col); // Up
dfs(grid, row, col + 1); // Right
dfs(grid, row, col - 1); // Left
}
Note: The DFS approach modifies the input grid to mark visited cells. For a non-destructive solution, use a separate boolean matrix or set to track visited cells.
11. Solving Word Search II
Given a 2D board and a list of words from the dictionary, return all words in the board. Each word must be constructed from letters of sequentially adjacent cells, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.
| Property | Description | Notes |
|---|---|---|
| board | 2D character grid representing the board | Each cell contains a single character |
| words | List of words to search for | Words can be of any length |
Example:
const board = [
['A', 'B', 'C', 'E'],
['S', 'F', 'C', 'S'],
['A', 'D', 'E', 'E']
];
const words = ['ABCCED', 'SFCS', 'ABCB'];
// Output: ['ABCCED', 'SFCS']
Solution Approach:
- Build a Trie data structure to efficiently store and search words
- For each cell in the board, initiate a DFS traversal if the character matches the root of the Trie
- During DFS, maintain a path and check if any prefix exists in the Trie
- If a complete word is found, add it to the result set
- Backtrack by marking visited cells and restoring them after traversal
Note: The solution uses a Trie to optimize prefix lookups and DFS with backtracking to explore all valid paths.
12. Finding Largest Rectangle
| Property | Description | Notes |
|---|---|---|
| matrix | 2D binary matrix of 0s and 1s | Input grid to analyze |
| maxArea | Maximum area of rectangle containing only 1s | Result to compute |
Example: Find Largest Rectangle in Binary Matrix
function maximalRectangle(matrix) {
if (!matrix || matrix.length === 0 || matrix[0].length === 0) return 0;
const rows = matrix.length;
const cols = matrix[0].length;
const heights = new Array(cols).fill(0);
let maxArea = 0;
for (let i = 0; i < rows; i++) {
for (let j = 0; j < cols; j++) {
heights[j] = matrix[i][j] === '1' ? heights[j] + 1 : 0;
}
maxArea = Math.max(maxArea, largestRectangleInHistogram(heights));
}
return maxArea;
}
function largestRectangleInHistogram(heights) {
const stack = [];
let maxArea = 0;
for (let i = 0; i <= heights.length; i++) {
while (stack.length && (i === heights.length || heights[stack[stack.length - 1]] > heights[i])) {
const h = heights[stack.pop()];
const w = stack.length === 0 ? i : i - stack[stack.length - 1] - 1;
maxArea = Math.max(maxArea, h * w);
}
stack.push(i);
}
return maxArea;
}
// Example usage:
const matrix = [
['1', '0', '1', '0', '0'],
['1', '0', '1', '1', '1'],
['1', '1', '1', '1', '1'],
['1', '0', '0', '1', '0']
];
console.log(maximalRectangle(matrix)); // Output: 6
Note: This algorithm uses a combination of histogram-based approach and stack to efficiently compute the largest rectangle in O(mn) time where m is rows and n is columns.