59. Spiral Matrix II

Spiral Matrix II

Problem Description

Given a positive integer n, generate an n x n matrix filled with elements from 1 to n2 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

Approach) Generic Solution

/**
 * @param {number} n
 * @return {number[][]}
 */
var generateMatrix = function(n) {
    let result = [];
    // creating two dimensional array
    for (var i = 0; i < n; i++) {
      result[i] = new Array(n);
    }
    let val = 1;
 
    let rowBeg = 0
    let rowEnd = n - 1
    let colBeg = 0
    let colEnd = n - 1
    
    while (rowBeg <= rowEnd && colBeg <= colEnd) {
        for (let i = colBeg; i <= colEnd; i++) {
            result[rowBeg][i] = val++;
        }
        rowBeg++
        for (let i = rowBeg; i <= rowEnd; i++) {
             result[i][colEnd] = val++;
        }
        colEnd--
        if (rowBeg <= rowEnd) {
            for (let i = colEnd; i >= colBeg; i--) {
                result[rowEnd][i] = val++;
            }
            rowEnd--
        }
        
        if (colBeg <= colEnd) {
            for (let i = rowEnd;i >= rowBeg; i--) {
                 result[i][colBeg] = val++;
            }
            colBeg++
        }
    }
    return result
};

Approach) Elegant

const generateMatrix = (n) => {
  const M = [...Array(n)].map(() => Array(n).fill(0));
  let x = 0, y = 0, dx = 1, dy = 0;
  for (let i = 1, nn = n**2; i <= nn; ++i) {
    M[y][x] = i;
    if (!M[y + dy] || M[y + dy][x + dx] !== 0)
      [dx, dy] = [-dy, dx];
    x += dx;
    y += dy;
  }
  return M;
};

Approach) Math Power

const generateMatrix = (n) => {
  const {max, abs, floor} = Math;
  const num = (x, y) => {
    x += x - n + 1;
    y += y - n + 1;
    const m = max(abs(x), abs(y));
    let p = floor((x + y) / 2);
    if (x < y) p = 2 * m - p;
    return n * n - m * m - m + p;
  }
    
  const M = [];
  for (let y = 0; y < n; ++y) {
    M[y] = [];
    for (let x = 0; x < n; ++x)
      M[y][x] = num(x, y);
  }
  return M;
};

Approach) Without If

There are steps in each direction in the spiral for n = 5.
[0, 5, 4, 4, 3, 3, 2, 2, 1, 1] and for any n [0, n, n - 1, n - 1, ..., 3, 3, 2, 2, 1, 1]

Update signs of directions.

[0, 5, 4, -4, -3, 3, 2, -2, -1, 1]


const generateMatrix = (n) => {    
  const M = [...Array(n)].map(() => Array(n));
  let v = 0, x = -1, y = 0;
  for (let i = 0, m, s, dx, dy; i < 2*n; ++i) {
    m = i && (2*n - i + 1) / 2|0;
    s = (-1)**((i - 1)/2|0);
    dx = s * (i % 2);
    dy = s * ((i + 1) % 2);
    for (let j = 0; j < m; ++j) {
      x += dx;
      y += dy;
      M[y][x] = ++v;
    }
  }
  return M;
};

Conclusion

That’s all folks! In this post, we solved LeetCode problem 59. Spiral Matrix II

I hope you have enjoyed this post. Feel free to share your thoughts on this.

You can find the complete source code on my GitHub repository. If you like what you learn. feel free to fork 🔪 and star ⭐ it.

In this blog, I have tried to collect & present the most important points to consider when improving Data structure and logic, feel free to add, edit, comment, or ask. For more information please reach me here
Happy coding!