Spiral Matrix - Java Solution

1. Introduction

This blog post focuses on a fascinating matrix traversal problem: returning all elements of a matrix in spiral order. This problem is a great example of how to apply complex iteration patterns in a two-dimensional array.

Problem

Given an m x n matrix, the objective is to return all the elements of the matrix in a spiral order, starting from the top left corner and progressively spiraling inward.

2. Solution Steps

1. Define four boundaries (top, bottom, left, right) to track the limits of the spiral.

2. Iterate over the matrix in a spiral order: right across the top row, down the right column, left across the bottom row, and up the left column.

3. After completing each row or column traversal, adjust the corresponding boundary.

4. Continue the process until all elements are traversed.

5. Return the list of elements obtained from the spiral traversal.

3. Code Program

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

public class SpiralMatrix {
    public static void main(String[] args) {
        int[][] matrix = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
        System.out.println(spiralOrder(matrix)); // Test the function
    }

    // Function to return elements of a matrix in spiral order
    public static List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> result = new ArrayList<>();
        if (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--;

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

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

Output:

[1, 2, 3, 6, 9, 8, 7, 4, 5]

Explanation:

1. spiralOrder: This function collects the elements of a matrix in spiral order.

2. It defines four boundaries (top, bottom, left, right) to limit the spiral's scope.

3. The function iterates over the matrix in a spiral pattern, adjusting the boundaries after completing each row or column traversal.

4. It adds elements to the result list while traversing right, down, left, and up, respecting the updated boundaries.

5. The process continues until all elements are included in the result.

6. Finally, the function returns the list of elements in the order they were traversed.