DSA for Interviews, From Zero

Part 4 · Lesson 25 · 26 min read

2-D Arrays and Matrices

Rows and columns: transpose, rotate, spiral order, set zeroes and search a matrix.

On this page

  1. An array of rows
  2. Creating a matrix (and the shared-row trap)
  3. Looping: rows, columns, diagonals, neighbours
  4. Row and column sums
  5. Transpose and rotate by 90°
  6. Spiral order with four boundaries
  7. Set matrix zeroes
  8. Searching a sorted matrix
  9. Traced: the staircase search
  10. Practice questions (7)
  11. Make it stick
  12. Part 4 complete — what's next

An array of rows

A matrix (also called a grid) is a table of values arranged in rows and columns, like a spreadsheet. In JavaScript it is an array whose items are also arrays, one array for each row. m[r][c] means “go to row r, then take column c”. It is the nested-loop grid from Lesson 6, now holding data. Images, game boards, maps and spreadsheets are all matrices. Part 13 will treat grids as graphs (points joined by links).

Creating a matrix (and the shared-row trap)

JavaScript
const rows = 3, cols = 4;// Correct: a new row array for every rowconst grid = Array.from({ length: rows }, () => new Array(cols).fill(0));grid[0][1] = 5;console.log(grid[0][1], grid[1][1]); // 5 0// Trap: fill() puts the SAME row object in every slotconst bad = new Array(rows).fill(new Array(cols).fill(0));bad[0][1] = 5;console.log(bad[0][1], bad[1][1]);   // 5 5   ← every "row" changed
Always create rows with Array.from

new Array(rows).fill(row) puts a reference to the same row in every slot (Lesson 8 explained references: a reference is an arrow that points to one object, not a copy of it). So there is only one row, shown many times. Changing one cell then changes that column in every row. Use Array.from({ length: rows }, () => new Array(cols).fill(0)) instead. It runs the function once for each row, so every row is a new array.

Looping: rows, columns, diagonals, neighbours

JavaScript
const m = [  [1, 2, 3],  [4, 5, 6],  [7, 8, 9],];const rows = m.length, cols = m[0].length;for (let r = 0; r < rows; r++) {  for (let c = 0; c < cols; c++) {    // m[r][c] — row first, then column  }}// Diagonals of a square matrixlet main = 0, anti = 0;for (let i = 0; i < rows; i++) {  main += m[i][i];                 // top-left to bottom-right  anti += m[i][cols - 1 - i];      // top-right to bottom-left}console.log(main, anti);           // 15 15// The four neighbours of (r, c), skipping cells outside the gridconst DIRS = [[-1, 0], [1, 0], [0, -1], [0, 1]];   // up, down, left, rightfunction neighbours(r, c) {  const out = [];  for (const [dr, dc] of DIRS) {    const nr = r + dr, nc = c + dc;    if (nr >= 0 && nr < rows && nc >= 0 && nc < cols) out.push(m[nr][nc]);  }  return out;}console.log(neighbours(0, 0));     // [ 4, 2 ]console.log(neighbours(1, 1));     // [ 2, 8, 4, 6 ]

The direction array DIRS is a small list of steps: each pair is how much to change the row and the column. It is worth learning by heart. It turns “check up, down, left and right” into one short loop. The bounds check (the if that tests the new position is inside the grid) stops you from reading outside the grid. Reading outside is the most common matrix bug. You will use this pattern in every grid problem in Part 13.

Row and column sums

JavaScript
const m = [  [3, 1, 2],  [0, 4, 5],];const rowSums = m.map((row) => row.reduce((a, b) => a + b, 0));const colSums = new Array(m[0].length).fill(0);for (const row of m) {  for (let c = 0; c < row.length; c++) colSums[c] += row[c];}console.log(rowSums, colSums); // [ 6, 9 ] [ 3, 5, 7 ]

Visiting every cell once takes O(rows × cols) time. This is the number of cells, which is the size of the input. So it is linear time for a matrix.

Transpose and rotate by 90°

The transpose of a matrix turns its rows into columns: t[c][r] = m[r][c]. To rotate a square matrix 90° clockwise in place (using the same matrix, with no second one), transpose it and then reverse each row:

Dry run · rotating [[1, 2, 3], [4, 5, 6], [7, 8, 9]] clockwise
StepRow 0Row 1Row 2
start1 2 34 5 67 8 9
transpose1 4 72 5 83 6 9
reverse each row7 4 18 5 29 6 3

For anticlockwise, reverse each row first and then transpose. Another way is to transpose and then reverse the order of the rows.

JavaScript
function rotate(m) {  const n = m.length;  // 1. transpose: swap across the main diagonal (only j > i, or each pair swaps twice)  for (let i = 0; i < n; i++) {    for (let j = i + 1; j < n; j++) {      [m[i][j], m[j][i]] = [m[j][i], m[i][j]];    }  }  // 2. reverse every row  for (const row of m) row.reverse();  return m;}console.log(rotate([[1, 2, 3], [4, 5, 6], [7, 8, 9]]));// [ [ 7, 4, 1 ], [ 8, 5, 2 ], [ 9, 6, 3 ] ]

Spiral order with four boundaries

Reading a matrix in a spiral means: right along the top, down the right side, left along the bottom, up the left side, then repeat on the inside. This tests whether you handle boundaries carefully. Keep four boundaries (top, bottom, left, right). After you read a side, move that boundary one step inwards:

JavaScript
function spiralOrder(m) {  const out = [];  let top = 0, bottom = m.length - 1, left = 0, right = m[0].length - 1;  while (top <= bottom && left <= right) {    for (let c = left; c <= right; c++) out.push(m[top][c]);          // → along the top    top++;    for (let r = top; r <= bottom; r++) out.push(m[r][right]);        // ↓ down the right    right--;    if (top <= bottom) {      for (let c = right; c >= left; c--) out.push(m[bottom][c]);     // ← along the bottom      bottom--;    }    if (left <= right) {      for (let r = bottom; r >= top; r--) out.push(m[r][left]);       // ↑ up the left      left++;    }  }  return out;}console.log(spiralOrder([[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12]]));// [ 1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7 ]

The two if checks matter when the matrix is not square. After you read the top row and the right column, what is left may be a single row or a single column. Without the checks, you would read it twice.

Set matrix zeroes

The task: if a cell is 0, set its whole row and column to 0. If you write zeros while you are still scanning, the new zeros look like original zeros and spread too far. So do it in two passes. First scan and remember which rows and columns to clear. Then write the zeros:

JavaScript
function setZeroes(m) {  const zeroRows = new Set(), zeroCols = new Set();  for (let r = 0; r < m.length; r++)                       // pass 1: find the zeros    for (let c = 0; c < m[0].length; c++)      if (m[r][c] === 0) { zeroRows.add(r); zeroCols.add(c); }  for (let r = 0; r < m.length; r++)                       // pass 2: write the zeros    for (let c = 0; c < m[0].length; c++)      if (zeroRows.has(r) || zeroCols.has(c)) m[r][c] = 0;  return m;}console.log(setZeroes([[1, 1, 1], [1, 0, 1], [1, 1, 1]]));// [ [ 1, 0, 1 ], [ 0, 0, 0 ], [ 1, 0, 1 ] ]

This takes O(rows × cols) time and O(rows + cols) extra space. A common follow-up asks for O(1) extra space (a fixed amount, however big the matrix is). The idea is to use the first row and first column of the matrix itself as the markers (Practice question 5).

There are two common kinds of “sorted matrix”. They need different searches:

  • Fully sorted (each row is sorted, and each row starts after the previous one ends): this is one sorted list folded into rows. Use binary search (a search that checks the middle value and throws away half of the range each time) over the indices 0 … rows × cols − 1. Turn an index into a cell with row = Math.floor(i / cols) and col = i % cols. It takes O(log(rows × cols)) time.
  • Rows and columns sorted separately (every row is sorted, and every column is sorted, but rows do not follow each other): start at the top-right corner and walk like a staircase. It takes O(rows + cols) time.
JavaScript
// Rows sorted, and each row starts after the previous row ends:// the matrix is really one sorted list of rows × cols values.function searchMatrix(m, target) {  const rows = m.length, cols = m[0].length;  let lo = 0, hi = rows * cols - 1;  while (lo <= hi) {    const mid = Math.floor((lo + hi) / 2);    const v = m[Math.floor(mid / cols)][mid % cols];    // 1-D index → (row, column)    if (v === target) return true;    if (v < target) lo = mid + 1;    else hi = mid - 1;  }  return false;}console.log(searchMatrix([[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60]], 3));  // trueconsole.log(searchMatrix([[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60]], 13)); // false

Lesson 28 explains binary search in full. Here, look only at how the index is converted to a row and a column.

Traced: the staircase search

step 1 / 9
Set up
start at the top-right corner: (0, 3)

From here, moving left gives smaller values and moving down gives bigger values. So each direction has one clear meaning.

1const m = [2  [1, 4, 7, 11],3  [2, 5, 8, 12],4  [3, 6, 9, 16],5  [10, 13, 14, 17],6];7const target = 9;▶let r = 0, c = m[0].length - 1;9while (r < m.length && c >= 0) {10  if (m[r][c] === target) break;11  if (m[r][c] > target) c--;12  else r++;13}14console.log(r, c);
Variables
target9
r0
c3
value11
Console
(nothing printed yet)
At the top-right corner, a value that is too big rules out its whole column. A value that is too small rules out its whole row. · interactive

Practice questions

Draw a small matrix on paper for every question. Most matrix bugs are index mistakes, and a drawing shows them at once.

Q1Matrix diagonal sumEasy

Return the sum of both diagonals of a square matrix, counting the centre once.

Example 1
Input: [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
Output: 25
Explanation: Main diagonal 1 + 5 + 9, other diagonal 3 + 7 (the centre 5 is counted once).
Example 2
Input: [[5]]
Output: 5
Explanation: One cell.
Stuck? Open one hint at a time
Hint 1
Main diagonal: (i, i). Other diagonal: (i, n − 1 − i). For odd n they share the centre.
Show the solution with explanations
Approach 1One loop over i
The idea

Add both diagonal cells for each row, skipping the second when it is the same cell.

JavaScript
function diagonalSum(mat) {  const n = mat.length;  let sum = 0;  for (let i = 0; i < n; i++) {    sum += mat[i][i];    if (i !== n - 1 - i) sum += mat[i][n - 1 - i];  }  return sum;}console.log(diagonalSum([[1, 2, 3], [4, 5, 6], [7, 8, 9]])); // 25console.log(diagonalSum([[5]]));                             // 5
How it works

O(n) time. Only the diagonal cells are visited, not all n² cells.

Which approach should you use?

Do not use a double loop with an if to find the diagonals. Use the indices directly. (LeetCode 1572.)

Q2Transpose matrixEasy

Return the transpose of a matrix (rows become columns).

Example 1
Input: [[1, 2, 3], [4, 5, 6]]
Output: [[1, 4], [2, 5], [3, 6]]
Explanation: 2 × 3 becomes 3 × 2: row r becomes column r.
Stuck? Open one hint at a time
Hint 1
The result has cols rows and rows columns. t[c][r] = m[r][c].
Show all 2 solutions with explanations
Approach 1New matrix
The idea

Create a cols × rows matrix and copy each cell to its swapped position.

JavaScript
function transpose(m) {  const rows = m.length, cols = m[0].length;  const t = Array.from({ length: cols }, () => new Array(rows));  for (let r = 0; r < rows; r++)    for (let c = 0; c < cols; c++) t[c][r] = m[r][c];  return t;}console.log(transpose([[1, 2, 3], [4, 5, 6]])); // [ [ 1, 4 ], [ 2, 5 ], [ 3, 6 ] ]
How it works

O(rows × cols). A non-square matrix cannot easily be transposed in place, because its shape changes (rows × cols becomes cols × rows).

Approach 2With map
The idea

Column c of m is row c of the result.

JavaScript
const transpose = (m) => m[0].map((_, c) => m.map((row) => row[c]));console.log(transpose([[1, 2, 3], [4, 5, 6]])); // [ [ 1, 4 ], [ 2, 5 ], [ 3, 6 ] ]
How it works

Same cost, but shorter. Make sure you can also write the loop version.

Which approach should you use?

(LeetCode 867.)

Q3Rotate imageMedium

Rotate an n × n matrix 90° clockwise, in place.

Example 1
Input: [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
Output: [[7, 4, 1], [8, 5, 2], [9, 6, 3]]
Explanation: 90° clockwise.
Example 2
Input: [[5, 1, 9, 11], [2, 4, 8, 10], [13, 3, 6, 7], [15, 14, 12, 16]]
Output: [[15, 13, 2, 5], [14, 3, 4, 1], [12, 6, 8, 9], [16, 7, 10, 11]]
Explanation: The first column read upwards becomes the first row.
Stuck? Open one hint at a time
Hint 1
In place: transpose, then reverse each row.
Hint 2
Where does (r, c) go? To (c, n − 1 − r).
Show all 2 solutions with explanations
Approach 1Copy with the index formula
The idea

Write each value to its new position in a new matrix.

JavaScript
function rotate(m) {  const n = m.length;  const out = Array.from({ length: n }, () => new Array(n));  for (let r = 0; r < n; r++)    for (let c = 0; c < n; c++) out[c][n - 1 - r] = m[r][c];  return out;}console.log(rotate([[1, 2, 3], [4, 5, 6], [7, 8, 9]])); // [ [ 7, 4, 1 ], [ 8, 5, 2 ], [ 9, 6, 3 ] ]
How it works

O(n²) time and O(n²) extra space. This is not allowed when the question says “in place”.

Approach 2Transpose + reverse rows (in place)
The idea

The method from the lesson.

JavaScript
function rotate(m) {  const n = m.length;  for (let i = 0; i < n; i++)    for (let j = i + 1; j < n; j++) [m[i][j], m[j][i]] = [m[j][i], m[i][j]];  for (const row of m) row.reverse();  return m;}console.log(rotate([[5, 1, 9, 11], [2, 4, 8, 10], [13, 3, 6, 7], [15, 14, 12, 16]]));// [ [ 15, 13, 2, 5 ], [ 14, 3, 4, 1 ], [ 12, 6, 8, 9 ], [ 16, 7, 10, 11 ] ]
How it works

O(n²) time, O(1) extra space. The inner loop starts at j = i + 1 so that each pair is swapped only once.

Which approach should you use?

The in-place version is expected. (LeetCode 48.)

Q4Spiral matrixMedium

Return all values of the matrix in spiral order.

Example 1
Input: [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
Output: [1, 2, 3, 6, 9, 8, 7, 4, 5]
Explanation: Clockwise from the top-left, moving inwards.
Example 2
Input: [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12]]
Output: [1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7]
Explanation: A non-square matrix: the last ring is a single row.
Stuck? Open one hint at a time
Hint 1
Four boundaries: top, bottom, left, right. Shrink each after reading its side.
Hint 2
Check the boundaries again before you read the bottom row and the left column.
Show the solution with explanations
Approach 1Four boundaries
The idea

The method from the lesson.

JavaScript
function spiralOrder(m) {  const out = [];  let top = 0, bottom = m.length - 1, left = 0, right = m[0].length - 1;  while (top <= bottom && left <= right) {    for (let c = left; c <= right; c++) out.push(m[top][c]);    top++;    for (let r = top; r <= bottom; r++) out.push(m[r][right]);    right--;    if (top <= bottom) {      for (let c = right; c >= left; c--) out.push(m[bottom][c]);      bottom--;    }    if (left <= right) {      for (let r = bottom; r >= top; r--) out.push(m[r][left]);      left++;    }  }  return out;}console.log(spiralOrder([[1, 2, 3], [4, 5, 6], [7, 8, 9]]));           // [ 1, 2, 3, 6, 9, 8, 7, 4, 5 ]console.log(spiralOrder([[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12]])); // [ 1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7 ]
How it works
Dry run · 3 × 4 example, one row per side
SideReadsBoundary after
top →1 2 3 4top = 1
right ↓8 12right = 2
bottom ←11 10 9bottom = 1
left ↑5left = 1
top →6 7top = 2 (loop ends)
Which approach should you use?

O(rows × cols) time. Test with a single row, a single column and a non-square matrix. (LeetCode 54.)

Q5Set matrix zeroes (O(1) space)Medium

If a cell is 0, set its entire row and column to 0, in place.

Example 1
Input: [[1, 1, 1], [1, 0, 1], [1, 1, 1]]
Output: [[1, 0, 1], [0, 0, 0], [1, 0, 1]]
Explanation: The 0 clears row 1 and column 1.
Example 2
Input: [[0, 1, 2, 0], [3, 4, 5, 2], [1, 3, 1, 5]]
Output: [[0, 0, 0, 0], [0, 4, 5, 0], [0, 3, 1, 0]]
Explanation: Zeros in the first row clear columns 0 and 3.
Stuck? Open one hint at a time
Hint 1
The Sets version uses O(rows + cols) extra space. Where else could you store the marks?
Hint 2
Use the first row and first column as markers. But first remember, in two separate flags, whether they contained a 0 themselves.
Show all 2 solutions with explanations
Approach 1Row and column Sets
The idea

The version from the lesson.

JavaScript
function setZeroes(m) {  const rows = new Set(), cols = new Set();  m.forEach((row, r) => row.forEach((v, c) => { if (v === 0) { rows.add(r); cols.add(c); } }));  m.forEach((row, r) => row.forEach((_, c) => { if (rows.has(r) || cols.has(c)) row[c] = 0; }));  return m;}console.log(setZeroes([[1, 1, 1], [1, 0, 1], [1, 1, 1]])); // [ [ 1, 0, 1 ], [ 0, 0, 0 ], [ 1, 0, 1 ] ]
How it works

O(rows × cols) time, O(rows + cols) space.

Approach 2First row and column as markers
The idea
  1. Remember whether row 0 and column 0 contain a zero.
  2. For every other zero at (r, c), set m[r][0] = 0 and m[0][c] = 0.
  3. Clear inner cells using those marks, then clear row 0 and column 0 if needed.
JavaScript
function setZeroes(m) {  const R = m.length, C = m[0].length;  const firstRow = m[0].some((v) => v === 0);  const firstCol = m.some((row) => row[0] === 0);  for (let r = 1; r < R; r++)    for (let c = 1; c < C; c++)      if (m[r][c] === 0) { m[r][0] = 0; m[0][c] = 0; }  for (let r = 1; r < R; r++)    for (let c = 1; c < C; c++)      if (m[r][0] === 0 || m[0][c] === 0) m[r][c] = 0;  if (firstRow) m[0].fill(0);  if (firstCol) for (let r = 0; r < R; r++) m[r][0] = 0;  return m;}console.log(setZeroes([[1, 1, 1], [1, 0, 1], [1, 1, 1]]));// [ [ 1, 0, 1 ], [ 0, 0, 0 ], [ 1, 0, 1 ] ]console.log(setZeroes([[0, 1, 2, 0], [3, 4, 5, 2], [1, 3, 1, 5]]));// [ [ 0, 0, 0, 0 ], [ 0, 4, 5, 0 ], [ 0, 3, 1, 0 ] ]
How it works

O(1) extra space. The two flags are needed because the marks from other cells overwrite row 0 and column 0.

Which approach should you use?

Give the Sets version first. The marker version is the follow-up. (LeetCode 73.)

Q6Search a fully sorted matrixMedium

Each row is sorted, and the first value of each row is greater than the last value of the previous row. Return whether target is in the matrix.

Example 1
Input: matrix = [[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60]], target = 3
Output: true
Explanation: 3 is in row 0.
Example 2
Input: same matrix, target = 13
Output: false
Explanation: 13 would be between 11 and 16, but is not there.
Stuck? Open one hint at a time
Hint 1
Each row starts after the previous row ends, so the whole matrix is one sorted list.
Hint 2
Binary search on index i; read m[Math.floor(i / cols)][i % cols].
Show the solution with explanations
Approach 1Binary search on a virtual 1-D array
The idea

Search indices 0 … rows × cols − 1 and convert each index to a cell.

JavaScript
function searchMatrix(m, target) {  const cols = m[0].length;  let lo = 0, hi = m.length * cols - 1;  while (lo <= hi) {    const mid = Math.floor((lo + hi) / 2);    const v = m[Math.floor(mid / cols)][mid % cols];    if (v === target) return true;    if (v < target) lo = mid + 1;    else hi = mid - 1;  }  return false;}const M = [[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60]];console.log(searchMatrix(M, 3));  // trueconsole.log(searchMatrix(M, 13)); // false
How it works

O(log(rows × cols)) time. The index conversion is useful in many other problems too.

Which approach should you use?

(LeetCode 74.)

Q7Search a row- and column-sorted matrixMedium

Each row is sorted left to right and each column is sorted top to bottom. Return whether target is in the matrix.

Example 1
Input: the 4 × 4 matrix from the lesson, target = 9
Output: true
Explanation: Found at (2, 2) in four steps.
Example 2
Input: the same matrix, target = 20
Output: false
Explanation: The walk leaves the grid without finding it.
Stuck? Open one hint at a time
Hint 1
The 1-D trick does not work: row 1 does not start after row 0 ends.
Hint 2
Start at the top-right corner.
Show the solution with explanations
Approach 1Staircase from the top-right
The idea

Too big → move left. Too small → move down.

JavaScript
function searchMatrix(m, target) {  let r = 0, c = m[0].length - 1;  while (r < m.length && c >= 0) {    if (m[r][c] === target) return true;    if (m[r][c] > target) c--;    else r++;  }  return false;}const M = [[1, 4, 7, 11], [2, 5, 8, 12], [3, 6, 9, 16], [10, 13, 14, 17]];console.log(searchMatrix(M, 9));  // trueconsole.log(searchMatrix(M, 20)); // false
How it works

O(rows + cols) time, O(1) extra space. The bottom-left corner works too, with the directions swapped. The top-left and bottom-right corners do not work, because from there both moves go in the same direction (both make the value bigger, or both make it smaller), so you cannot tell which way to go.

Which approach should you use?

Know which kind of “sorted matrix” you have before choosing the search. (LeetCode 240.)

Make it stick

Make it stick — close this page, then
  1. Write the safe way to create a rows × cols grid, and explain the fill trap.
  2. Write the four-direction neighbour loop with its bounds check.
  3. Rotate a 3 × 3 matrix by hand: transpose, then reverse rows.
  4. Explain why the staircase search starts at the top-right corner.

Revisit schedule: solve two of the questions again tomorrow, again in 3 days, and once more in a week — without looking at the answers. Each time it will feel easier. That is the memory forming.

Part 4 complete — what's next

You now know the main array patterns: read/write pointers, prefix sums, two pointers, fixed and variable windows, Kadane's algorithm and matrix traversal. Together they solve many of the array questions in interviews.

Part 5 — Hashing Patterns goes back to Maps and Sets and uses them to solve problems: Two Sum, “have I seen this before?”, longest consecutive sequence, grouping anagrams and finding the majority element.

Practise on LeetCode

Real interview problems that use exactly what this lesson teaches. Solve them in JavaScript after the practice questions above.

Published by Jainik · Last updated · How these lessons are made

Keep learning

Related series