54. Spiral Matrix

📝 Problem Details

• Title: 54. Spiral Matrix
• Link: https://leetcode.com/problems/spiral-matrix/
• Difficulty: Medium
• Tags/Categories: Matrix Arrays

💭What Were My Initial Thoughts?

- things to address:
	- switching between row and column movement
	- switching between forward and backward directions
	- changes in boundaries as we spiral inward

- potential solution [WRONG]:
	- potentially keep an unodered_set of elements traversed in the matrix
	- if the next element exists in the set, rotate early
	- if we have hit a boundary, rotate

	- above proposed solution doesnt take into account duplicate elements in the matrix
	- also space inefficient

🤔What Did I Struggle With?

~

💡 Explanation of Solution

1. The matrix traversal follows a specific spiral order:
   - Traverse from left to right along the top row.
   - Traverse from top to bottom along the right column.
   - Traverse from right to left along the bottom row (if still within bounds).
   - Traverse from bottom to top along the left column (if still within bounds).
   - Repeat the above steps until all elements are visited.

2. Use boundaries (`top`, `bottom`, `left`, `right`) to keep track of the traversed rows and columns:
   - `top`: The first untraversed row.
   - `bottom`: The last untraversed row.
   - `left`: The first untraversed column.
   - `right`: The last untraversed column.
   
3. The algorithm stops when `top > bottom` or `left > right`.
4. Edge case: Handle empty matrices by returning an empty result early.

⌛ Complexity Analysis

1. **Time Complexity**:
   - Each element of the matrix is visited exactly once.
   - Time complexity: `O(m * n)`, where `m` is the number of rows and `n` is the number of columns.

2. **Space Complexity**:
   - The result vector stores all elements of the matrix.
   - Space complexity: `O(m * n)` for the result vector.

💻 Implementation of Solution

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        if (matrix.empty()) return {}; // Early exit for empty matrix
        
        vector<int> result;
 
        // Define boundaries
        int top = 0;
        int bottom = matrix.size() - 1;
        int left = 0;
        int right = matrix[0].size() - 1;
 
        // Traverse the matrix in spiral order
        while (top <= bottom && left <= right) {
            // Traverse from left to right along the top row
            for (int j = left; j <= right; j++) {
                result.push_back(matrix[top][j]);
            }
            top++;
 
            // Traverse from top to bottom along the right column
            for (int i = top; i <= bottom; i++) {
                result.push_back(matrix[i][right]);
            }
            right--;
 
            // Traverse from right to left along the bottom row (if within bounds)
            if (top <= bottom) {
                for (int j = right; j >= left; j--) {
                    result.push_back(matrix[bottom][j]);
                }
                bottom--;
            }
 
            // Traverse from bottom to top along the left column (if within bounds)
            if (left <= right) {
                for (int i = bottom; i >= top; i--) {
                    result.push_back(matrix[i][left]);
                }
                left++;
            }
        }
 
        return result;
    }
};