Solving LeetCode Problem 48: Rotate Image using JavaScript
Welcome back, fellow coding enthusiasts! Today, we’re going to dive into one of the interesting problems from LeetCode – Problem 48: Rotate Image. This problem challenges us to rotate an NxN 2D matrix (image) in place by 90 degrees clockwise. Let’s explore the problem statement, understand the approach, and implement the solution using JavaScript.
You are given an n x n 2D matrix representing an image, rotate the image by 90 degrees (clockwise).
You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.
Example 1:
Input: matrix = [[1,2,3],[4,5,6],[7,8,9]] Output: [[7,4,1],[8,5,2],[9,6,3]]
Example 2:
Input: matrix = [[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]]
Constraints:
n == matrix.length == matrix[i].length1 <= n <= 20-1000 <= matrix[i][j] <= 1000
Approach to solving leet code problem: rotate the image using JavaScript:
To solve this problem, we need to perform the rotation in layers. We start by rotating the outermost layer and then move toward the inner layers until we have turned the entire image.
Identify the number of layers: In an NxN matrix, there will be N/2 layers. For each layer, the rotation will be performed in a ring-like manner.
Rotate each layer: To rotate each layer, we take four elements at a time from each corner and rotate them in place. We repeat this process for each layer until we have rotated the entire image.
Implementation of LeetCode problem: rotate the image using JavaScript
function rotate(matrix) {
const n = matrix.length;
for (let layer = 0; layer < Math.floor(n / 2); layer++) {
const first = layer;
const last = n – 1 – layer;
for (let i = first; i < last; i++) {
const offset = i – first;
const top = matrix[first][i];
// Left to Top
matrix[first][i] = matrix[last – offset][first];
// Bottom to Left
matrix[last – offset][first] = matrix[last][last – offset];
// Right to Bottom
matrix[last][last – offset] = matrix[i][last];
// Top to Right
matrix[i][last] = top;
}
}
}
Explanation:
- The rotate function takes a 2D matrix as input and rotates it in place by 90 degrees clockwise.
- const n = matrix.length;: We calculate the size of the matrix (n x n) since it’s a square matrix.
- for (let layer = 0; layer < Math.floor(n / 2); layer++): We iterate through each layer of the matrix. We only need to go up to the middle layer (rounded down if n is odd) because the rest of the layers will be rotated along with the outer layers.
- const first = layer; const last = n – 1 – layer;: We define variables first and last to represent the indices of the first and last elements in the current layer.
- The inner loop starts with i at first and continues until i reaches last – 1.
- const offset = i – first; const top = matrix[first][i];: We calculate the offset to move from the current position i to the starting position first, and we store the value of the top element in the current layer in the variable top.
- matrix[first][i] = matrix[last – offset][first];: We move the left element to the top position.
- matrix[last – offset][first] = matrix[last][last – offset];: We move the bottom element to the left position.
- matrix[last][last – offset] = matrix[i][last];: We move the right element to the bottom position.
- matrix[i][last] = top;: We move the top element to the right position, completing the rotation of the current four elements.
- The process repeats for the entire layer, rotating all the elements in that layer.
- Once all the layers have been rotated, the function completes, and the matrix is now rotated 90 degrees clockwise in place.
Time Complexity:
The time complexity of the rotate function is O(N^2), where N is the number of rows (or columns) in the square matrix.
The function uses two nested loops: the outer loop runs through the layers (N/2 layers), and the inner loop iterates through the elements in each layer (4 elements per layer).
Since the number of elements in each layer is constant (4), the overall time complexity is proportional to the number of layers, which is N/2. Therefore, the time complexity is O(N^2).
Space Complexity:
The space complexity of the rotate function is O(1) – constant space complexity.
The algorithm performs the rotation in place without using any additional data structures that grow with the size of the input.
The variables used within the function, such as n, layer, first, last, i, offset, and top, occupy constant space, irrespective of the size of the matrix.
Conclusion:
Congratulations! You’ve successfully solved LeetCode Problem 48, Rotate Image, using JavaScript. We implemented an algorithm that rotates an NxN matrix in place by 90 degrees clockwise.
This problem teaches us about working with 2D arrays, identifying layers in matrices, and using loops to perform rotations effectively.
Keep practicing such coding challenges to enhance your problem-solving skills, and I’ll see you in the next blog post with more exciting coding adventures! Happy coding!
Oh my goodness! an amazing article dude. Thanks Nevertheless I’m experiencing situation with ur rss . Don’t know why Unable to subscribe to it. Is there anyone getting an identical rss downside? Anyone who knows kindly respond. Thnkx
My husband and i ended up being now ecstatic when Emmanuel managed to finish up his homework from the precious recommendations he came across through the web page. It is now and again perplexing to just choose to be releasing helpful hints which usually many others might have been trying to sell. And now we grasp we need the blog owner to thank because of that. All of the explanations you have made, the straightforward website navigation, the relationships you will aid to create – it’s mostly great, and it’s really aiding our son and us recognize that this subject matter is enjoyable, which is tremendously serious. Thank you for all the pieces!