Your Web News in One Place

Help Webnuz

Referal links:

Sign up for GreenGeeks web hosting
April 25, 2021 08:11 am GMT

Solution: Rotate Image

This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful, please like this post and/or upvote my solution post on Leetcode's forums.

Leetcode Problem #48 (Medium): Rotate Image

Description:


(Jump to: Solution Idea || Code: JavaScript | Python | Java | C++)

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.

Examples:

Example 1:
Input:matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output:[[7,4,1],[8,5,2],[9,6,3]]
Visual:Example 1 Visual
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]]
Visual:Example 1 Visual
Example 3:
Input:matrix = [[1]]
Output:[[1]]
Example 4:
Input:matrix = [[1,2],[3,4]]
Output:[[3,1],[4,2]]

Constraints:

  • matrix.length == n
  • matrix[i].length == n
  • 1 <= n <= 20
  • -1000 <= matrix[i][j] <= 1000

Idea:


(Jump to: Problem Description || Code: JavaScript | Python | Java | C++)

The trick here is to realize that cells in our matrix (M) can be swapped out in groups of four in a self-contained manner. This will allow us to keep our space complexity down to O(1).

The remaining difficulty lies in setting up our nested for loops to accomplish the entirety of these four-way swaps. If we consider each ring of data as a larger iteration, we can notice that each successive ring shortens in the length of its side by 2. This means that we will need to perform this process to a maximum depth of floor(n / 2) times. We can use floor here because the center cell of an odd-sided matrix will not need to be swapped.

For each ring, we'll need to perform a number of iterations equal to the length of the side minus 1, since we will have already swapped the far corner as our first iteration. As noticed earlier, the length of the side of a ring is shortened by 2 for each layer of depth we've achieved (len = n - 2 * i - 1).

Inside the nested for loops, we need to perform a four-way swap between the linked cells. In order to save on some processing, we can store the value of the opposite side of i (opp = n - 1 - i) as that value will be reused many times over.

Visual 1

Once the nested loops are finished, M has been successfully transformed in-place.

  • Time Complexity: O(N^2) where N is the length of each side of the matrix
  • Space Complexity: O(1)

Implementation:

There are only minor differences between the code of all four languages.

Javascript Code:


(Jump to: Problem Description || Solution Idea)

var rotate = function(M) {    let n = M.length, depth = ~~(n / 2)    for (let i = 0; i < depth; i++) {        let len = n - 2 * i - 1, opp = n - 1 - i        for (let j = 0; j < len; j++) {            let temp = M[i][i+j]            M[i][i+j] = M[opp-j][i]            M[opp-j][i] = M[opp][opp-j]            M[opp][opp-j] = M[i+j][opp]            M[i+j][opp] = temp        }    }};

Python Code:


(Jump to: Problem Description || Solution Idea)

class Solution:    def rotate(self, M: List[List[int]]) -> None:        n = len(M)        depth = n // 2        for i in range(depth):            rlen, opp = n - 2 * i - 1, n - 1 - i            for j in range(rlen):                temp = M[i][i+j]                M[i][i+j] = M[opp-j][i]                M[opp-j][i] = M[opp][opp-j]                M[opp][opp-j] = M[i+j][opp]                M[i+j][opp] = temp

Java Code:


(Jump to: Problem Description || Solution Idea)

class Solution {    public void rotate(int[][] M) {        int n = M.length, depth = n / 2;        for (int i = 0; i < depth; i++) {            int len = n - 2 * i - 1, opp = n - 1 - i;            for (int j = 0; j < len; j++) {                int temp = M[i][i+j];                M[i][i+j] = M[opp-j][i];                M[opp-j][i] = M[opp][opp-j];                M[opp][opp-j] = M[i+j][opp];                M[i+j][opp] = temp;            }        }    }}

C++ Code:


(Jump to: Problem Description || Solution Idea)

class Solution {public:    void rotate(vector<vector<int>>& M) {        int n = M.size(), depth = n / 2;        for (int i = 0; i < depth; i++) {            int len = n - 2 * i - 1, opp = n - 1 - i;            for (int j = 0; j < len; j++) {                int temp = M[i][i+j];                M[i][i+j] = M[opp-j][i];                M[opp-j][i] = M[opp][opp-j];                M[opp][opp-j] = M[i+j][opp];                M[i+j][opp] = temp;            }        }    }};

Original Link: https://dev.to/seanpgallivan/solution-rotate-image-cpp

Share this article:    Share on Facebook
View Full Article

Dev To

An online community for sharing and discovering great ideas, having debates, and making friends

More About this Source Visit Dev To