54. Spiral Matrix

[jason89521]

Practice Dates

• 2024/05/15

Description

Link: https://leetcode.com/problems/spiral-matrix/description/

Solution

Record all the boundaries and check whether the length of the result vector is equal to the total number of elements in the matrix.

impl Solution {
    pub fn spiral_order(matrix: Vec<Vec<i32>>) -> Vec<i32> {
        let mut bottom_row_boundary = matrix.len();
        let mut right_col_boundary = matrix[0].len();
        let mut top_row_boundary = 0;
        let mut left_col_boundary = 0;
        let mut result = vec![];
        let element_counts = matrix.len() * matrix[0].len();

        while result.len() < element_counts  {
            for col in left_col_boundary..right_col_boundary {
                result.push(matrix[top_row_boundary][col]);
            }
            right_col_boundary -= 1;
            top_row_boundary += 1;

            if result.len() >= element_counts {
                break;
            }
            for row in top_row_boundary..bottom_row_boundary {
                result.push(matrix[row][right_col_boundary]);
            }
            bottom_row_boundary -= 1;

            if result.len() >= element_counts {
                break;
            }
            for col in (left_col_boundary..right_col_boundary).rev() {
                result.push(matrix[bottom_row_boundary][col]);
            }

            if result.len() >= element_counts {
                break;
            }
            for row in (top_row_boundary..bottom_row_boundary).rev() {
                result.push(matrix[row][left_col_boundary]);
            }
            left_col_boundary += 1;
        }

        result
    }
}

Performance

Time complexity:

[jason89521]

There is another approach that doesn't require checking the length of the result every time we want to push an element to the result.

We can use an integer to record the direction: 1 means from left to right or from top to bottom, and -1 means from right to left or from bottom to top. We also use two variables, rows and cols, to record how many rows or columns are left to handle.