Matrix Problems
Matrices (2D arrays) appear in many algorithmic problems. Here are classic matrix problems and their efficient solutions.
1. Spiral Traversal
Print matrix elements in spiral order.
public static List spiralOrder(int[][] matrix) {
List result = new ArrayList<>();
int top = 0, bottom = matrix.length - 1;
int left = 0, right = matrix[0].length - 1;
while (top <= bottom && left <= right) {
// left -> right
for (int i = left; i <= right; i++) result.add(matrix[top][i]);
top++;
// top -> bottom
for (int i = top; i <= bottom; i++) result.add(matrix[i][right]);
right--;
// right -> left (if still rows)
if (top <= bottom) {
for (int i = right; i >= left; i--) result.add(matrix[bottom][i]);
bottom--;
}
// bottom -> top (if still columns)
if (left <= right) {
for (int i = bottom; i >= top; i--) result.add(matrix[i][left]);
left++;
}
}
return result;
}
2. Rotate Matrix by 90 Degrees
Transpose and then reverse each row.
public static void rotate(int[][] matrix) {
// Transpose
for (int i = 0; i < matrix.length; i++) {
for (int j = i; j < matrix[0].length; j++) {
int temp = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = temp;
}
}
// Reverse each row
for (int i = 0; i < matrix.length; i++) {
int left = 0, right = matrix[0].length - 1;
while (left < right) {
int temp = matrix[i][left];
matrix[i][left] = matrix[i][right];
matrix[i][right] = temp;
left++; right--;
}
}
}
3. Set Matrix Zeroes
If an element is zero, set its entire row and column to zero. Use first row and column as markers to avoid extra space.
Two Minute Drill
- Spiral traversal: maintain four boundaries and move inward.
- Rotate matrix: transpose then reverse rows (for clockwise).
- Set zeroes: use first row/col as markers to store zero information.
- Matrix problems test spatial reasoning and index manipulation.
Need more clarification?
Drop us an email at career@quipoinfotech.com