DSA-010 · Shrinking matrix boundaries
Spiral Matrix
Intermediate · Java 21 · Version 1 · editorial draft
Java reference and baseline verified on JDK 21: 445 deterministic checks. Learner drafts are not executed.
Understand the problem
Return every matrix value in clockwise spiral order, starting at the top-left and initially moving right. Preserve the matrix and retain repeated values as separate occurrences.
- matrix is non-null and rectangular with 0–100 rows and 0–100 columns. Rows are non-null and entries are signed ints.
- Return List<Integer> containing exactly R×C entries in the stated traversal order. Empty or zero-column matrices return an empty list.
- Preserve input values and row references. The optimized method uses O(1) auxiliary boundary indices, excluding the O(RC) returned list.
Examples
Input:
[[1,2,3],[4,5,6],[7,8,9]]
Output:[1,2,3,6,9,8,7,4,5]Visit the outer perimeter clockwise, then the remaining center.
Input:
[[1,2,3,4],[5,6,7,8],[9,10,11,12]]
Output:[1,2,3,4,8,12,11,10,9,5,6,7]After removing the outer ring, the final remaining row is read once.
Before you start
- Rectangular index bounds and inclusive ranges
- Separate visited cells from the remaining rectangle
Recognize the structure
After an outer perimeter is consumed, the unvisited cells still form a smaller rectangle. Four boundary indices can represent that rectangle, avoiding a visited matrix. This works because the traversal geometry is a complete rectangle, not a grid with obstacles.
Try before revealing
Hint 1
What shape remains after removing one complete outer perimeter?
Hint 2
Represent the unvisited rectangle by four bounds.
Hint 3
Consume each edge once, shrink immediately, and guard a collapsed final row or column.
Derive the solution
Reveal the baseline, optimized reasoning, and Java code
Simulate direction and visited state
Keep a visited[R][C] matrix and move right, down, left, up in cycle. After emitting a cell, turn when the next position is out of bounds or already visited. Emit exactly RC cells. On a 2×2 grid the walk visits (0,0),(0,1),(1,1),(1,0). This costs O(RC) time, O(RC) visited storage, and O(RC) output.
Improve the baseline
Represent only the remaining rectangle
Keep inclusive top, bottom, left, right boundaries. The while condition requires a nonempty rectangle in both dimensions.
Consume edges and shrink immediately
Emit the top row and increment top; emit the right column and decrement right. These updates keep later edges from re-emitting their corner cells.
Recheck collapsed dimensions
Only emit the bottom row if top≤bottom and the left column if left≤right. A final single row or column must not be walked twice. Shrink those boundaries after their edges are handled.
Why it is correct
Initialization
The full rectangle contains exactly the unvisited cells and the output is empty.
Preservation
Each edge walk uses only the current inclusive bounds, then removes that edge from the remaining rectangle. Earlier corner removals and collapse guards prevent overlap between edges. The output therefore contains each removed coordinate once in clockwise order.
Termination and coverage
Every active round removes at least one row or column. When either dimension is exhausted, no unvisited coordinate remains. Thus the output contains all RC positions exactly once; repeated numeric values are retained because ownership is by coordinate.
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.
import java.util.ArrayList;
import java.util.List;
public final class Solution {
public static List<Integer> spiralOrder(int[][] matrix) {
List<Integer> result = new ArrayList<>();
int top = 0, bottom = matrix.length - 1;
int left = 0, right = matrix.length == 0 ? -1 : matrix[0].length - 1;
while (top <= bottom && left <= right) {
for (int c = left; c <= right; c++) result.add(matrix[top][c]);
top++;
for (int r = top; r <= bottom; r++) result.add(matrix[r][right]);
right--;
if (top <= bottom) {
for (int c = right; c >= left; c--) result.add(matrix[bottom][c]);
bottom--;
}
if (left <= right) {
for (int r = bottom; r >= top; r--) result.add(matrix[r][left]);
left++;
}
}
return result;
}
public static List<Integer> baseline(int[][] matrix) {
List<Integer> result = new ArrayList<>();
int rows = matrix.length, cols = rows == 0 ? 0 : matrix[0].length;
if (rows == 0 || cols == 0) return result;
boolean[][] visited = new boolean[rows][cols];
int[][] directions = {{0,1},{1,0},{0,-1},{-1,0}};
int r = 0, c = 0, direction = 0;
for (int count = 0; count < rows * cols; count++) {
result.add(matrix[r][c]); visited[r][c] = true;
int nr = r + directions[direction][0], nc = c + directions[direction][1];
if (nr < 0 || nr >= rows || nc < 0 || nc >= cols || visited[nr][nc]) {
direction = (direction + 1) % 4;
nr = r + directions[direction][0]; nc = c + directions[direction][1];
}
r = nr; c = nc;
}
return result;
}
}
Read the meaningful blocks
Compute an empty right bound safely
Zero rows must not read matrix[0]; zero columns produce right=-1, preventing any edge access.
Advance boundaries between edge walks
Updating only at the end of a ring can duplicate corners.
Guard the last two sides
Thin residual rectangles need fresh dimension checks after top and right have moved.
Complexity
O(RC) time, O(1) auxiliary boundary state, and O(RC) separately counted output storage. Each coordinate is emitted once.
The direction-simulation baseline has the same time/output size but adds O(RC) visited flags. Neither method mutates the matrix.
Exact-state walkthroughs
Reveal normal and boundary traces
Peel the outer ring
Input: [[1,2,3],[4,5,6],[7,8,9]] · Result: [1,2,3,6,9,8,7,4,5]
Step 1 of 17: Initialize the inclusive remaining rectangle.
No coordinate has been emitted.
A highlighted coordinate is the current cell; the state table records boundaries, flags, or output progress.
| Variable | Value |
|---|---|
| sourceMatrix | [[1,2,3],[4,5,6],[7,8,9]] |
| top | 0 |
| bottom | 2 |
| left | 0 |
| right | 2 |
| resultValues | [] |
| visitedCoordinates | [] |
See the affected Java block
1 import java.util.ArrayList; 2 import java.util.List; 3 public final class Solution { 4 public static List<Integer> spiralOrder(int[][] matrix) { 5 List<Integer> result = new ArrayList<>(); 6 int top = 0, bottom = matrix.length - 1; 7 int left = 0, right = matrix.length == 0 ? -1 : matrix[0].length - 1; 8 while (top <= bottom && left <= right) { 9 for (int c = left; c <= right; c++) result.add(matrix[top][c]); 10 top++; 11 for (int r = top; r <= bottom; r++) result.add(matrix[r][right]); 12 right--; 13 if (top <= bottom) { 14 for (int c = right; c >= left; c--) result.add(matrix[bottom][c]); 15 bottom--; 16 } 17 if (left <= right) { 18 for (int r = bottom; r >= top; r--) result.add(matrix[r][left]); 19 left++; 20 } 21 } 22 return result; 23 } 24 public static List<Integer> baseline(int[][] matrix) { 25 List<Integer> result = new ArrayList<>(); 26 int rows = matrix.length, cols = rows == 0 ? 0 : matrix[0].length; 27 if (rows == 0 || cols == 0) return result; 28 boolean[][] visited = new boolean[rows][cols]; 29 int[][] directions = {{0,1},{1,0},{0,-1},{-1,0}}; 30 int r = 0, c = 0, direction = 0; 31 for (int count = 0; count < rows * cols; count++) { 32 result.add(matrix[r][c]); visited[r][c] = true; 33 int nr = r + directions[direction][0], nc = c + directions[direction][1]; 34 if (nr < 0 || nr >= rows || nc < 0 || nc >= cols || visited[nr][nc]) { 35 direction = (direction + 1) % 4; 36 nr = r + directions[direction][0]; nc = c + directions[direction][1]; 37 } 38 r = nr; c = nc; 39 } 40 return result; 41 } 42 } 43
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Initialize the inclusive remaining rectangle.
No coordinate has been emitted.
- sourceMatrix
[[1,2,3],[4,5,6],[7,8,9]]- top
0- bottom
2- left
0- right
2- resultValues
[]- visitedCoordinates
[]
- Emit one coordinate on the current clockwise edge.
Coordinate ownership, not value uniqueness, prevents duplicate output.
- sourceMatrix
[[1,2,3],[4,5,6],[7,8,9]]- top
0- bottom
2- left
0- right
2- resultValues
[1]- visitedCoordinates
[[0,0]]- r
0- c
0
- Emit one coordinate on the current clockwise edge.
Coordinate ownership, not value uniqueness, prevents duplicate output.
- sourceMatrix
[[1,2,3],[4,5,6],[7,8,9]]- top
0- bottom
2- left
0- right
2- resultValues
[1,2]- visitedCoordinates
[[0,0],[0,1]]- r
0- c
1
- Emit one coordinate on the current clockwise edge.
Coordinate ownership, not value uniqueness, prevents duplicate output.
- sourceMatrix
[[1,2,3],[4,5,6],[7,8,9]]- top
0- bottom
2- left
0- right
2- resultValues
[1,2,3]- visitedCoordinates
[[0,0],[0,1],[0,2]]- r
0- c
2
- Remove the consumed top edge.
The remaining top boundary excludes all top-edge coordinates already emitted.
- sourceMatrix
[[1,2,3],[4,5,6],[7,8,9]]- top
1- bottom
2- left
0- right
2- resultValues
[1,2,3]- visitedCoordinates
[[0,0],[0,1],[0,2]]
- Emit one coordinate on the current clockwise edge.
Coordinate ownership, not value uniqueness, prevents duplicate output.
- sourceMatrix
[[1,2,3],[4,5,6],[7,8,9]]- top
1- bottom
2- left
0- right
2- resultValues
[1,2,3,6]- visitedCoordinates
[[0,0],[0,1],[0,2],[1,2]]- r
1- c
2
- Emit one coordinate on the current clockwise edge.
Coordinate ownership, not value uniqueness, prevents duplicate output.
- sourceMatrix
[[1,2,3],[4,5,6],[7,8,9]]- top
1- bottom
2- left
0- right
2- resultValues
[1,2,3,6,9]- visitedCoordinates
[[0,0],[0,1],[0,2],[1,2],[2,2]]- r
2- c
2
- Remove the consumed right edge.
The next side cannot repeat the top-right corner.
- sourceMatrix
[[1,2,3],[4,5,6],[7,8,9]]- top
1- bottom
2- left
0- right
1- resultValues
[1,2,3,6,9]- visitedCoordinates
[[0,0],[0,1],[0,2],[1,2],[2,2]]
- Emit one coordinate on the current clockwise edge.
Coordinate ownership, not value uniqueness, prevents duplicate output.
- sourceMatrix
[[1,2,3],[4,5,6],[7,8,9]]- top
1- bottom
2- left
0- right
1- resultValues
[1,2,3,6,9,8]- visitedCoordinates
[[0,0],[0,1],[0,2],[1,2],[2,2],[2,1]]- r
2- c
1
- Emit one coordinate on the current clockwise edge.
Coordinate ownership, not value uniqueness, prevents duplicate output.
- sourceMatrix
[[1,2,3],[4,5,6],[7,8,9]]- top
1- bottom
2- left
0- right
1- resultValues
[1,2,3,6,9,8,7]- visitedCoordinates
[[0,0],[0,1],[0,2],[1,2],[2,2],[2,1],[2,0]]- r
2- c
0
- Remove a still-present bottom edge.
The guard prevents re-emitting a collapsed single row.
- sourceMatrix
[[1,2,3],[4,5,6],[7,8,9]]- top
1- bottom
1- left
0- right
1- resultValues
[1,2,3,6,9,8,7]- visitedCoordinates
[[0,0],[0,1],[0,2],[1,2],[2,2],[2,1],[2,0]]
- Emit one coordinate on the current clockwise edge.
Coordinate ownership, not value uniqueness, prevents duplicate output.
- sourceMatrix
[[1,2,3],[4,5,6],[7,8,9]]- top
1- bottom
1- left
0- right
1- resultValues
[1,2,3,6,9,8,7,4]- visitedCoordinates
[[0,0],[0,1],[0,2],[1,2],[2,2],[2,1],[2,0],[1,0]]- r
1- c
0
- Remove a still-present left edge.
The guard prevents re-emitting a collapsed single column.
- sourceMatrix
[[1,2,3],[4,5,6],[7,8,9]]- top
1- bottom
1- left
1- right
1- resultValues
[1,2,3,6,9,8,7,4]- visitedCoordinates
[[0,0],[0,1],[0,2],[1,2],[2,2],[2,1],[2,0],[1,0]]
- Emit one coordinate on the current clockwise edge.
Coordinate ownership, not value uniqueness, prevents duplicate output.
- sourceMatrix
[[1,2,3],[4,5,6],[7,8,9]]- top
1- bottom
1- left
1- right
1- resultValues
[1,2,3,6,9,8,7,4,5]- visitedCoordinates
[[0,0],[0,1],[0,2],[1,2],[2,2],[2,1],[2,0],[1,0],[1,1]]- r
1- c
1
- Remove the consumed top edge.
The remaining top boundary excludes all top-edge coordinates already emitted.
- sourceMatrix
[[1,2,3],[4,5,6],[7,8,9]]- top
2- bottom
1- left
1- right
1- resultValues
[1,2,3,6,9,8,7,4,5]- visitedCoordinates
[[0,0],[0,1],[0,2],[1,2],[2,2],[2,1],[2,0],[1,0],[1,1]]
- Remove the consumed right edge.
The next side cannot repeat the top-right corner.
- sourceMatrix
[[1,2,3],[4,5,6],[7,8,9]]- top
2- bottom
1- left
1- right
0- resultValues
[1,2,3,6,9,8,7,4,5]- visitedCoordinates
[[0,0],[0,1],[0,2],[1,2],[2,2],[2,1],[2,0],[1,0],[1,1]]
- Return the contract result.
The completed state satisfies the declared output and mutation contract.
- result
[1,2,3,6,9,8,7,4,5]
A single remaining column
Input: [[7],[8],[9]] · Result: [7,8,9]
Step 1 of 8: Initialize the inclusive remaining rectangle.
No coordinate has been emitted.
A highlighted coordinate is the current cell; the state table records boundaries, flags, or output progress.
| Variable | Value |
|---|---|
| sourceMatrix | [[7],[8],[9]] |
| top | 0 |
| bottom | 2 |
| left | 0 |
| right | 0 |
| resultValues | [] |
| visitedCoordinates | [] |
See the affected Java block
1 import java.util.ArrayList; 2 import java.util.List; 3 public final class Solution { 4 public static List<Integer> spiralOrder(int[][] matrix) { 5 List<Integer> result = new ArrayList<>(); 6 int top = 0, bottom = matrix.length - 1; 7 int left = 0, right = matrix.length == 0 ? -1 : matrix[0].length - 1; 8 while (top <= bottom && left <= right) { 9 for (int c = left; c <= right; c++) result.add(matrix[top][c]); 10 top++; 11 for (int r = top; r <= bottom; r++) result.add(matrix[r][right]); 12 right--; 13 if (top <= bottom) { 14 for (int c = right; c >= left; c--) result.add(matrix[bottom][c]); 15 bottom--; 16 } 17 if (left <= right) { 18 for (int r = bottom; r >= top; r--) result.add(matrix[r][left]); 19 left++; 20 } 21 } 22 return result; 23 } 24 public static List<Integer> baseline(int[][] matrix) { 25 List<Integer> result = new ArrayList<>(); 26 int rows = matrix.length, cols = rows == 0 ? 0 : matrix[0].length; 27 if (rows == 0 || cols == 0) return result; 28 boolean[][] visited = new boolean[rows][cols]; 29 int[][] directions = {{0,1},{1,0},{0,-1},{-1,0}}; 30 int r = 0, c = 0, direction = 0; 31 for (int count = 0; count < rows * cols; count++) { 32 result.add(matrix[r][c]); visited[r][c] = true; 33 int nr = r + directions[direction][0], nc = c + directions[direction][1]; 34 if (nr < 0 || nr >= rows || nc < 0 || nc >= cols || visited[nr][nc]) { 35 direction = (direction + 1) % 4; 36 nr = r + directions[direction][0]; nc = c + directions[direction][1]; 37 } 38 r = nr; c = nc; 39 } 40 return result; 41 } 42 } 43
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Initialize the inclusive remaining rectangle.
No coordinate has been emitted.
- sourceMatrix
[[7],[8],[9]]- top
0- bottom
2- left
0- right
0- resultValues
[]- visitedCoordinates
[]
- Emit one coordinate on the current clockwise edge.
Coordinate ownership, not value uniqueness, prevents duplicate output.
- sourceMatrix
[[7],[8],[9]]- top
0- bottom
2- left
0- right
0- resultValues
[7]- visitedCoordinates
[[0,0]]- r
0- c
0
- Remove the consumed top edge.
The remaining top boundary excludes all top-edge coordinates already emitted.
- sourceMatrix
[[7],[8],[9]]- top
1- bottom
2- left
0- right
0- resultValues
[7]- visitedCoordinates
[[0,0]]
- Emit one coordinate on the current clockwise edge.
Coordinate ownership, not value uniqueness, prevents duplicate output.
- sourceMatrix
[[7],[8],[9]]- top
1- bottom
2- left
0- right
0- resultValues
[7,8]- visitedCoordinates
[[0,0],[1,0]]- r
1- c
0
- Emit one coordinate on the current clockwise edge.
Coordinate ownership, not value uniqueness, prevents duplicate output.
- sourceMatrix
[[7],[8],[9]]- top
1- bottom
2- left
0- right
0- resultValues
[7,8,9]- visitedCoordinates
[[0,0],[1,0],[2,0]]- r
2- c
0
- Remove the consumed right edge.
The next side cannot repeat the top-right corner.
- sourceMatrix
[[7],[8],[9]]- top
1- bottom
2- left
0- right
-1- resultValues
[7,8,9]- visitedCoordinates
[[0,0],[1,0],[2,0]]
- Remove a still-present bottom edge.
The guard prevents re-emitting a collapsed single row.
- sourceMatrix
[[7],[8],[9]]- top
1- bottom
1- left
0- right
-1- resultValues
[7,8,9]- visitedCoordinates
[[0,0],[1,0],[2,0]]
- Return the contract result.
The completed state satisfies the declared output and mutation contract.
- result
[7,8,9]
Test the contract
Input:
[]
Output:[]Empty.
Input:
[[]]
Output:[]Zero columns.
Input:
[[1,2,3]]
Output:[1,2,3]One row.
Input:
[[1],[2],[3]]
Output:[1,2,3]One column.
Input:
[[7,7],[7,7]]
Output:[7,7,7,7]All occurrences retained.
Common mistakes and counterexamples
Emit all four sides unconditionally
Counterexample: [[1,2,3]] would duplicate its only row.
Recheck remaining dimensions before bottom and left walks.
Check only one dimension in the outer loop
Counterexample: A tall single-column matrix can exhaust columns first.
Require both top≤bottom and left≤right.
Deduplicate repeated values
Counterexample: [[7,7]] must return [7,7].
Track traversal by coordinates, not numeric-value membership.
Follow-ups
Generate an n×n spiral matrix.
Use the same coordinate traversal but assign increasing values instead of reading them. Define the starting value and direction before coding.
Traverse a grid with obstacles.
The unvisited region need not remain rectangular, so four boundaries are insufficient. Specify the desired walk policy and use explicit state/visited handling.
Provide a lazy iterator.
Store bounds, current side, and position between calls, emitting one value at a time. It reduces retained output memory but must still handle corner transitions and exhausted dimensions exactly.
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.
No unsaved text changes · 117/20,000 characters
Self-review
Use the checklist to test your explanation. Checks apply to this visit.
Related foundations
Review the prerequisites above and the related problems below.