DDSA Solutions

Spirally traversing a matrix

Time: O(n*m)
Space: O(1)
Advertisement

Intuition

Traverse matrix in spiral order: right, down, left, up, shrinking boundaries.

Algorithm

  1. 1top=0, bottom=m-1, left=0, right=n-1. Process each boundary layer inward.

Common Pitfalls

  • Check boundaries after each direction to avoid double-counting single rows/columns.
Spirally traversing a matrix.java
Java
// Approach: Four-boundary approach: top, bottom, left, right. Shrink boundaries as each boundary is traversed.
// Time: O(n*m) Space: O(1)
import java.util.*;

class Solution {
    // Function to return a list of integers denoting spiral traversal of matrix.
    public ArrayList<Integer> spirallyTraverse(int matrix[][]) {
        int m = matrix.length;
        int n = matrix[0].length;
        int left = 0, top = 0;
        int right = n - 1, bottom = m - 1;

        ArrayList<Integer> ans = new ArrayList<>();
        while (left <= right && top <= bottom) {
            for (int i = left; i <= right; i++)
                ans.add(matrix[top][i]);
            top++;

            for (int i = top; i <= bottom; i++)
                ans.add(matrix[i][right]);
            right--;

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

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

        return ans;
    }
}
Advertisement
Was this solution helpful?