Introduction
Rotating a 2D matrix is a classic coding problem often asked in interviews to test your understanding of matrix manipulation and algorithm efficiency. In this post, we will discuss the theory behind rotating an image (represented as a matrix), the JavaScript code to achieve this, and an analysis of the time and space complexity.
Problem Statement
The task is simple: You are given an N x N matrix, which represents an image. Rotate the matrix 90 degrees clockwise in place. This means modifying the matrix without using any extra space for another matrix.
Input:
[
[1, 2, 3],
[4, 5, 6],
[7, 8, 9]
]
Output:
[
[7, 4, 1],
[8, 5, 2],
[9, 6, 3]
]
Theory Behind the Solution
To rotate a matrix 90 degrees clockwise, we can break down the problem into two main steps:
1. Transpose the Matrix: Convert all the rows of the matrix into columns.
2. Reverse Each Row: Reverse the order of the elements in each row.
Step 1: Transpose the Matrix
Transposing a matrix means swapping elements across its main diagonal. For example:
Before Transposing:
1 2 3
4 5 6
7 8 9
After Transposing:
1 4 7
2 5 8
3 6 9
Step 2: Reverse Each Row
Once we have the transposed matrix, we need to reverse each row to achieve the desired 90-degree rotation:
Before Reversing Rows:
1 4 7
2 5 8
3 6 9
After Reversing Rows:
7 4 1
8 5 2
9 6 3
JavaScript Code Solution
Let’s implement this approach in JavaScript:
function rotateMatrix(matrix) {
const n = matrix.length;
// Step 1: Transpose the matrix
for (let i = 0; i < n; i++) {
for (let j = i; j < n; j++) {
// Swap elements across the diagonal
let temp = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = temp;
}
}
// Step 2: Reverse each row
for (let i = 0; i < n; i++) {
matrix[i].reverse();
}
return matrix;
}
// Example usage:
const image = [
[1, 2, 3],
[4, 5, 6],
[7, 8, 9]
];
console.log(rotateMatrix(image));
Explanation of the Code
1. Transpose Step:
• We iterate over the matrix and swap each element matrix[i][j] with matrix[j][i] for all i and j such that i < j. This rearranges the matrix into its transposed form.
• The outer loop iterates through all rows, while the inner loop starts from the current row index to avoid swapping back.
2. Reverse Each Row:
• We then use the built-in JavaScript reverse() function to reverse each row of the transposed matrix.
Output of the Code:
For an input matrix:
[
[1, 2, 3],
[4, 5, 6],
[7, 8, 9]
]
The rotated output will be:
[
[7, 4, 1],
[8, 5, 2],
[9, 6, 3]
]
Complexity Analysis
Time Complexity:
• Transpose Step: Transposing requires two nested loops iterating over an N x N matrix. This results in O(N²) time complexity.
• Reverse Step: Reversing each row involves a single loop that processes N elements in each of the N rows, leading to O(N²) complexity.
Thus, the total time complexity of the algorithm is O(N²).
Space Complexity:
• Since we are modifying the matrix in place without using any additional data structures proportional to the size of the matrix, the space complexity is O(1). We only use a few auxiliary variables for swapping elements.
Why Can’t We Improve the Transpose Step?
The transpose step requires touching every element of the matrix. Since an N x N matrix has N² elements, it’s mathematically impossible to transpose without accessing each element at least once. Thus, O(N²) is the best achievable complexity for this operation.
Conclusion
Rotating a matrix is a classic problem to test your understanding of matrix manipulation, in-place operations, and algorithm complexity. By breaking the problem into smaller steps (transposing and reversing rows), you can solve it efficiently using O(N²) time and O(1) space.
Call to Action
If you enjoyed this tutorial, don’t forget to like and share! Also, subscribe to our channel for more detailed coding tutorials and interview problem breakdowns.
Related Posts You May Like
• How to Reverse a Linked List in JavaScript
• Sorting Algorithms Visualized: A Step-by-Step Guide
• Understanding Graph Algorithms with JavaScript