Beginner LevelData Structures & Algorithms
How do you traverse a 2D matrix (row-major, spiral, diagonal)?
ā Interview Prompt: Traverse a 2D matrix in row-major order and implement spiral order traversal.
Row-Major Traversal: $O(M \times N)$
Access each row left-to-right, top-to-bottom. Maximises CPU cache efficiency since 2D arrays are stored in row-major order in memory.
Spiral Order Traversal:
Maintain four boundaries ā top, bottom, left, right ā and peel off the outer layer in each pass (right ā down ā left ā up), shrinking boundaries inward.
Code Implementation Example
typescript
function spiralOrder(matrix: number[][]): number[] {
const result: number[] = [];
let top = 0, bottom = matrix.length - 1;
let left = 0, right = matrix[0].length - 1;
while (top <= bottom && left <= right) {
for (let c = left; c <= right; c++) result.push(matrix[top][c]);
top++;
for (let r = top; r <= bottom; r++) result.push(matrix[r][right]);
right--;
if (top <= bottom) {
for (let c = right; c >= left; c--) result.push(matrix[bottom][c]);
bottom--;
}
if (left <= right) {
for (let r = bottom; r >= top; r--) result.push(matrix[r][left]);
left++;
}
}
return result;
}š”Spiral matrix traversal using four shrinking boundary pointers.
šÆ Interview Key Takeaway
Matrix problems often require boundary pointers. Spiral order is a classic interview question testing careful index management.
#DSA#Matrix#Arrays#2D#Beginner
Back to all Data Structures & Algorithms Questionsā