Matrix Problems

🗺️ Matrix Adventures: Navigating the Grid

Imagine you’re an explorer walking through a magical grid city. Each cell is a room with a number inside. Your job? Learn all the secret paths to walk through this city!

🌟 The Big Picture

A matrix is just a grid—like a chocolate bar with rows and columns. Each little square (cell) holds a value. Today we’ll learn five amazing tricks to explore and transform these grids:

graph TD
    A["Matrix Problems"] --> B["Traversal Patterns"]
    A --> C["Spiral Matrix"]
    A --> D["Rotate Matrix"]
    A --> E["Set Matrix Zeroes"]
    A --> F["Search 2D Matrix II"]

1️⃣ Matrix Traversal Patterns

🎯 What Is It?

Traversal means visiting every room in the grid. Think of it like reading a book—you can read left-to-right, top-to-bottom, or even in zigzag!

🚶 Common Walking Patterns

🍬 Simple Example

Imagine this 3×3 candy grid:

1  2  3
4  5  6
7  8  9

Row-wise traversal: 1, 2, 3, 4, 5, 6, 7, 8, 9 Column-wise traversal: 1, 4, 7, 2, 5, 8, 3, 6, 9 Zigzag traversal: 1, 2, 3, 6, 5, 4, 7, 8, 9

💻 Code Example

// Row-wise traversal
function rowWise(matrix) {
  const result = [];
  for (let row of matrix) {
    for (let cell of row) {
      result.push(cell);
    }
  }
  return result;
}

🧠 Why It Matters

Every matrix problem starts with knowing how to walk through it. Master the walks, master the matrix!

2️⃣ Spiral Matrix

🌀 The Story

Imagine a snail starting at the top-left corner of the grid. It walks right until it hits a wall, then turns down, then left, then up—always spiraling inward until it visits every cell.

graph TD
    A["Start Top-Left"] --> B["Go Right →"]
    B --> C["Go Down ↓"]
    C --> D["Go Left ←"]
    D --> E["Go Up ↑"]
    E --> F["Spiral Inward"]
    F --> G["Done!"]

🎨 Visual Walk-Through

Grid:           Spiral Order:
1  2  3         1 → 2 → 3
4  5  6               ↓
7  8  9         4 → 5   6
                ↑       ↓
                7 ← 8 ← 9

Result: 1, 2, 3, 6, 9, 8, 7, 4, 5

🔑 The Secret

Keep four boundaries:

• top: which row to start from the top
• bottom: which row to end at the bottom
• left: which column to start from the left
• right: which column to end at the right

After each direction, shrink the boundary!

💻 Code Example

function spiralOrder(matrix) {
  const result = [];
  let top = 0, bottom = matrix.length - 1;
  let left = 0, right = matrix[0].length - 1;

  while (top <= bottom && left <= right) {
    // Go right
    for (let i = left; i <= right; i++)
      result.push(matrix[top][i]);
    top++;

    // Go down
    for (let i = top; i <= bottom; i++)
      result.push(matrix[i][right]);
    right--;

    // Go left (if rows remain)
    if (top <= bottom) {
      for (let i = right; i >= left; i--)
        result.push(matrix[bottom][i]);
      bottom--;
    }

    // Go up (if columns remain)
    if (left <= right) {
      for (let i = bottom; i >= top; i--)
        result.push(matrix[i][left]);
      left++;
    }
  }
  return result;
}

⏱️ Complexity

• Time: O(m × n) — visit every cell once
• Space: O(1) extra — just boundaries

3️⃣ Rotate Matrix

🔄 The Challenge

Turn the entire picture 90 degrees clockwise. Imagine picking up a photo and rotating it—that’s what we do to the matrix!

🎯 The Magic Two-Step

1. Transpose — flip rows into columns (mirror along diagonal)
2. Reverse each row — flip left-to-right

graph LR
    A["Original"] --> B["Transpose"]
    B --> C["Reverse Rows"]
    C --> D["Rotated 90°"]

🍰 Example

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

The number 3 traveled from top-right to bottom-right—rotated 90°! ✨

💻 Code Example

function rotate(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 row
  for (let row of matrix) {
    row.reverse();
  }
}

🧩 Pro Tip

• 90° clockwise: Transpose + Reverse rows
• 90° counter-clockwise: Transpose + Reverse columns
• 180°: Reverse rows, then reverse columns

4️⃣ Set Matrix Zeroes

💥 The Problem

If any cell contains 0, its entire row AND column become zeros. It’s like a “bomb” that destroys its row and column!

🚫 The Trap

Don’t set zeros while scanning—you’ll trigger chain reactions and wipe everything!

✅ The Smart Solution

Use the first row and first column as markers:

graph TD
    A["Scan Matrix"] --> B["Mark first row/col"]
    B --> C["Process inner cells"]
    C --> D["Zero out marked rows"]
    D --> E["Zero out marked cols"]
    E --> F["Handle first row/col"]

🎨 Example

Before:         After:
1  1  1         1  0  1
1  0  1    →    0  0  0
1  1  1         1  0  1

The zero at (1,1) “exploded” its row and column!

💻 Code Example

function setZeroes(matrix) {
  const m = matrix.length;
  const n = matrix[0].length;
  let firstRowZero = false;
  let firstColZero = false;

  // Check if first row has zero
  for (let j = 0; j < n; j++) {
    if (matrix[0][j] === 0) firstRowZero = true;
  }

  // Check if first column has zero
  for (let i = 0; i < m; i++) {
    if (matrix[i][0] === 0) firstColZero = true;
  }

  // Mark zeros in first row/col
  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      if (matrix[i][j] === 0) {
        matrix[i][0] = 0;
        matrix[0][j] = 0;
      }
    }
  }

  // Zero out based on marks
  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      if (matrix[i][0] === 0 || matrix[0][j] === 0) {
        matrix[i][j] = 0;
      }
    }
  }

  // Handle first row
  if (firstRowZero) {
    for (let j = 0; j < n; j++) matrix[0][j] = 0;
  }

  // Handle first column
  if (firstColZero) {
    for (let i = 0; i < m; i++) matrix[i][0] = 0;
  }
}

⏱️ Complexity

• Time: O(m × n)
• Space: O(1) — we reuse the matrix itself!

5️⃣ Search a 2D Matrix II

🔍 The Setup

The matrix is sorted in a special way:

• Each row is sorted left → right (increasing)
• Each column is sorted top → bottom (increasing)

🎯 The Trick: Start from a Corner!

Start at top-right (or bottom-left). From there:

• If target is smaller → move LEFT
• If target is larger → move DOWN

It’s like playing a game where you always know which direction to go!

graph TD
    A["Start Top-Right"] --> B{Compare with Target}
    B -->|Target smaller| C["Move Left"]
    B -->|Target larger| D["Move Down"]
    B -->|Found!| E["Return True"]
    C --> B
    D --> B

🎨 Example

Matrix:              Find: 5
1   4   7   11
2   5   8   12      Start at 11
3   6   9   16      5 < 11 → go left to 7
10  13  14  17      5 < 7 → go left to 4
                    5 > 4 → go down to 5
                    Found! ✅

💻 Code Example

function searchMatrix(matrix, target) {
  if (!matrix.length) return false;

  let row = 0;
  let col = matrix[0].length - 1;

  while (row < matrix.length && col >= 0) {
    const current = matrix[row][col];

    if (current === target) {
      return true;
    } else if (current > target) {
      col--;  // Move left
    } else {
      row++;  // Move down
    }
  }

  return false;
}

⏱️ Complexity

• Time: O(m + n) — at most m + n steps!
• Space: O(1) — just two pointers

🧠 Why This Works

From the top-right corner:

• Going left always gives smaller values
• Going down always gives larger values

You eliminate one row OR one column with each step!

🏆 Summary Table

🎉 You Did It!

You’ve learned five powerful matrix techniques. Think of the matrix as your playground:

• 🚶 Traversal = Learn to walk
• 🐌 Spiral = Walk like a snail
• 🔄 Rotate = Spin the playground
• 💣 Set Zeroes = Handle explosions smartly
• 🔍 Search = Find treasures efficiently

Now go practice—the grid is yours to explore! 🗺️✨