@meta
title: Rotate matrix by 90 degrees
questionNo: 7
totalQuestions: 191
sheetLabel: Striver SDE Sheet
sourceLabel: TakeUForward
@endmeta

@page
tag: A
pageNo: 1 / 1
totalPages: 1
@endpage

@section
region: full
title: Problem Statement
content:
Given an N x N 2D integer matrix, rotate it by 90 degrees clockwise.
The rotation must be done in-place, meaning the input matrix itself should be modified directly.
Do not use another 2D matrix for the final optimal solution.
@endsection

@section
region: left
title: Examples
content:
Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [[7,4,1],[8,5,2],[9,6,3]]
Explanation: The first column becomes the first row, the second column becomes the second row, and so on.

---
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]]
Explanation: Every element moves from position (i, j) to (j, n - i - 1), giving a 90 degree clockwise rotation.
@endsection

@section
region: right
title: Custom Notes
content:
- Memory hook: Clockwise rotation = transpose + reverse every row.
- Formula hook: old position (i, j) goes to new position (j, n - i - 1).
- Mistake to avoid: Do not reverse columns after transpose; that gives anti-clockwise rotation.
- Mistake to avoid: During transpose, start j from i + 1, otherwise you may swap elements twice.
- Better than brute force because it avoids O(N²) extra space and satisfies the in-place condition.
@endsection

@section
region: full
title: Brute Force Approach : TC: O(N²), SC: O(N²)
badge: 1 / 3
content:
Algorithm: Use an extra matrix and place every element directly at its rotated position.
Pseudo:
- Create a new N x N matrix called rotated.
- Traverse every cell (i, j) of the original matrix.
- Put matrix[i][j] at rotated[j][n - i - 1].
- Copy rotated back into matrix if the original matrix must be modified.
Time: O(N²)
Space: O(N²)
Why mention it: This is the easiest baseline and helps understand the position-mapping formula.
@endsection

@section
region: full
title: Better Approach : TC: O(N²), SC: O(1)
badge: 2 / 3
content:
Algorithm: Rotate the matrix layer by layer using four-way swaps.
Pseudo:
- Treat the matrix as square layers from outside to inside.
- For each layer, move elements in groups of four.
- Store one value temporarily.
- Move left to top, bottom to left, right to bottom, and top to right.
- Continue until all layers are rotated.
Time: O(N²)
Space: O(1)
Interview line: This is in-place, but the index handling is more error-prone than transpose plus reverse.
@endsection

@section
region: full
title: Optimal Approach : TC: O(N²), SC: O(1)
badge: 3 / 3
content:
Algorithm: First transpose the matrix, then reverse every row.
Pseudo:
- Transpose the matrix by swapping matrix[i][j] with matrix[j][i] for j > i.
- After transposition, reverse each row.
- The matrix is now rotated 90 degrees clockwise.
Time: O(N²)
Space: O(1)
Key insight: Transpose converts rows into columns, and reversing each row fixes the order for clockwise rotation.
@endsection

@section
region: grid
title: PCode
badge: 1 / 3
codeLang: pseudo
content:
START
n = matrix.size
rotated = new n x n matrix

FOR i = 0 TO n - 1
    FOR j = 0 TO n - 1
        rotated[j][n - i - 1] = matrix[i][j]
    END FOR
END FOR

FOR i = 0 TO n - 1
    FOR j = 0 TO n - 1
        matrix[i][j] = rotated[i][j]
    END FOR
END FOR
END
@endsection

@section
region: grid
title: PCode
badge: 2 / 3
codeLang: pseudo
content:
START
n = matrix.size

FOR layer = 0 TO n / 2 - 1
    first = layer
    last = n - 1 - layer

    FOR i = first TO last - 1
        offset = i - first

        top = matrix[first][i]

        matrix[first][i] = matrix[last - offset][first]
        matrix[last - offset][first] = matrix[last][last - offset]
        matrix[last][last - offset] = matrix[i][last]
        matrix[i][last] = top
    END FOR
END FOR
END
@endsection

@section
region: grid
title: PCode
badge: 3 / 3
codeLang: pseudo
content:
START
n = matrix.size

FOR i = 0 TO n - 1
    FOR j = i + 1 TO n - 1
        SWAP matrix[i][j] WITH matrix[j][i]
    END FOR
END FOR

FOR i = 0 TO n - 1
    REVERSE matrix[i]
END FOR
END
@endsection