Hard · simulation
Spiral Order
Peel the grid like an onion: print the top row, then the right column, then the bottom row backwards, then the left column upwards — and after each of the last two, ask whether there is anything left to peel. The question is the whole difficulty.
At a glanceKeep <code>top/bottom/left/right</code>; sweep the top row, the right column, then the bottom row backwards and the left column upwards — but only <em>if</em> rows and columns still remain.
Problem
Input: The first line has n and m (1 ≤ n, m ≤ 10). Then n lines of m integers (−100 to 100).
Output: The spiral traversal starting at the top-left corner going right, values separated by single spaces on one line.
Samples:
| Input | Output |
|---|---|
3 3 | 1 2 3 6 9 8 7 4 5 |
1 4 | 1 2 3 4 |
The single-row sample is there for a reason: after the top sweep, top exceeds bottom, so the bottom-row sweep must be skipped entirely — or the row prints twice. The judge's second sample is the trap detector.
Your solution
Custom input for "Run my input"
Judging runs in your browser against hidden tests. A runaway loop is cut off after 3 seconds — still, make sure every loop has an exit. Your code is saved in this browser as you type.
Stuck? Hints
Hint 1 — One lap = four sweeps
Top row left→right, right column top→bottom, bottom row right→left, left column bottom→top. After each sweep, shrink the corresponding boundary: top++, right--, bottom--, left++. Loop while top <= bottom && left <= right — when the ranges cross, the onion is finished.
Hint 2 — The two re-checks are the problem
After top++, the bottom row may no longer exist (single-row grids, or the spiral ending on a horizontal strip) — guard the bottom sweep with if (top <= bottom). Symmetrically, guard the left sweep with if (left <= right). Without these two, the judge's single-row and single-column tests fail by double-visits.
Hint 3 — Trace a non-square by hand
Square grids hide boundary bugs beautifully — everything closes up neatly. A 2×3 and a 3×2 traced once on paper expose every mistake in the four loops. If your spiral works on squares but fails the judge, this is why.
Solution (try it first!)
#include <iostream>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
int a[12][12];
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
cin >> a[i][j];
int top = 0, bottom = n - 1, left = 0, right = m - 1;
bool first = true;
while (top <= bottom && left <= right) {
for (int j = left; j <= right; j++) {
if (!first) cout << " ";
cout << a[top][j]; first = false;
}
top++;
for (int i = top; i <= bottom; i++) {
if (!first) cout << " ";
cout << a[i][right]; first = false;
}
right--;
if (top <= bottom) {
for (int j = right; j >= left; j--) {
if (!first) cout << " ";
cout << a[bottom][j]; first = false;
}
bottom--;
}
if (left <= right) {
for (int i = bottom; i >= top; i--) {
if (!first) cout << " ";
cout << a[i][left]; first = false;
}
left++;
}
}
cout << endl;
return 0;
}Boundary-shrinking simulation is the skeleton behind rotation, traversal and flood-fill style grid problems. Compare it with the other way you have handled grids — whole-row reindexing in Matrix Transpose — and notice the difference: transposition moves indices, the spiral moves *edges*. The next grid skill after both is asking questions about rectangles: 2D Range Sums.
Deep dive
Why this works
Four boundaries (top/bottom/left/right) define the unvisited ring; each lap prints one full revolution and shrinks one boundary per sweep. The two re-checks after shrinking exist because a ring can be one row or one column thin — printing its bottom then left would walk the same cells twice.
The cost
O(n·m): every cell is printed exactly once, and the boundary arithmetic is constant per sweep. Space O(1) beyond the grid itself.
Where it goes wrong
- Missing the
if (top <= bottom)guard before the bottom sweep (or the left guard): single-row and single-column grids print twice — the judge's non-square tests exist for exactly this. - Sweeping the bottom row left→right or the left column top→bottom: the spiral direction alternates, and reversed loops (
j--,i--) are mandatory on the second half of each lap. - Trusting square tests: 3×3 closes up neatly and hides every bug. Only 2×3 and 3×2 traced by hand expose the four loop bounds.
Next step
Grid handling so far: reindex rows in Matrix Transpose, combine grids in Matrix Multiplication, walk edges here. Then ask questions about rectangles: 2D Range Sums.
Two things to remember
- One lap = four sweeps; after each, shrink that boundary.
- The two re-checks (rows left? columns left?) are what non-square tests buy.
🐞 This version fails — open it and try
No re-checks before the bottom and left sweeps — single rows print twice
#include <iostream>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
int a[12][12];
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
cin >> a[i][j];
int top = 0, bottom = n - 1, left = 0, right = m - 1;
bool first = true;
while (top <= bottom && left <= right) {
for (int j = left; j <= right; j++) { if (!first) cout << " "; cout << a[top][j]; first = false; }
top++;
for (int i = top; i <= bottom; i++) { if (!first) cout << " "; cout << a[i][right]; first = false; }
right--;
for (int j = right; j >= left; j--) { if (!first) cout << " "; cout << a[bottom][j]; first = false; } // bug: no guard
bottom--;
for (int i = bottom; i >= top; i--) { if (!first) cout << " "; cout << a[i][left]; first = false; } // bug: no guard
left++;
}
cout << endl;
return 0;
}