Matrix Traversal

1. Spiral Traversal Four Directions

Technique	Pattern	Boundary Management	Application
Layer-by-Layer	Process outer layer, then inner recursively	Track top, bottom, left, right boundaries	Spiral matrix traversal
Direction Array	`dirs = [[0,1], [1,0], [0,-1], [-1,0]]`	Right → Down → Left → Up cycle	Clockwise spiral movement
Visited Tracking	Mark cells as visited or use boundaries	Prevent revisiting cells	When cannot modify matrix
Shrinking Bounds	Adjust boundaries after each direction	top++, right--, bottom--, left++	Memory efficient approach

Example: Spiral Matrix Traversal

function spiralOrder(matrix) {
  if (!matrix.length) return [];
  
  const result = [];
  let top = 0, bottom = matrix.length - 1;
  let left = 0, right = matrix[0].length - 1;
  
  while (top <= bottom && left <= right) {
    // Move right along top row
    for (let col = left; col <= right; col++) {
      result.push(matrix[top][col]);
    }
    top++;
    
    // Move down along right column
    for (let row = top; row <= bottom; row++) {
      result.push(matrix[row][right]);
    }
    right--;
    
    // Move left along bottom row (if row exists)
    if (top <= bottom) {
      for (let col = right; col >= left; col--) {
        result.push(matrix[bottom][col]);
      }
      bottom--;
    }
    
    // Move up along left column (if column exists)
    if (left <= right) {
      for (let row = bottom; row >= top; row--) {
        result.push(matrix[row][left]);
      }
      left++;
    }
  }
  
  return result;
}

const matrix = [
  [1, 2, 3, 4],
  [5, 6, 7, 8],
  [9, 10, 11, 12]
];
console.log(spiralOrder(matrix));
// [1,2,3,4,8,12,11,10,9,5,6,7]

Example: Generate Spiral Matrix

function generateMatrix(n) {
  const matrix = Array(n).fill(null).map(() => Array(n).fill(0));
  
  let num = 1;
  let top = 0, bottom = n - 1;
  let left = 0, right = n - 1;
  
  while (top <= bottom && left <= right) {
    // Fill top row
    for (let col = left; col <= right; col++) {
      matrix[top][col] = num++;
    }
    top++;
    
    // Fill right column
    for (let row = top; row <= bottom; row++) {
      matrix[row][right] = num++;
    }
    right--;
    
    // Fill bottom row
    for (let col = right; col >= left; col--) {
      matrix[bottom][col] = num++;
    }
    bottom--;
    
    // Fill left column
    for (let row = bottom; row >= top; row--) {
      matrix[row][left] = num++;
    }
    left++;
  }
  
  return matrix;
}

console.log(generateMatrix(3));
// [[1,2,3],
//  [8,9,4],
//  [7,6,5]]

Note: For spiral traversal, always check boundary conditions before the bottom-left and left-up movements to avoid duplicate elements in non-square matrices.

2. Search in Sorted Matrix Stairs

Matrix Type	Strategy	Starting Point	Time Complexity
Row & Column Sorted	Staircase search from top-right or bottom-left	Top-right: go left if target < current, down if >	`O(m + n)`
Fully Sorted	Binary search treating as 1D array	Map 1D index to 2D: `[mid/n][mid%n]`	`O(log(m*n))`
Each Row Sorted	Binary search on each row	Find valid row range, then binary search	`O(m log n)`

Example: Search in Row and Column Sorted Matrix

function searchMatrix(matrix, target) {
  if (!matrix.length || !matrix[0].length) return false;
  
  const m = matrix.length;
  const n = matrix[0].length;
  
  // Start from top-right corner
  let row = 0;
  let col = n - 1;
  
  while (row < m && col >= 0) {
    if (matrix[row][col] === target) {
      return true;
    } else if (matrix[row][col] > target) {
      col--; // Move left
    } else {
      row++; // Move down
    }
  }
  
  return false;
}

const matrix = [
  [1,  4,  7,  11, 15],
  [2,  5,  8,  12, 19],
  [3,  6,  9,  16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30]
];
console.log(searchMatrix(matrix, 5)); // true
console.log(searchMatrix(matrix, 20)); // false

// Why top-right works:
// - Smallest in column (can only go down)
// - Largest in row (can only go left)
// - Eliminates entire row or column each step

Example: Search in Fully Sorted Matrix (2D Binary Search)

function searchMatrixFullySorted(matrix, target) {
  if (!matrix.length || !matrix[0].length) return false;
  
  const m = matrix.length;
  const n = matrix[0].length;
  let left = 0;
  let right = m * n - 1;
  
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    
    // Convert 1D index to 2D coordinates
    const row = Math.floor(mid / n);
    const col = mid % n;
    const midValue = matrix[row][col];
    
    if (midValue === target) {
      return true;
    } else if (midValue < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
  
  return false;
}

// Matrix where each row's first element > previous row's last
const sortedMatrix = [
  [1,  3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 60]
];
console.log(searchMatrixFullySorted(sortedMatrix, 3)); // true

Staircase Search Visualization

Start at top-right [0,4]:
[1,  4,  7,  11, 15*]
[2,  5,  8,  12, 19]
[3,  6,  9,  16, 22]
Target=5, 15>5 → move left

At [0,3]:
[1,  4,  7,  11*, 15]
Target=5, 11>5 → move left

At [0,2]:
[1,  4,  7*, 11, 15]
Target=5, 7>5 → move left

At [0,1]:
[1,  4*, 7,  11, 15]
Target=5, 4<5 → move down

At [1,1]:
[1,  4,  7,  11, 15]
[2,  5*, 8,  12, 19]
Found!

Note: Staircase Search Invariant

All elements to the right are larger
All elements below are larger
Can eliminate entire row or column per step
Works from top-right OR bottom-left

3. Island Counting DFS BFS

Approach	Strategy	Marking Technique	Space
DFS Recursive	Explore island fully before next	Mark visited as '0' or use visited set	`O(m*n)` stack
BFS Queue	Level-by-level exploration	Queue for current island cells	`O(min(m,n))`
Union Find	Connect adjacent land cells	Count connected components	`O(m*n)`
In-place Marking	Modify input to mark visited	Change '1' to '0' or '#'	`O(1)` extra

Example: Number of Islands (DFS)

function numIslands(grid) {
  if (!grid.length || !grid[0].length) return 0;
  
  const m = grid.length;
  const n = grid[0].length;
  let count = 0;
  
  function dfs(row, col) {
    // Base cases: out of bounds or water
    if (row < 0 || row >= m || col < 0 || col >= n || grid[row][col] === '0') {
      return;
    }
    
    // Mark as visited
    grid[row][col] = '0';
    
    // Explore 4 directions
    dfs(row + 1, col); // Down
    dfs(row - 1, col); // Up
    dfs(row, col + 1); // Right
    dfs(row, col - 1); // Left
  }
  
  for (let row = 0; row < m; row++) {
    for (let col = 0; col < n; col++) {
      if (grid[row][col] === '1') {
        count++;
        dfs(row, col); // Sink entire island
      }
    }
  }
  
  return count;
}

const grid = [
  ['1','1','0','0','0'],
  ['1','1','0','0','0'],
  ['0','0','1','0','0'],
  ['0','0','0','1','1']
];
console.log(numIslands(grid)); // 3

Example: Number of Islands (BFS)

function numIslandsBFS(grid) {
  if (!grid.length || !grid[0].length) return 0;
  
  const m = grid.length;
  const n = grid[0].length;
  let count = 0;
  const directions = [[0,1], [1,0], [0,-1], [-1,0]];
  
  function bfs(startRow, startCol) {
    const queue = [[startRow, startCol]];
    grid[startRow][startCol] = '0';
    
    while (queue.length) {
      const [row, col] = queue.shift();
      
      for (const [dr, dc] of directions) {
        const newRow = row + dr;
        const newCol = col + dc;
        
        if (newRow >= 0 && newRow < m && 
            newCol >= 0 && newCol < n && 
            grid[newRow][newCol] === '1') {
          
          grid[newRow][newCol] = '0';
          queue.push([newRow, newCol]);
        }
      }
    }
  }
  
  for (let row = 0; row < m; row++) {
    for (let col = 0; col < n; col++) {
      if (grid[row][col] === '1') {
        count++;
        bfs(row, col);
      }
    }
  }
  
  return count;
}

// Alternative: Use deque for better performance
// queue.shift() is O(n), use index pointer or actual Queue

Example: Max Area of Island

function maxAreaOfIsland(grid) {
  const m = grid.length;
  const n = grid[0].length;
  let maxArea = 0;
  
  function dfs(row, col) {
    if (row < 0 || row >= m || col < 0 || col >= n || grid[row][col] === 0) {
      return 0;
    }
    
    grid[row][col] = 0; // Mark visited
    
    // Count current cell + all connected cells
    return 1 + 
           dfs(row + 1, col) +
           dfs(row - 1, col) +
           dfs(row, col + 1) +
           dfs(row, col - 1);
  }
  
  for (let row = 0; row < m; row++) {
    for (let col = 0; col < n; col++) {
      if (grid[row][col] === 1) {
        const area = dfs(row, col);
        maxArea = Math.max(maxArea, area);
      }
    }
  }
  
  return maxArea;
}

const islandGrid = [
  [0,0,1,0,0,0,0,1,0,0,0,0,0],
  [0,0,0,0,0,0,0,1,1,1,0,0,0],
  [0,1,1,0,1,0,0,0,0,0,0,0,0],
  [0,1,0,0,1,1,0,0,1,0,1,0,0],
  [0,1,0,0,1,1,0,0,1,1,1,0,0],
  [0,0,0,0,0,0,0,0,0,0,1,0,0]
];
console.log(maxAreaOfIsland(islandGrid)); // 6

Note: When counting islands, you can either use in-place modification (change grid values) or maintain a separate visited set. In-place is O(1) space but modifies input; visited set is O(m*n) space but preserves input.

4. Rotating Matrix In-place

Rotation	Strategy	Steps	Space
90° Clockwise	Transpose + Reverse each row	Swap [i][j] ↔ [j][i], then reverse rows	`O(1)`
90° Counter-Clockwise	Transpose + Reverse each column	Swap [i][j] ↔ [j][i], then reverse columns	`O(1)`
180°	Reverse rows + Reverse each row	Or apply 90° twice	`O(1)`
Layer by Layer	Rotate outer layers to inner	Four-way swap in concentric squares	`O(1)`

Example: Rotate Matrix 90° Clockwise

function rotate90Clockwise(matrix) {
  const n = matrix.length;
  
  // Step 1: Transpose (swap across diagonal)
  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]];
    }
  }
  
  // Step 2: Reverse each row
  for (let i = 0; i < n; i++) {
    matrix[i].reverse();
  }
}

const mat1 = [
  [1, 2, 3],
  [4, 5, 6],
  [7, 8, 9]
];
rotate90Clockwise(mat1);
console.log(mat1);
// [[7, 4, 1],
//  [8, 5, 2],
//  [9, 6, 3]]

// Visualization:
// Original:     Transpose:    Reverse rows:
// 1 2 3         1 4 7         7 4 1
// 4 5 6    →    2 5 8    →    8 5 2
// 7 8 9         3 6 9         9 6 3

Example: Rotate 90° Counter-Clockwise

function rotate90CounterClockwise(matrix) {
  const n = matrix.length;
  
  // Step 1: Transpose
  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]];
    }
  }
  
  // Step 2: Reverse each column (reverse the array of rows)
  matrix.reverse();
}

// Alternative: Reverse rows first, then transpose
function rotate90CounterClockwiseAlt(matrix) {
  const n = matrix.length;
  
  // Reverse rows (flip vertically)
  matrix.reverse();
  
  // Transpose
  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]];
    }
  }
}

Example: Layer-by-Layer Rotation

function rotateLayerByLayer(matrix) {
  const n = matrix.length;
  
  // Process concentric layers
  for (let layer = 0; layer < Math.floor(n / 2); layer++) {
    const first = layer;
    const last = n - 1 - layer;
    
    for (let i = first; i < last; i++) {
      const offset = i - first;
      
      // Save top
      const top = matrix[first][i];
      
      // Left → Top
      matrix[first][i] = matrix[last - offset][first];
      
      // Bottom → Left
      matrix[last - offset][first] = matrix[last][last - offset];
      
      // Right → Bottom
      matrix[last][last - offset] = matrix[i][last];
      
      // Top → Right
      matrix[i][last] = top;
    }
  }
}

const mat2 = [
  [1,  2,  3,  4],
  [5,  6,  7,  8],
  [9,  10, 11, 12],
  [13, 14, 15, 16]
];
rotateLayerByLayer(mat2);
console.log(mat2);
// [[13, 9,  5, 1],
//  [14, 10, 6, 2],
//  [15, 11, 7, 3],
//  [16, 12, 8, 4]]

Rotation Formulas

90° CW: [i][j] → [j][n-1-i]
90° CCW: [i][j] → [n-1-j][i]
180°: [i][j] → [n-1-i][n-1-j]
Transpose: [i][j] ↔ [j][i]
Flip Horizontal: [i][j] ↔ [i][n-1-j]
Flip Vertical: [i][j] ↔ [n-1-i][j]

Note: Rotation Strategies

Transpose + Reverse: Simple, easy to remember
Layer by Layer: Direct rotation, good for understanding
Formula: Calculate new position directly
All are O(n²) time, O(1) space

5. Shortest Path in Grid A*

Algorithm	Strategy	Use Case	Time
BFS	Explore level-by-level, unweighted edges	Shortest path in unweighted grid	`O(m*n)`
Dijkstra	Priority queue, weighted edges	Shortest path with edge weights	`O(mnlog(m*n))`
A* Search	Dijkstra + heuristic (Manhattan distance)	Faster path finding with goal knowledge	`O(b^d)` optimal
Bidirectional BFS	Search from both start and end	Reduce search space by half	`O(b^(d/2))`

Example: Shortest Path in Binary Grid (BFS)

function shortestPathBinaryMatrix(grid) {
  const n = grid.length;
  
  // Check if start or end is blocked
  if (grid[0][0] === 1 || grid[n-1][n-1] === 1) return -1;
  
  // 8 directions (including diagonals)
  const dirs = [
    [-1,-1], [-1,0], [-1,1],
    [0,-1],          [0,1],
    [1,-1],  [1,0],  [1,1]
  ];
  
  const queue = [[0, 0, 1]]; // [row, col, distance]
  grid[0][0] = 1; // Mark visited
  
  while (queue.length) {
    const [row, col, dist] = queue.shift();
    
    // Reached destination
    if (row === n - 1 && col === n - 1) {
      return dist;
    }
    
    for (const [dr, dc] of dirs) {
      const newRow = row + dr;
      const newCol = col + dc;
      
      if (newRow >= 0 && newRow < n &&
          newCol >= 0 && newCol < n &&
          grid[newRow][newCol] === 0) {
        
        grid[newRow][newCol] = 1; // Mark visited
        queue.push([newRow, newCol, dist + 1]);
      }
    }
  }
  
  return -1; // No path found
}

const pathGrid = [
  [0,0,0],
  [1,1,0],
  [1,1,0]
];
console.log(shortestPathBinaryMatrix(pathGrid)); // 4

Example: A* Search with Manhattan Heuristic

class MinHeap {
  constructor(compareFn) {
    this.heap = [];
    this.compare = compareFn || ((a, b) => a - b);
  }
  
  push(val) {
    this.heap.push(val);
    this.bubbleUp(this.heap.length - 1);
  }
  
  pop() {
    if (this.size() === 0) return null;
    if (this.size() === 1) return this.heap.pop();
    
    const min = this.heap[0];
    this.heap[0] = this.heap.pop();
    this.bubbleDown(0);
    return min;
  }
  
  bubbleUp(i) {
    while (i > 0) {
      const p = Math.floor((i - 1) / 2);
      if (this.compare(this.heap[p], this.heap[i]) <= 0) break;
      [this.heap[p], this.heap[i]] = [this.heap[i], this.heap[p]];
      i = p;
    }
  }
  
  bubbleDown(i) {
    while (true) {
      let min = i;
      const left = 2 * i + 1;
      const right = 2 * i + 2;
      
      if (left < this.size() && this.compare(this.heap[left], this.heap[min]) < 0) {
        min = left;
      }
      if (right < this.size() && this.compare(this.heap[right], this.heap[min]) < 0) {
        min = right;
      }
      if (min === i) break;
      
      [this.heap[i], this.heap[min]] = [this.heap[min], this.heap[i]];
      i = min;
    }
  }
  
  size() { return this.heap.length; }
}

function aStarSearch(grid, start, end) {
  const m = grid.length;
  const n = grid[0].length;
  const [startR, startC] = start;
  const [endR, endC] = end;
  
  // Manhattan distance heuristic
  const heuristic = (r, c) => Math.abs(r - endR) + Math.abs(c - endC);
  
  // Priority queue: [f-score, g-score, row, col]
  const pq = new MinHeap((a, b) => a[0] - b[0]);
  pq.push([heuristic(startR, startC), 0, startR, startC]);
  
  const visited = new Set();
  const dirs = [[0,1], [1,0], [0,-1], [-1,0]];
  
  while (pq.size() > 0) {
    const [f, g, row, col] = pq.pop();
    
    if (row === endR && col === endC) {
      return g; // Found shortest path
    }
    
    const key = `${row},${col}`;
    if (visited.has(key)) continue;
    visited.add(key);
    
    for (const [dr, dc] of dirs) {
      const newRow = row + dr;
      const newCol = col + dc;
      
      if (newRow >= 0 && newRow < m &&
          newCol >= 0 && newCol < n &&
          grid[newRow][newCol] === 0 &&
          !visited.has(`${newRow},${newCol}`)) {
        
        const newG = g + 1;
        const newH = heuristic(newRow, newCol);
        const newF = newG + newH;
        
        pq.push([newF, newG, newRow, newCol]);
      }
    }
  }
  
  return -1; // No path
}

const aStarGrid = [
  [0,0,0,0],
  [1,1,0,1],
  [0,0,0,0],
  [0,1,1,0]
];
console.log(aStarSearch(aStarGrid, [0,0], [3,3])); // 6

Note: A* is optimal when heuristic is admissible (never overestimates) and consistent (satisfies triangle inequality). Manhattan distance is perfect for grid-based pathfinding.

6. Diagonal Traversal Pattern

Pattern	Direction	Formula	Use Case
Main Diagonal	Top-left to bottom-right	`i === j`	Primary diagonal elements
Anti-Diagonal	Top-right to bottom-left	`i + j === n - 1`	Secondary diagonal elements
Diagonal Order	Bottom-left to top-right	Group by `i + j`, alternate direction	Zigzag diagonal traversal
Parallel Diagonals	All diagonals from corners	Start from edges, move inward	Process all diagonals systematically

Example: Diagonal Traversal (Zigzag)

function findDiagonalOrder(matrix) {
  if (!matrix.length || !matrix[0].length) return [];
  
  const m = matrix.length;
  const n = matrix[0].length;
  const result = [];
  
  // Group elements by diagonal (i+j is constant for each diagonal)
  const diagonals = new Map();
  
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      const diag = i + j;
      if (!diagonals.has(diag)) {
        diagonals.set(diag, []);
      }
      diagonals.get(diag).push(matrix[i][j]);
    }
  }
  
  // Process diagonals in order, alternating direction
  for (let d = 0; d < m + n - 1; d++) {
    const diagonal = diagonals.get(d);
    if (d % 2 === 0) {
      // Even diagonals: reverse (bottom-left to top-right)
      result.push(...diagonal.reverse());
    } else {
      // Odd diagonals: normal (top-right to bottom-left)
      result.push(...diagonal);
    }
  }
  
  return result;
}

const diagMatrix = [
  [1, 2, 3],
  [4, 5, 6],
  [7, 8, 9]
];
console.log(findDiagonalOrder(diagMatrix));
// [1, 2, 4, 7, 5, 3, 6, 8, 9]

// Visualization:
// Diag 0: [1]
// Diag 1: [2, 4] → reverse → [4, 2]
// Diag 2: [3, 5, 7]
// Diag 3: [6, 8] → reverse → [8, 6]
// Diag 4: [9]

Example: Process All Diagonals

function traverseAllDiagonals(matrix) {
  const m = matrix.length;
  const n = matrix[0].length;
  const diagonals = [];
  
  // Top-left to bottom-right diagonals
  // Start from first row
  for (let startCol = 0; startCol < n; startCol++) {
    const diagonal = [];
    let row = 0, col = startCol;
    
    while (row < m && col < n) {
      diagonal.push(matrix[row][col]);
      row++;
      col++;
    }
    
    diagonals.push(diagonal);
  }
  
  // Start from first column (skip [0,0] already covered)
  for (let startRow = 1; startRow < m; startRow++) {
    const diagonal = [];
    let row = startRow, col = 0;
    
    while (row < m && col < n) {
      diagonal.push(matrix[row][col]);
      row++;
      col++;
    }
    
    diagonals.push(diagonal);
  }
  
  return diagonals;
}

const mat = [
  [1, 2, 3, 4],
  [5, 6, 7, 8],
  [9, 10, 11, 12]
];
console.log(traverseAllDiagonals(mat));
// [[1], [2,6], [3,7,11], [4,8,12], [5,10], [9]]

Example: Check Diagonal and Anti-Diagonal Sums

function diagonalSum(matrix) {
  const n = matrix.length;
  let sum = 0;
  
  for (let i = 0; i < n; i++) {
    sum += matrix[i][i]; // Main diagonal
    sum += matrix[i][n - 1 - i]; // Anti-diagonal
  }
  
  // If odd size, center element counted twice
  if (n % 2 === 1) {
    const mid = Math.floor(n / 2);
    sum -= matrix[mid][mid];
  }
  
  return sum;
}

// Check if matrix is Toeplitz (diagonals have same value)
function isToeplitzMatrix(matrix) {
  const m = matrix.length;
  const n = matrix[0].length;
  
  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      if (matrix[i][j] !== matrix[i - 1][j - 1]) {
        return false;
      }
    }
  }
  
  return true;
}

const toeplitz = [
  [1, 2, 3, 4],
  [5, 1, 2, 3],
  [9, 5, 1, 2]
];
console.log(isToeplitzMatrix(toeplitz)); // true

Summary: Matrix Traversal Pattern

Spiral Traversal: Track 4 boundaries (top, bottom, left, right) - shrink after each direction
Search Sorted Matrix: Staircase from top-right - go left if too big, down if too small - O(m+n)
Island Counting: DFS/BFS from each unvisited land cell - mark visited to avoid recount
Rotate 90° CW: Transpose matrix (swap [i][j] ↔ [j][i]) then reverse each row
Shortest Path BFS: Level-by-level exploration - optimal for unweighted grids
A* Search: Priority queue with f = g + h (cost + heuristic) - faster than Dijkstra
Diagonal Traversal: Group by i+j sum - alternate direction for zigzag pattern
Direction Arrays: Use [[0,1],[1,0],[0,-1],[-1,0]] for 4-way, add diagonals for 8-way
In-place Modification: Mark visited cells directly in grid for O(1) space vs visited set O(m*n)
Key Insight: Matrix problems often reduce to graph traversal - choose BFS for shortest path, DFS for exploration

Related Cheatsheets

Datastructures-algorithms