SAMSUNG 49-Inch Odyssey G9

Because earth is not flat

Description

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

Intuition

The problem can be visualized as filling up an n x n grid by following a spiral pattern, starting from the top-left corner. We can achieve this by iteratively filling the matrix while carefully controlling the direction of movement and ensuring that we don't overwrite any existing values.

Approach

1. Matrix Initialization: Start by creating an n x n matrix initialized to zero.
2. Direction Control: Use a list of tuples to represent the four possible directions (right, down, left, up). Begin with the direction set to "right."
3. Matrix Filling:
   • Place numbers from 1 to n^2 in the matrix, starting from the top-left corner.
   • After placing each number, check if the next position is either out of bounds or already filled. If it is, change direction.
4. Direction Change: The direction should change in the order of right → down → left → up whenever the next move is invalid.
5. Boundary Conditions: The loop runs until all cells in the matrix are filled, ensuring that each number is placed correctly without overwriting.

Complexity

Time Complexity:

O(n^2), since we fill in every cell in the n x n matrix exactly once.

Space Complexity:

O(n^2), as we are using an n x n matrix to store the result.

Code

C++

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        int x = 0, y = 0, dx = 1, dy = 0;
        vector<vector<int>> res(n, vector<int>(n, 0));
        
        for (int i = 0; i < n * n; ++i) {
            res[y][x] = i + 1;
            if (!(0 <= x + dx && x + dx < n && 0 <= y + dy && y + dy < n && res[y + dy][x + dx] == 0)) {
                tie(dx, dy) = make_tuple(-dy, dx);
            }
            x += dx;
            y += dy;
        }
        
        return res;
    }
};

Python

class Solution:
    def generateMatrix(self, n: int) -> List[List[int]]:
        # Initialize the result matrix
        res = [[0] * n for _ in range(n)]
        
        # Initialize directions for right, down, left, and up movements
        directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        x, y = 0, 0  # Starting position
        dx, dy = directions[0]  # Start with the "right" direction
        
        for i in range(1, n * n + 1):
            res[x][y] = i  # Place the current number
            
            # Calculate the next position
            nx, ny = x + dx, y + dy
            
            # Check if the next position is out of bounds or already filled
            if not (0 <= nx < n and 0 <= ny < n and res[nx][ny] == 0):
                # Change direction: (right -> down -> left -> up)
                dx, dy = directions[(directions.index((dx, dy)) + 1) % 4]
                nx, ny = x + dx, y + dy
            
            # Move to the next position
            x, y = nx, ny
        
        return res

Java

class Solution {
    public int[][] generateMatrix(int n) {
        int x = 0, y = 0, dx = 1, dy = 0;
        int[][] res = new int[n][n];
        
        for (int i = 0; i < n * n; i++) {
            res[y][x] = i + 1;
            if (!(0 <= x + dx && x + dx < n && 0 <= y + dy && y + dy < n && res[y + dy][x + dx] == 0)) {
                int temp = dx;
                dx = -dy;
                dy = temp;
            }
            x += dx;
            y += dy;
        }
        
        return res;
    }
}

JavaScript

var generateMatrix = function(n) {

    let x = 0, y = 0, dx = 1, dy = 0;
    let res = Array.from({length: n}, () => Array.from({length: n}, () => 0));

    for (let i = 0; i < n * n; i++) {
        res[y][x] = i + 1;

        if (!(0 <= x + dx && x + dx < n && 0 <= y + dy && y + dy < n && res[y+dy][x+dx] === 0)) {
            [dx, dy] = [-dy, dx];
        }     
        x += dx;
        y += dy;
    }
    return res;    
};