Mastering Matrix Traversal and Search in Interviews

You stop making 2D grids harder than they are by tracking four boundary variables instead of trying to manipulate the array in place on your first pass. Most candidates fail matrix rounds because they lose track of row and column limits during traversal, which leads to infinite loops or out of bounds errors.

The Four Boundary Trap

When you face a problem like spiral order traversal, you do not need to write complex conditional statements for every single cell. You need four integer variables named top, bottom, left, and right.

Take a 3 by 3 matrix containing values from 1 to 9. The top boundary starts at row 0, the bottom at row 2, the left at column 0, and the right at column 2.

As you traverse from left to right across the top row, you process 1, 2, and 3. Then you increment top to 1. When you move down the right column, you process 6 and 9, then decrement right to 1. This shrinking window removes the need for visited boolean arrays.

Index Math for Rotations

Rotating an image by 90 degrees clockwise without extra space breaks down into two distinct operations. You transpose the matrix by swapping matrix[i][j] with matrix[j][i] for all valid pairs. Then you reverse every single row in place.

If you try to calculate the new destination coordinates in a single formula while shifting elements four at a time, you will mix up your indices. The two step transpose and reverse approach uses straightforward loops where i runs from 0 to n - 1 and j runs from i + 1 to n - 1.

Searching Sorted Grids

Consider a 2D matrix where each row is sorted from left to right, and the first integer of each row is greater than the last integer of the previous row. You do not need a two pointer search or a nested loop. Treat the entire 2D grid as a 1D array of length m * n by converting a single index mid into 2D coordinates using row = mid / cols and col = mid % cols.

This maps a 3 by 4 matrix index of 5 directly to row 1 and column 1. The standard binary search logic applies immediately without modification.

Grid BFS Foundations

Matrix problems that ask for the shortest path or connected components are standard breadth first search problems in disguise. You queue up coordinate pairs and use a directions array containing {-1, 0}, {1, 0}, {0, -1}, and {0, 1} to generate valid neighbors.

Always mark a cell as visited the moment you push it onto the queue, rather than when you pop it. Waiting until the pop step allows duplicate nodes to enter the queue, which causes memory limits to exceed on large test cases.

Index Bookkeeping Rules

• Define top, bottom, left, right before writing any loops.
• Check top <= bottom and left <= right inside the traversal condition.
• Convert 1D indices to 2D using division for row and modulo for column.
• Transpose before reversing when rotating matrices in place.
• Mark visited cells during queue insertion for graph traversals.

Practice these patterns on DSA Tracker today by solving Search a 2D Matrix using the flat index conversion method.

Keep going with the step-by-step visualizer and practice problems.

Further reading: Binary search on Wikipedia.