Complexity

⏰ Time complexity: O(n^2)
🧺 Space complexity: O(n^2)

But as we are using lots of space, can we do better?

Method 2 - Four swap technique - layered looping

Intuition

Matrix rotation can also be viewed as a layer-by-layer process:

Each layer of the matrix resembles a square ring.
Elements move clockwise within the ring:
- Top → Right → Bottom → Left → Top.
By performing these swaps one element at a time, the rotation is achieved without extra space.

Approach

Identify concentric layers in the matrix (e.g., outermost layer, 2nd layer, etc.).
For each layer:
- Iterate over the top row of the layer (i indexes the columns).
- For each element in the top row:
  - Perform four swaps:
    - Top element → Right column.
    - Right column → Bottom row.
    - Bottom row → Left column.
    - Left column → Top row.
Repeat for all layers until the entire matrix is rotated.

Code

[{"language":"Java","code":"class Solution {\n    public void rotate(int[][] matrix) {\n        int n = matrix.length;\n        // Process each layer\n        for (int layer = 0; layer < n / 2; layer++) {\n            for (int i = layer; i < n - layer - 1; i++) { // For each element in the layer\n                // Save the top element\n                int top = matrix[layer][i];\n                \n                // Perform the four swaps\n                // Left -> Top\n                matrix[layer][i] = matrix[n - i - 1][layer];\n                \n                // Bottom -> Left\n                matrix[n - i - 1][layer] = matrix[n - layer - 1][n - i - 1];\n                \n                // Right -> Bottom\n                matrix[n - layer - 1][n - i - 1] = matrix[i][n - layer - 1];\n                \n                // Top -> Right\n                matrix[i][n - layer - 1] = top;\n            }\n        }\n    }\n}","lang":"java","html":"<pre class=\"shiki shiki-themes github-light github-dark\" style=\"background-color:#fff;--shiki-dark-bg:#24292e;color:#24292e;--shiki-dark:#e1e4e8\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">class</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> Solution</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> {</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">    public</span><span style=\"color:#D73A49;--shiki-dark:#F97583\"> void</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> rotate</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">(</span><span style=\"color:#D73A49;--shiki-dark:#F97583\">int</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">[][] </span><span style=\"color:#E36209;--shiki-dark:#FFAB70\">matrix</span><span style=\"color:#24292E;--shiki-dark:#E1E

Related Tags