Practice › Arrays
Spiral Matrix
Medium · Arrays · Asked at Amazon, Microsoft, Google, Paytm
Print all elements of an r × c matrix in spiral order (right, down, left, up, repeat).
Input
First line: r c. Next r lines: c integers each.
Output
All elements in spiral order, space-separated.
Constraints
- 1 ≤ r, c ≤ 100
Example 1
Input
3 3 1 2 3 4 5 6 7 8 9
Output
1 2 3 6 9 8 7 4 5
Example 2
Input
3 4 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
Hints
- Keep four boundaries: top, bottom, left and right.
- Walk the top row, right column, bottom row (if any left) and left column (if any left), then shrink the boundaries.
Approach
Maintain top, bottom, left, right. Each loop prints one ring: the top row left→right (then top++), the right column top→bottom (right--), the bottom row right→left if top <= bottom (bottom--), and the left column bottom→top if left <= right (left++). The two checks stop a single remaining row or column from being printed twice.
Complexity: O(r·c) time · O(1) extra space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int r, c;
cin >> r >> c;
vector<vector<long long>> m(r, vector<long long>(c));
for (auto &row : m)
for (auto &x : row) cin >> x;
vector<long long> out;
int top = 0, bottom = r - 1, left = 0, right = c - 1;
while (top <= bottom && left <= right) {
for (int j = left; j <= right; j++) out.push_back(m[top][j]);
top++;
for (int i = top; i <= bottom; i++) out.push_back(m[i][right]);
right--;
if (top <= bottom) {
for (int j = right; j >= left; j--) out.push_back(m[bottom][j]);
bottom--;
}
if (left <= right) {
for (int i = bottom; i >= top; i--) out.push_back(m[i][left]);
left++;
}
}
for (size_t i = 0; i < out.size(); i++) cout << out[i] << (i + 1 < out.size() ? " " : "\n");
return 0;
}Python solution
import sys
data = list(map(int, sys.stdin.read().split()))
r, c = data[0], data[1]
m = [data[2 + i * c : 2 + (i + 1) * c] for i in range(r)]
out = []
top, bottom, left, right = 0, r - 1, 0, c - 1
while top <= bottom and left <= right:
out += m[top][left : right + 1]
top += 1
out += [m[i][right] for i in range(top, bottom + 1)]
right -= 1
if top <= bottom:
out += m[bottom][left : right + 1][::-1]
bottom -= 1
if left <= right:
out += [m[i][left] for i in range(bottom, top - 1, -1)]
left += 1
print(*out)Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int r = sc.nextInt(), c = sc.nextInt();
long[][] m = new long[r][c];
for (int i = 0; i < r; i++)
for (int j = 0; j < c; j++) m[i][j] = sc.nextLong();
StringBuilder sb = new StringBuilder();
int top = 0, bottom = r - 1, left = 0, right = c - 1;
while (top <= bottom && left <= right) {
for (int j = left; j <= right; j++) sb.append(m[top][j]).append(' ');
top++;
for (int i = top; i <= bottom; i++) sb.append(m[i][right]).append(' ');
right--;
if (top <= bottom) {
for (int j = right; j >= left; j--) sb.append(m[bottom][j]).append(' ');
bottom--;
}
if (left <= right) {
for (int i = bottom; i >= top; i--) sb.append(m[i][left]).append(' ');
left++;
}
}
System.out.println(sb.toString().trim());
}
}