Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

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

  1. Keep four boundaries: top, bottom, left and right.
  2. 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());
    }
}

Solve Spiral Matrix online · All practice problems