Spiral Matrix medium

Problem Statement

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

Example 1

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

Example 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]

Steps

The spiral traversal can be achieved by iteratively processing the outer layers of the matrix. We can simulate this using four pointers:

1. top: Represents the top row index.
2. bottom: Represents the bottom row index.
3. left: Represents the leftmost column index.
4. right: Represents the rightmost column index.

In each iteration, we traverse the matrix layer by layer:

1. Traverse right: From left to right, adding elements to the result list.
2. Traverse down: From top + 1 to bottom, adding elements.
3. Traverse left: From right - 1 to left, adding elements (if there are any elements left in this row).
4. Traverse up: From bottom - 1 to top + 1, adding elements (if there are any elements left in this column).

We then update the pointers to shrink the bounds for the next layer and repeat this process until all elements are processed.

Explanation

The code implements the above steps. It initializes the pointers to the matrix boundaries. Then, it enters a while loop that continues as long as there are unvisited elements (i.e., top <= bottom and left <= right). Inside the loop, each of the four traversal directions is handled, adding elements to the result list. After each traversal direction, the corresponding pointer is adjusted to move inwards towards the center of the matrix.

Code

import java.util.ArrayList;
import java.util.List;

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

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

        while (top <= bottom && left <= right) {
            // Traverse right
            for (int i = left; i <= right; i++) {
                result.add(matrix[top][i]);
            }
            top++;

            // Traverse down
            for (int i = top; i <= bottom; i++) {
                result.add(matrix[i][right]);
            }
            right--;

            // Check if there are more elements to traverse (handle single row or column case)
            if (top <= bottom && left <= right) {
                // Traverse left
                for (int i = right; i >= left; i--) {
                    result.add(matrix[bottom][i]);
                }
                bottom--;

                // Traverse up
                for (int i = bottom; i >= top; i--) {
                    result.add(matrix[i][left]);
                }
                left++;
            }
        }
        return result;
    }
}

Complexity

• Time Complexity: O(m * n), where 'm' is the number of rows and 'n' is the number of columns. We visit each element exactly once.
• Space Complexity: O(1) (excluding the space for the result list), as we are using a constant amount of extra space to track the pointers. The space used by the result list is O(m*n) in the worst case.