Matrix

Illustration showing a word being searched in a grid using DFS backtracking

Word Search (Blind 75): DFS + Backtracking Explained

Problem Overview We are given a 2D array of characters named board. The board size is m x n. We are also given a string word. Our goal is to find whether the word exists in the board. If found → return true, otherwise → return false. LeetCode - Word Search Example Input: board = [["A","B","C","E"], ["S","F","C","S"], ["A","D","E","E"]], word = "ABCCED" Output: true ...

Illustration showing a matrix rotated 90 degrees clockwise

Rotate Image (Blind 75): 90° Matrix Rotation Explained

Problem Overview We are given a 2D matrix of size n * n. The matrix represents an image. Our goal is to rotate the image by 90 degrees clockwise. The solution must use constant extra space (in-place). LeetCode - Rotate Image Example Input: matrix = [[1,2,3], [4,5,6], [7,8,9]] Output: [[7,4,1], [8,5,2], [9,6,3]] Intuition If we remember basic matrix properties: Transpose of a matrix Reverse of each row If we: First take the transpose (swap (i,j) with (j,i)) Then reverse every row We effectively rotate the matrix 90° clockwise. ...

Illustration of matrix traversal in spiral order and the result order

Spiral Matrix (Blind 75): Matrix traversal in spiral order

Problem Overview We are given a matrix of size m * n. We need to return all elements of the matrix in spiral order. Note: The matrix is not necessarily square. LeetCode - Spiral Matrix Example Input: matrix = [[1,2,3], [4,5,6], [7,8,9]] Output: [1,2,3,6,9,8,7,4,5] Intuition We need to travese the matrix in this order Indices traversal: (0,0) → (0,1) → (0,2) right (0,2) ↓ (1,2) ↓ (2,2) down (2,2) ← (2,1) ← (2,0) left (2,0) ↑ (1,0) up (1,0) → (1,1) right So the movement pattern becomes: ...

Illustration showing rows and columns of a matrix being set to zero

Set Matrix Zeroes (Blind 75): O(1) Space Solution

Problem Overview We are given a matrix of size m * n. If any element in the matrix is 0, set its entire row and column to 0. Constraint: The solution must use O(1) extra space. LeetCode - Set Matrix Zeroes Example Input: matrix = [[1,1,1],[1,0,1],[1,1,1]] Output: [[1,0,1],[0,0,0],[1,0,1]] Brute Force Intuition and Approach Use an unordered_map to store positions of original zeros. In a second traversal: ...