Spiral Matrix In C Program

Introduction

The spiral matrix problem is a classic algorithm challenge that involves traversing or generating a 2D array in a spiral order.

In this article, you will learn how to implement an efficient C program to generate a square matrix filled with numbers in a spiral pattern.

Problem Statement

The challenge is to create an N x N matrix and fill it with consecutive integers, starting from 1, in a clockwise spiral fashion. This problem often tests a programmer's understanding of array manipulation, loop control, and boundary conditions. Mastering it is crucial for optimizing data access patterns in various applications, from image processing to game development.

Example

Consider a 3x3 matrix. When filled in a spiral pattern, it should look like this:

1 2 3
8 9 4
7 6 5

 

Background & Knowledge Prerequisites

To understand this article, you should have a basic understanding of:

• C Programming Basics: Variables, data types, loops (for, while), conditional statements (if).
• Arrays: Declaring and manipulating 2D arrays (matrices).
• Functions: Defining and calling functions.

No special libraries are needed beyond the standard stdio.h for input/output.

Use Cases or Case Studies

Spiral patterns, though seemingly abstract, appear in various practical scenarios:

1. Image Processing: Algorithms might traverse pixels in a spiral to process regions of interest, ensuring all surrounding data is considered before moving further away.
2. Game Development: AI pathfinding or level generation can use spiral patterns to explore areas or create unique terrain layouts.
3. Data Compression: Certain data encoding schemes might process data blocks in a spiral order to exploit spatial locality.
4. Robotics: Robot navigation systems might employ spiral search patterns to explore an unknown environment efficiently.
5. Memory Access Optimization: In some systems, accessing data in a spiral fashion can improve cache utilization by maintaining data locality.

Solution Approaches

The most common and intuitive way to generate a spiral matrix is the Boundary Shrinking Iterative Approach.

Approach 1: Boundary Shrinking Iterative Approach

This method works by maintaining four boundary pointers (top, bottom, left, right) that define the current layer of the spiral. We fill the matrix layer by layer, moving right, then down, then left, and finally up, shrinking the boundaries after each direction.

One-line summary

Generate the spiral matrix by iteratively filling elements in four directions (right, down, left, up) and progressively shrinking the matrix boundaries until the entire matrix is filled.

Code Example

// Generate Spiral Matrix
#include <stdio.h>

// Function to print the matrix
void printMatrix(int N, int matrix[N][N]) {
    printf("Generated Spiral Matrix:\\n");
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            printf("%4d", matrix[i][j]); // Print with spacing for alignment
        }
        printf("\\n");
    }
}

int main() {
    // Step 1: Define matrix size N
    int N;
    printf("Enter the size of the square matrix (N): ");
    scanf("%d", &N);

    // Step 2: Declare the N x N matrix
    int matrix[N][N];

    // Step 3: Initialize boundary pointers and current number
    int top = 0, bottom = N - 1;
    int left = 0, right = N - 1;
    int currentNum = 1; // Start filling from 1

    // Step 4: Loop until all elements are filled (boundaries cross)
    while (top <= bottom && left <= right) {
        // Fill from left to right along the top row
        for (int i = left; i <= right; i++) {
            matrix[top][i] = currentNum++;
        }
        top++; // Move top boundary down

        // Fill from top to bottom along the right column
        for (int i = top; i <= bottom; i++) {
            matrix[i][right] = currentNum++;
        }
        right--; // Move right boundary left

        // Check if top boundary is still less than or equal to bottom boundary
        // This is crucial for non-square matrices, though here N x N
        // It prevents re-traversing if only a single row or column is left
        if (top <= bottom) {
            // Fill from right to left along the bottom row
            for (int i = right; i >= left; i--) {
                matrix[bottom][i] = currentNum++;
            }
            bottom--; // Move bottom boundary up
        }

        // Check if left boundary is still less than or equal to right boundary
        // Similar to the check for top <= bottom
        if (left <= right) {
            // Fill from bottom to top along the left column
            for (int i = bottom; i >= top; i--) {
                matrix[i][left] = currentNum++;
            }
            left++; // Move left boundary right
        }
    }

    // Step 5: Print the generated matrix
    printMatrix(N, matrix);

    return 0;
}

Run

Sample Output

For N = 4:

Enter the size of the square matrix (N): 4
Generated Spiral Matrix:
   1   2   3   4
  12  13  14   5
  11  16  15   6
  10   9   8   7

 

For N = 3:

Enter the size of the square matrix (N): 3
Generated Spiral Matrix:
   1   2   3
   8   9   4
   7   6   5

 

 

Stepwise explanation

1. Initialization:
   • top, bottom, left, right: These variables define the current "layer" of the spiral. top and left start at 0, while bottom and right start at N-1.

• currentNum: This counter starts at 1 and is incremented after each number is placed in the matrix.

1. Main Loop: The while (top <= bottom && left <= right) loop continues as long as there are elements left to fill in the current layer. When top crosses bottom or left crosses right, it means all elements have been filled.
2. Fill Right (Top Row):
   • Iterate from left to right along the top row, filling matrix[top][i] with currentNum.

• After filling, increment top to move the top boundary down for the next layer.

1. Fill Down (Right Column):
   • Iterate from the new top to bottom along the right column, filling matrix[i][right] with currentNum.

• After filling, decrement right to move the right boundary left.

1. Fill Left (Bottom Row):
   • Crucial Check: Before filling, check if (top <= bottom). This prevents redundant filling if only a single row or column remains (e.g., in odd-sized matrices, the innermost element or row/column might have already been processed).

• Iterate from the new right back to left along the bottom row, filling matrix[bottom][i] with currentNum.
• After filling, decrement bottom to move the bottom boundary up.

1. Fill Up (Left Column):
   • Crucial Check: Similarly, check if (left <= right).

• Iterate from the new bottom back to top along the left column, filling matrix[i][left] with currentNum.
• After filling, increment left to move the left boundary right.

1. The loop repeats, processing the next inner layer until currentNum exceeds NN or the boundaries cross.

Conclusion

The spiral matrix generation problem is an excellent exercise in understanding array traversal and boundary management. The boundary shrinking iterative approach provides a clean and efficient way to solve this, moving layer by layer. By carefully managing the top, bottom, left, and right pointers, we can ensure every cell is filled correctly in a spiral sequence.

Summary

• Problem: Fill an N x N matrix with numbers 1 to NN in a clockwise spiral.
• Approach: The "Boundary Shrinking Iterative Approach" is efficient and intuitive.
• Mechanics:
• Use top, bottom, left, right pointers to define current layer.
• Iteratively fill in four directions: right (top row), down (right column), left (bottom row), up (left column).
• Shrink boundaries after each direction (increment top, decrement right, decrement bottom, increment left).
• Include checks (if (top <= bottom) and if (left <= right)) before filling the left and up segments to handle edge cases, especially for non-square or odd-sized matrices.
• Use Cases: Relevant in image processing, game AI, robotics, and data optimization.

Test Your Understanding

1. How would you modify the code to generate an anti-clockwise spiral matrix?
2. What changes would be needed if the matrix was rectangular (e.g., M x N) instead of square?
3. Can you think of a scenario where a recursive approach might be preferred over the iterative one for this problem?