Problem

Given an m x n matrix, return all elements of the matrix in spiral order.

Examples

Example 1:

1
2
3
4
5
6

Input: matrix = [
	[ 1, 2, 3 ],
	[ 4, 5, 6 ],
	[ 7, 8, 9 ]
]
Output: [1,2,3,6,9,8,7,4,5]

Example 2:

1
2

Input: matrix =[[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]

Follow Up

Spiral Matrix 2 - Generate

Similar Problems

Solution

Method 1 - Iterative just checking boundaries

We have 4 boundaries - left, right, top and bottom. We now have to loop from left to right, then top to bottom, then right to left and bottom to top. Each time, we change direction, we update respective boundary.

Also, we can run the loop in 2 ways:

1

while(left < right && top < bottom)

OR

1

while(ans.size() < m*n)

In the code below, we are using latter, but any of the conditions will work.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

class Solution {
	public List<Integer> spiralOrder(int[][] matrix) {
		List<Integer> ans = new ArrayList<Integer> ();
		if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
			return ans;
		}
	
		int m = matrix.length;
		int n = matrix[0].length;
	
		int left = 0;
		int right = n - 1;
		int top = 0;
		int bottom = m - 1;
	
		while (ans.size() < m * n) {
			for (int i = left; i<= right; i++) {
				ans.add(matrix[top][i]);
			}
			top++;
	
			for (int i = top; i<= bottom; i++) {
				ans.add(matrix[i][right]);
			}
			right--;
	
			//prevent duplicate row
			if (top <= bottom) {
				for (int i = right; i >= left; i--) {
					ans.add(matrix[bottom][i]);
				}
				bottom--;
			}
	
			// prevent duplicate column
			if (left <= right) {
				for (int i = bottom; i >= top; i--) {
					ans.add(matrix[i][left]);
				}
				left++;
			}
		}
	
		return ans;
	}
}

Method 2 - Iterative with Direction Variable

We can also use direction variable.

Initially, consider the boundaries for mXn matrix (similar to previous method):

  • top = 0
  • right = n – 1
  • bottom  = m – 1
  • left = 0

Also:

  • dir == 1, print top row
  • dir == 2, print right column
  • dir == 3, print bottom row
  • dir == 4, print left column

Also, initially, dir = 1

  • dir = 1

So, when dir == 1, we have:

1
2
3
4
5

for (int i = left; i<= right; ++i) {
	print arr[top][i];
}

++top;

We must keep rotating the value of dir between 1, 2, 3, 4 as long as top ≤ bottom and left ≤ right. If you have understood the logic, you should be able to write the code easily. If you didn’t just go through the explanation once more, it is can be tricky.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

public static void printInSpiralOrder(final int[][] arr) {
	if (arr.length == 0 || arr[0].length == 0) {
		return;
	}

	int top = 0, bottom = arr.length - 1, left = 0, right = arr[0].length - 1;
	int dir = 1;

	while (top<= bottom && left<= right) {
		if (dir == 1) { // left-right
			for (int i = left; i<= right; ++i) {
				System.out.print(arr[top][i] + " ");
			}

			++top;
			dir = 2;
		} else if (dir == 2) { // top-bottom
			for (int i = top; i<= bottom; ++i) {
				System.out.print(arr[i][right] + " ");
			}

			--right;
			dir = 3;
		} else if (dir == 3) { // right-left
			for (int i = right; i >= left; --i) {
				System.out.print(arr[bottom][i] + " ");
			}

			--bottom;
			dir = 4;
		} else if (dir == 4) { // bottom-up
			for (int i = bottom; i >= top; --i) {
				System.out.print(arr[i][left] + " ");
			}

			++left;
			dir = 1;
		}
	}
}

Method 3 - Iterative with direction and switch case

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> ans = new ArrayList<>();
        if (matrix.length == 0 || matrix[0].length == 0) {
            return ans;
        }

        int top = 0;
        int bottom = matrix.length - 1;
        int left = 0;
        int right = matrix[0].length - 1;
        int dir = 0; // we go right, down, left, top

        while (top <= bottom && left <= right) {
            switch (dir) {
                case 0: // Right
                    for (int i = left; i <= right; i++) {
                        result.add(matrix[top][i]);
                    }
                    top++;
                    break;
                case 1: // Down
                    for (int i = top; i <= bottom; i++) {
                        result.add(matrix[i][right]);
                    }
                    right--;
                    break;
                case 2: // Left
                    for (int i = right; i >= left; i--) {
                        result.add(matrix[bottom][i]);
                    }
                    bottom--;
                    break;
                case 3: // Top
                    for (int i = bottom; i >= top; i--) {
                        result.add(matrix[i][left]);
                    }
                    left++;
            }
            dir = (dir + 1) % 4;
        }

        return result;
    }
}

Method 4 - Recursive

Here is the logic:

  • Start printing from first row.
  • Print row and columns, forward and backward alternatively
  • With every iteration of (either row or column), reduce the size of an row or column by 1
  • Call recursively

We can also recursively solve this problem. The solution’s performance is not better than Solution 1. Therefore, Solution 1 should be preferred.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

class Solution {

	public List<Integer> spiralOrder(int[][] matrix) {
		List<Integer> ans = new ArrayList<Integer>();

		if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
			return ans;
		}

		helper(matrix, 0, matrix.length - 1, 0, matrix[0].length - 1, ans);
		return ans;
	}

	private void helper(int[][] matrix, int r1, int r2, int c1, int c2, List<Integer> ans) {
		if (r1 > r2 || c1 > c2) {
			return;
		}
		// right
		for (int c = c1; c <= c2; c++) {
			ans.add(matrix[r1][c]);
		}

		// down
		for (int r = r1 + 1; r <= r2; r++) {
			ans.add(matrix[r][c2]);
		}

		// if already processed
		if (r1 == r2 || c1 == c2) return;

		// left
		for (int c = c2 - 1; c >= c1; c--) {
			ans.add(matrix[r2][c]);
		}

		// top
		for(int r = r2 - 1; r >= r1 + 1; r--) {
			ans.add(matrix[r][c1]);
		}

		helper(matrix, r1 + 1, r2 - 1, c1 + 1, c2 - 1, ans);
	}
}