Spiral Matrix - C Solution

1. Introduction

This post discusses a matrix traversal problem known as "Spiral Matrix". The task is to return all elements of a given m x n matrix in spiral order. This problem is a classic example of handling complex array traversals and is often used to test a programmer's ability to implement and control nested loops and boundary conditions in array processing.

Problem

Given an m x n matrix, the goal is to return all the elements of the matrix in a spiral order. This involves traversing the matrix outward in from the top left corner, moving right, down, left, and up, in a spiral pattern until all elements have been traversed.

2. Solution Steps

1. Initialize variables for the boundaries of the matrix (top, bottom, left, right).

2. Use a loop to traverse the matrix in spiral order.

3. Traverse from left to right along the top row, then increment the top boundary.

4. Traverse from top to bottom along the right column, then decrement the right boundary.

5. Traverse from right to left along the bottom row, then decrement the bottom boundary.

6. Traverse from bottom to top along the left column, then increment the left boundary.

7. Repeat steps 3-6 until all elements have been included.

8. Return the list of elements in spiral order.

3. Code Program

#include <stdio.h>
#include <stdlib.h>

// Function to return elements of the matrix in spiral order
int* spiralOrder(int** matrix, int matrixSize, int* matrixColSize, int* returnSize) {
    if (matrixSize == 0 || matrixColSize[0] == 0) {
        *returnSize = 0;
        return NULL;
    }

    int* spiral = (int*) malloc(matrixSize * matrixColSize[0] * sizeof(int));
    *returnSize = 0;
    int top = 0, bottom = matrixSize - 1, left = 0, right = matrixColSize[0] - 1;

    while (top <= bottom && left <= right) {
        // Traverse from left to right
        for (int i = left; i <= right; i++) {
            spiral[(*returnSize)++] = matrix[top][i];
        }
        top++;

        // Traverse downwards
        for (int i = top; i <= bottom; i++) {
            spiral[(*returnSize)++] = matrix[i][right];
        }
        right--;

        // Traverse from right to left
        if (top <= bottom) {
            for (int i = right; i >= left; i--) {
                spiral[(*returnSize)++] = matrix[bottom][i];
            }
            bottom--;
        }

        // Traverse upwards
        if (left <= right) {
            for (int i = bottom; i >= top; i--) {
                spiral[(*returnSize)++] = matrix[i][left];
            }
            left++;
        }
    }

    return spiral;
}

// Main function to test the spiralOrder function
int main() {
    int matrix1[3][3] = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
    int matrixSize1 = 3, matrixColSize1[] = {3, 3, 3}, returnSize1;
    int* result1 = spiralOrder((int**)matrix1, matrixSize1, matrixColSize1, &returnSize1);
    printf("Spiral Order (Example 1): ");
    for (int i = 0; i < returnSize1; i++) {
        printf("%d ", result1[i]);
    }
    printf("\n");
    free(result1);

    return 0;
}

Output:

Spiral Order (Example 1): 1 2 3 6 9 8 7 4 5

Explanation:

1. Initialize boundaries (top, bottom, left, right) for the spiral traversal.

2. Use loops to move right, down, left, and up, adjusting the boundaries after each direction.

3. Continue the traversal until all matrix elements are included in the spiral order.

4. Allocate memory dynamically for the spiral array and return it.

5. The main function tests the spiralOrder function with a sample 3x3 matrix and prints the spiral order of its elements.