algoadvance

Leetcode 59. Spiral Matrix II

Problem Statement

Given a positive integer n, generate an n x n matrix filled with elements from 1 to n^2 in spiral order.

Clarifying Questions

1. Input Constraints:
   • What is the range of n?
     • Typically, 1 <= n <= 20 for such problems, but we should confirm.
2. Output Format:
   • Should the output be a 2D matrix?
3. Edge Cases:
   • How do we handle the smallest case where n = 1?

Assuming the problem follows the typical constraints and output format:

Example

Given n = 3, the output should be:

[
 [ 1, 2, 3 ],
 [ 8, 9, 4 ],
 [ 7, 6, 5 ]
]

Strategy

1. Initialization:
   • Create a 2D vector matrix with dimensions n x n and initialize with zeros or empty values.
   • Keep track of the current number to put in the matrix.
2. Direction Vectors:
   • Use four direction vectors to move right, down, left, and up.
3. Boundaries:
   • Maintain four boundary variables (top, bottom, left, right), initialized as 0, n-1, 0, and n-1 respectively.
4. Filling Logic:
   • While there are elements to fill (current_num <= n*n):
     • Traverse from left to right along the top boundary, then increment the top boundary.
     • Traverse from top to bottom along the right boundary, then decrement the right boundary.
     • Traverse from right to left along the bottom boundary, then decrement the bottom boundary.
     • Traverse from bottom to top along the left boundary, then increment the left boundary.

Code

#include <vector>

std::vector<std::vector<int>> generateMatrix(int n) {
    std::vector<std::vector<int>> matrix(n, std::vector<int>(n, 0));
    int current_num = 1;
    int left = 0, right = n - 1, top = 0, bottom = n - 1;

    while (current_num <= n * n) {
        // Traverse from left to right along the top boundary.
        for (int i = left; i <= right; ++i) {
            matrix[top][i] = current_num++;
        }
        top++;

        // Traverse from top to bottom along the right boundary.
        for (int i = top; i <= bottom; ++i) {
            matrix[i][right] = current_num++;
        }
        right--;

        // Traverse from right to left along the bottom boundary.
        for (int i = right; i >= left; --i) {
            matrix[bottom][i] = current_num++;
        }
        bottom--;

        // Traverse from bottom to top along the left boundary.
        for (int i = bottom; i >= top; --i) {
            matrix[i][left] = current_num++;
        }
        left++;
    }

    return matrix;
}

Time Complexity

• Time Complexity: The time complexity of this solution is (O(n^2)), since every element is visited exactly once.
• Space Complexity: The space complexity is (O(n^2)) due to the space required to store the n x n matrix.

This approach efficiently fills the matrix in a spiral order while maintaining ease of implementation and understanding.

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

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?