DSA-011 · Coordinate composition and in-place swaps

Rotate Image

Intermediate · Java 21 · Version 1 · editorial draft

Java reference and baseline verified on JDK 21: 1302 deterministic checks. Learner drafts are not executed.

Understand the problem

Rotate a square matrix 90 degrees clockwise in place, preserving the outer array and every row object.

matrix is non-null, square n×n with 0≤n≤300 and signed int entries. All rows are non-null, length n, and distinct objects; ragged, rectangular, aliased-row, or null inputs are outside the contract.
Return void. An original cell at (r,c) moves to (c,n-1-r). Preserve the outer and row identities; only values move. An empty matrix and a singleton remain valid.
Perform exactly one clockwise quarter-turn. The optimized implementation allocates no matrix or row replacement; no arithmetic is performed on cell values.

Examples

Input: [[1,2],[3,4]]
Output: [[3,1],[4,2]]
The first column becomes the first output row in bottom-to-top order.
Input: [[1,2,3],[4,5,6],[7,8,9]]
Output: [[7,4,1],[8,5,2],[9,6,3]]
The center stays fixed while corner and edge occurrences move.

Before you start

Array indexing and inclusive pointer bounds
Loop invariants and Java value versus reference semantics

Recognize the structure

The requested permutation has a coordinate formula. Compose two simple in-place involutions—transpose and row reversal—to realize that formula without overwriting unread sources.

Try before revealing

Hint 1

Write the destination coordinate of an arbitrary original cell.

Hint 2

Which two reflections compose to that mapping?

Hint 3

Transpose once across the main diagonal, then reverse every row.

Derive the solution

Reveal the baseline, optimized reasoning, and Java code

Copy to mapped coordinates

Allocate a square output, write output[c][n-1-r]=matrix[r][c], then copy values back into existing rows. On [[1,2],[3,4]], original 1 goes to (0,1), 2 to (1,1), 3 to (0,0), and 4 to (1,0), producing [[3,1],[4,2]]. This uses O(n²) time and O(n²) auxiliary space and exposes the exact mapping used by the oracle.

Improve the baseline

Find the destination

Clockwise rotation sends the old row number to a reversed column number: (r,c) becomes (c,n-1-r).

Transpose one triangle

Swap (r,c) and (c,r) only when c>r. Diagonal values already belong to themselves; processing both triangles would undo the transpose.

Reverse every row

After transposition, reverse column positions within each row using symmetric swaps. Row objects stay in their original outer-array slots.

Why it is correct

First permutation

The one-triangle swaps map every original coordinate (r,c) to (c,r), including the unchanged diagonal. Each off-diagonal pair is exchanged exactly once.

Composition

Row reversal maps (x,y) to (x,n-1-y). Composing it with the transpose gives (r,c)→(c,r)→(c,n-1-r), the required destination for every occurrence.

Termination and identity

Both loops have finite bounded ranges and each reversal shrinks its interval. Swaps preserve all values and references to the existing arrays. The empty and singleton ranges execute no effective swaps.

Complete Java reference and baseline

Save as Solution.java. Node definitions and imports are included where needed. The baseline is included for comparison; respect its input-size limits.

public final class Solution {
    public static void rotate(int[][] matrix) {
        int n = matrix.length;
        for (int r = 0; r < n; r++) for (int c = r + 1; c < n; c++) {
            int temporary = matrix[r][c];
            matrix[r][c] = matrix[c][r];
            matrix[c][r] = temporary;
        }
        for (int r = 0; r < n; r++) for (int left = 0, right = n - 1; left < right; left++, right--) {
            int temporary = matrix[r][left];
            matrix[r][left] = matrix[r][right];
            matrix[r][right] = temporary;
        }
    }
    public static void baseline(int[][] matrix) {
        int n = matrix.length;
        int[][] copy = new int[n][n];
        for (int r = 0; r < n; r++) for (int c = 0; c < n; c++) copy[c][n - 1 - r] = matrix[r][c];
        for (int r = 0; r < n; r++) System.arraycopy(copy[r], 0, matrix[r], 0, n);
    }
}

Read the meaningful blocks

c starts at r+1

This excludes the diagonal and avoids reversing a previous transpose swap.

Temporary storage

One int protects the overwritten value in each swap, regardless of duplicate values or extreme integers.

Reverse within rows

Swapping row references would reflect vertically and violate row identity; instead exchange the two entries inside a single row.

Complexity

O(n²) time for n(n-1)/2 transpose swaps and n floor(n/2) reversal swaps; O(1) auxiliary space. The mutated matrix is the output.

The mapped-copy baseline also takes O(n²) time but uses O(n²) extra cells. Rectangular rotation changes dimensions and cannot use this same square-array contract.

Exact-state walkthroughs

Reveal normal and boundary traces

Transpose, then reverse rows

Input: [[1,2,3],[4,5,6],[7,8,9]] · Final state: [[7,4,1],[8,5,2],[9,6,3]]

Step 1 of 9: Begin the square coordinate permutation.

All occurrences still occupy their original coordinates.

Matrix during clockwise rotation

123

456

789

A highlighted coordinate is the current cell; the state table records boundaries, flags, or output progress.

State after this step
Variable	Value
matrix	`[[1,2,3],[4,5,6],[7,8,9]]`

See the affected Java block

 1 public final class Solution {
 2     public static void rotate(int[][] matrix) {
 3         int n = matrix.length;
 4         for (int r = 0; r < n; r++) for (int c = r + 1; c < n; c++) {
 5             int temporary = matrix[r][c];
 6             matrix[r][c] = matrix[c][r];
 7             matrix[c][r] = temporary;
 8         }
 9         for (int r = 0; r < n; r++) for (int left = 0, right = n - 1; left < right; left++, right--) {
10             int temporary = matrix[r][left];
11             matrix[r][left] = matrix[r][right];
12             matrix[r][right] = temporary;
13         }
14     }
15     public static void baseline(int[][] matrix) {
16         int n = matrix.length;
17         int[][] copy = new int[n][n];
18         for (int r = 0; r < n; r++) for (int c = 0; c < n; c++) copy[c][n - 1 - r] = matrix[r][c];
19         for (int r = 0; r < n; r++) System.arraycopy(copy[r], 0, matrix[r], 0, n);
20     }
21 }
22

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Begin the square coordinate permutation.
All occurrences still occupy their original coordinates.
matrix
[[1,2,3],[4,5,6],[7,8,9]]
Exchange one pair across the diagonal.
Only the upper triangle owns transpose swaps, so no pair is undone.
phase
"transpose"
r
0
c
1
matrix
[[1,4,3],[2,5,6],[7,8,9]]
Exchange one pair across the diagonal.
Only the upper triangle owns transpose swaps, so no pair is undone.
phase
"transpose"
r
0
c
2
matrix
[[1,4,7],[2,5,6],[3,8,9]]
Exchange one pair across the diagonal.
Only the upper triangle owns transpose swaps, so no pair is undone.
phase
"transpose"
r
1
c
2
matrix
[[1,4,7],[2,5,8],[3,6,9]]
The transpose is complete.
Every original (r,c) now occupies (c,r).
phase
"transposed"
matrix
[[1,4,7],[2,5,8],[3,6,9]]
Reverse one symmetric pair within this row.
Transposed columns receive their clockwise reflected destinations without replacing row objects.
phase
"reverse"
r
0
left
0
right
2
matrix
[[7,4,1],[2,5,8],[3,6,9]]
Reverse one symmetric pair within this row.
Transposed columns receive their clockwise reflected destinations without replacing row objects.
phase
"reverse"
r
1
left
0
right
2
matrix
[[7,4,1],[8,5,2],[3,6,9]]
Reverse one symmetric pair within this row.
Transposed columns receive their clockwise reflected destinations without replacing row objects.
phase
"reverse"
r
2
left
0
right
2
matrix
[[7,4,1],[8,5,2],[9,6,3]]
Final in-place state; Java returns void.
All required values have been finalized under the declared contract.
result
[[7,4,1],[8,5,2],[9,6,3]]

Singleton fixed point

Input: [[7]] · Final state: [[7]]

Step 1 of 3: Begin the square coordinate permutation.

All occurrences still occupy their original coordinates.

Matrix during clockwise rotation

A highlighted coordinate is the current cell; the state table records boundaries, flags, or output progress.

State after this step
Variable	Value
matrix	`[[7]]`

See the affected Java block

 1 public final class Solution {
 2     public static void rotate(int[][] matrix) {
 3         int n = matrix.length;
 4         for (int r = 0; r < n; r++) for (int c = r + 1; c < n; c++) {
 5             int temporary = matrix[r][c];
 6             matrix[r][c] = matrix[c][r];
 7             matrix[c][r] = temporary;
 8         }
 9         for (int r = 0; r < n; r++) for (int left = 0, right = n - 1; left < right; left++, right--) {
10             int temporary = matrix[r][left];
11             matrix[r][left] = matrix[r][right];
12             matrix[r][right] = temporary;
13         }
14     }
15     public static void baseline(int[][] matrix) {
16         int n = matrix.length;
17         int[][] copy = new int[n][n];
18         for (int r = 0; r < n; r++) for (int c = 0; c < n; c++) copy[c][n - 1 - r] = matrix[r][c];
19         for (int r = 0; r < n; r++) System.arraycopy(copy[r], 0, matrix[r], 0, n);
20     }
21 }
22

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Begin the square coordinate permutation.
All occurrences still occupy their original coordinates.
matrix
[[7]]
The transpose is complete.
Every original (r,c) now occupies (c,r).
phase
"transposed"
matrix
[[7]]
Final in-place state; Java returns void.
All required values have been finalized under the declared contract.
result
[[7]]

Test the contract

Input: []
Output: []
No rows to access.
Input: [[7]]
Output: [[7]]
The only coordinate is fixed.
Input: [[1,1],[1,1]]
Output: [[1,1],[1,1]]
Value equality must not hide incorrect coordinate ownership in other tests.
Input: Four successive clockwise rotations
Output: Original matrix restored
A metamorphic check complements the direct coordinate oracle.

Common mistakes and counterexamples

Transpose every ordered pair

Counterexample: [[1,2],[3,4]] returns to its initial off-diagonal arrangement after both swaps.

Use c>r.

Reverse columns after transpose

Counterexample: [[1,2],[3,4]] becomes [[2,4],[1,3]], a counterclockwise turn.

Reverse each row for clockwise rotation.

Replace row objects

Counterexample: Assigning newly allocated rotated rows gives correct values but changes references held by a caller.

Copy values into the existing rows; test identities as well as values.

Follow-ups

Rotate counterclockwise.

Transpose then reverse each column, or reverse each row before transposing. Derive the resulting coordinate formula rather than guessing operation order.

Rotate a rectangular matrix.

Allocate an m-column by n-row result for an n×m source. The coordinate mapping is still (r,c)→(c,n-1-r), but the output type has different dimensions.

Use layer cycles.

For each square ring, move four corresponding entries with one saved value. Prove each cycle visits its four destinations once and avoid double-processing corners.

Your Java attempt

Java 21 · Draft only. Your code is not compiled, executed, or graded here. Run it locally against the examples and edge cases.

Saving stores text in this browser, visible to other people using this browser profile. It does not sync to your account. Loading is always explicit.

Approach, code, and test notes (20,000 characters maximum)

No unsaved text changes · 85/20,000 characters

Self-review

I can compose the coordinate maps.I transpose one triangle only.I preserve rows and test four-turn restoration.

Use the checklist to test your explanation. Checks apply to this visit.

Related foundations

Two pointers: eliminate with a proof

Keep practicing

Open focused practice

AceYourInterviews · 2026-10-15 · Original teaching content, examples, and Java implementations authored for AceYourInterviews. These standard algorithmic tasks carry no company-frequency or interview-outcome claims.