Spirally traversing a matrix
JavaView on GFG
Time: O(n*m)
Space: O(1)
Advertisement
Intuition
Traverse matrix in spiral order: right, down, left, up, shrinking boundaries.
Algorithm
- 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?