We have 4 boundaries - left, right, top and bottom. We now have to loop from left to right, then top to bottom, then right to left and bottom to top. Each time, we change direction, we update respective boundary.
Also, we can run the loop in 2 ways:
1
while(left < right && top < bottom)
OR
1
while(ans.size() < m*n)
In the code below, we are using former, but any of the conditions will work.
publicclassSolution {
public List<Integer>spiralOrder(int[][] matrix) {
List<Integer> ans =new ArrayList<>();
// Define boundariesint top = 0;
int bottom = matrix.length- 1;
int left = 0;
int right = matrix[0].length- 1;
while (top <= bottom && left <= right) {
// Traverse top row from left to rightfor (int j = left; j <= right; j++) {
ans.add(matrix[top][j]);
}
top++;
// Traverse right column from top to bottomfor (int i = top; i <= bottom; i++) {
ans.add(matrix[i][right]);
}
right--;
// Traverse bottom row from right to left (if within bounds)if (top > bottom || left > right) {
break;
}
for (int j = right; j >= left; j--) {
ans.add(matrix[bottom][j]);
}
bottom--;
// Traverse left column from bottom to top (if within bounds)for (int i = bottom; i >= top; i--) {
ans.add(matrix[i][left]);
}
left++;
}
return ans;
}
}
classSolution:
defspiralOrder(self, matrix: list[list[int]]) -> list[int]:
ans: list[int] = []
top: int =0 bottom: int = len(matrix) -1 left: int =0 right: int = len(matrix[0]) -1while top <= bottom and left <= right:
for j in range(left, right +1):
ans.append(matrix[top][j])
top +=1for i in range(top, bottom +1):
ans.append(matrix[i][right])
right -=1if top > bottom or left > right:
breakfor j in range(right, left -1, -1):
ans.append(matrix[bottom][j])
bottom -=1for i in range(bottom, top -1, -1):
ans.append(matrix[i][left])
left +=1return ans
classSolution {
public List<Integer>spiralOrder(int[][] matrix) {
List<Integer> ans =new ArrayList<Integer> ();
if (matrix ==null|| matrix.length== 0 || matrix[0].length== 0) {
return ans;
}
int m = matrix.length;
int n = matrix[0].length;
int left = 0;
int right = n - 1;
int top = 0;
int bottom = m - 1;
while (ans.size() < m * n) {
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--;
//prevent duplicate rowif (top <= bottom) {
for (int i = right; i >= left; i--) {
ans.add(matrix[bottom][i]);
}
bottom--;
}
// prevent duplicate columnif (left <= right) {
for (int i = bottom; i >= top; i--) {
ans.add(matrix[i][left]);
}
left++;
}
}
return ans;
}
}
Method 3 - Iterative with direction and switch case#
classSolution {
public List<Integer>spiralOrder(int[][] matrix) {
List<Integer> ans =new ArrayList<>();
if (matrix.length== 0 || matrix[0].length== 0) {
return ans;
}
int top = 0;
int bottom = matrix.length- 1;
int left = 0;
int right = matrix[0].length- 1;
int dir = 0; // we go right, down, left, topwhile (top <= bottom && left <= right) {
switch (dir) {
case 0: // Rightfor (int i = left; i <= right; i++) {
result.add(matrix[top][i]);
}
top++;
break;
case 1: // Downfor (int i = top; i <= bottom; i++) {
result.add(matrix[i][right]);
}
right--;
break;
case 2: // Leftfor (int i = right; i >= left; i--) {
result.add(matrix[bottom][i]);
}
bottom--;
break;
case 3: // Topfor (int i = bottom; i >= top; i--) {
result.add(matrix[i][left]);
}
left++;
}
dir = (dir + 1) % 4;
}
return result;
}
}