DSCPPAS264 - Editorial

editorial
,
1

Problem Statement:

You are given an n × n matrix. The task is to print the elements of the matrix in an anticlockwise spiral order, starting from the top-left element.

Approach:

To solve this problem, we can use a boundary traversal technique where we traverse the matrix in layers, spiraling in an anticlockwise direction. The key idea is to control the boundaries (left, right, top, bottom) of the matrix and move inward while printing the elements in the desired order.

Detailed Steps:

  1. Initialization:

    • First, we check if the matrix is empty. If it is, we return an empty result since there are no elements to print.
    • Initialize the boundaries:
      • top and left start at 0 (the first row and column).
      • bottom is n-1 (last row), and right is n-1 (last column).

  2. Traversal Loop:

    • We run a loop until the left boundary exceeds right or top exceeds bottom.
    • In each iteration, we perform four steps to print elements:
      1. Top to Bottom (Left Column): Traverse from the top boundary to the bottom boundary along the left column. After this, increment the left boundary.
      2. Left to Right (Bottom Row): Traverse from the left boundary to the right boundary along the bottom row. Then, decrement the bottom boundary.
      3. Bottom to Top (Right Column): If left <= right, traverse from the bottom boundary to the top boundary along the right column. After that, decrement the right boundary.
      4. Right to Left (Top Row): If top <= bottom, traverse from the right boundary to the left boundary along the top row. Then, increment the top boundary.

  3. Completion:

    • The loop continues adjusting the boundaries inward until all elements are printed in an anticlockwise spiral order.
    • Finally, the result is printed.

Time Complexity:

The time complexity is O(n^2) because each element of the matrix is visited exactly once.

Space Complexity:

The space complexity is O(n^2) due to the additional space used by the result vector to store the matrix elements.