C++ Solution to 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.

Example 1

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

Example 2

Input: n = 1
Output: [[1]]

Constraints

1 <= n <= 20.

Solution

Starting from the top left of the matrix.
Going along the spiral direction.
Put the value to the matrix, starting from 1.

Code

#include <vector>
#include <iostream>
using namespace std;
enum Direction {RIGHT, DOWN, LEFT, UP};
vector<vector<int>> generateMatrix(int n) {
    vector<vector<int>> m(n, vector<int>(n));
    int bottom = n - 1;
    int right = n - 1;
    int top = 0;
    int left = 0;
    int row = 0;
    int col = 0;
    Direction d = RIGHT;
    int a = 1;
    while (top <= bottom && left <= right) {
        m[row][col] = a++;
        switch (d) {
            case RIGHT: if (col == right) {
                            top++;
                            d = DOWN;
                            row++;
                        } else {
                            col++;
                        }
                        break;
            case DOWN:  if (row == bottom) {
                            right--;
                            d = LEFT;
                            col--;
                        } else {
                            row++;
                        }
                        break;
            case LEFT:  if (col == left) {
                            bottom--;
                            d = UP;
                            row--;
                        } else {
                            col--;
                        }
                        break;
            case UP:    if (row == top) {
                            left++;
                            d = RIGHT;
                            col++;
                        } else {
                            row--;
                        }
                        break;
        }
    }
    return m;
}
void printResult(vector<vector<int>>& m) {
    cout << "[";
    for (auto& r : m) {
        cout << "[";
        for (int a : r) {
            cout << a << ",";
        }
        cout << "]";
    }
    cout << "]\n";
}
int main() {
    auto m = generateMatrix(3);
    printResult(m);
    m = generateMatrix(1);
    printResult(m);
}

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

This solution uses a Direction enum and boundary variables to iteratively fill the matrix in a spiral pattern. Updating the direction of movement based on the current position and boundaries efficiently populates the matrix with sequential values, traversing in a clockwise direction from the outer layer to the inner layer.

Complexity

Runtime: O(n^2), where n x n is the size of the matrix.
Extra space: O(1).

Key Takeaway

Enumerating directions with an enum (like Direction) can enhance code readability and maintainability, especially in algorithms involving traversal or movement. It aids in clearly defining and referencing the possible directions within the problem domain.

Exercise

Spiral Matrix.

Leetcode 59. How To Go Around A Square Matrix In Spiral Order

Comments

More from this blog

Leetcode 120. How To Find The Minimum Path From Top To Bottom Of A Triangle

How To Find The Longest Substring Without Repeating Characters

How To Find The Maximal Subarray Having Distinct Elements

Common Mistakes in Coding Interviews and How to Avoid Them

Problem statement

Example 1

Example 2

Constraints

Solution

Code

Complexity

Key Takeaway

Exercise

Command Palette

Comments

More from this blog

Problem statement

Example 1

Example 2

Constraints

Solution

Code

Complexity

Key Takeaway

Exercise