algoadvance

Leetcode 54. Spiral Matrix

Problem Statement:

Given an m x n matrix, return all elements of the matrix in spiral order.

Example:

Input: matrix = [
  [1, 2, 3],
  [4, 5, 6],
  [7, 8, 9]
]
Output: [1, 2, 3, 6, 9, 8, 7, 4, 5]

Clarifying Questions:

  1. What is the minimum and maximum size of the matrix?
    • The matrix can be as small as 1x1 and can be quite large.
  2. What should be returned if the matrix is empty (e.g., matrix = [])?
    • If the matrix is empty, return an empty list.
  3. Can elements of the matrix be negative or zero?
    • Yes, there are no restrictions on the values within the matrix.

Strategy:

To solve this problem, we will employ the following strategy:

  1. We need to traverse the matrix in layers, starting from the outermost layer.
  2. For each layer, we will first traverse from the left to the right across the top row, then from the top to the bottom down the right column, then from right to left across the bottom row (if it hasn’t already been included), and finally from bottom to top up the left column (again, if it hasn’t already been included).
  3. We will keep track of the boundaries of the current layer using four variables: top, bottom, left, and right.
  4. We will iterate until all elements are visited.

Here is the Java code implementing this strategy:

Code:

import java.util.ArrayList;
import java.util.List;

public class SpiralMatrix {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> result = new ArrayList<>();
        if (matrix == null || matrix.length == 0) {
            return result;
        }
        
        int top = 0;
        int bottom = matrix.length - 1;
        int left = 0;
        int right = matrix[0].length - 1;
        
        while (top <= bottom && left <= right) {
            // Traverse from left to right along the top row
            for (int i = left; i <= right; i++) {
                result.add(matrix[top][i]);
            }
            top++;
            
            // Traverse from top to bottom down the right column
            for (int i = top; i <= bottom; i++) {
                result.add(matrix[i][right]);
            }
            right--;

            // Traverse from right to left along the bottom row, if not already traversed
            if (top <= bottom) {
                for (int i = right; i >= left; i--) {
                    result.add(matrix[bottom][i]);
                }
                bottom--;
            }

            // Traverse from bottom to top up the left column, if not already traversed
            if (left <= right) {
                for (int i = bottom; i >= top; i--) {
                    result.add(matrix[i][left]);
                }
                left++;
            }
        }
        
        return result;
    }

    public static void main(String[] args) {
        SpiralMatrix sm = new SpiralMatrix();
        int[][] matrix = {
            {1, 2, 3},
            {4, 5, 6},
            {7, 8, 9}
        };
        System.out.println(sm.spiralOrder(matrix)); // Output: [1, 2, 3, 6, 9, 8, 7, 4, 5]
    }
}

Time Complexity:

The time complexity of this solution is O(m * n), where m is the number of rows and n is the number of columns in the matrix. This is because each element of the matrix is visited exactly once.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI