Square Spiral Matrix in Javascript

Question

I've been grinding some Leetcode for an interview coming up and just completed Square Spiral in Javascript.

Looking for feedback on performance. This ranked faster than 58% of submissions, would there be anyway to increase the speed using a similar implementation to what I have here?

enter image description here

let matrix = [
 [1, 2, 3, 4, 5],
 [6, 7, 8, 9, 10],
 [11,12,13,14,15],
 [16,17,18,19,20],
 [21,22,23,24,25]
]
var spiralOrder = (matrix) => {
 //make copy
 var dup=JSON.parse(JSON.stringify(matrix));
 //setup variables
 let maxX, maxY, baseX, baseY, x, y, vecX, vecY, nums, totalSquares;
 //Max indexes for array and sub arrays
 maxY=matrix[0].length-1;
 maxX=matrix.length-1;
 //baseX tells x when it has reached the first sub array.
 baseX=0;
 
 //baseY tells y when it has reached the first index of a sub array.
 baseY=0;
 
 //our indexes
 x=0;
 y=0;
 
 //our movement vectors
 vecX=0;
 vecY=0;
 
 //the count for keeping track of positions iterated
 count=0;
 
 //the total amount of squares to be iterated
 totalSquares=matrix.length*matrix[0].length;
 
 //return value array
 nums=[];
 //I don't get how subArrays with only a single element could
 //still be considered spiralable, but this if-statement handles
 //those edge cases. Thanks Leetcode.
 if (matrix[0].length===1) {
 for (var i=0;i<matrix.length;i++) {
 nums.push(matrix[i][0])
 }
 return nums
 }
 
 //While our iterated count is not equal to the total amount of
 //squares to be iterated. When this is true we know we
 //have completed the spiral.
 while(count!==totalSquares) {
 
 nums.push(dup[x][y]);
 count++;
 //Our loop iterates around in a spiral. On every turn
 //the loop increases the opposite side baseX, baseY,
 //maxX or maxY to increase the tightness of the spiral
 //as it loops.
 
 //This handles starting the very first iteration, moving right.
 if (x===0&&y===0) {
 vecX=0;
 vecY=1;
 //We've reached the top rightmost square, move down.
 } else if (x===baseX&&y===maxY) {
 vecX=1;
 vecY=0;
 //We can't increment baseY until we're on
 //our second turn downwards.
 if (baseX>0) {
 baseY+=1;
 }
 //We've reached bottom rightmost square, move left, increment baseX. 
 } else if (x===maxX&&y===maxY) {
 vecX=0;
 vecY=-1;
 baseX+=1;
 //We've reached bottom leftmost square, move up, decrement maxY.
 } else if (x===maxX&&y===baseY) {
 vecX=-1;
 vecY=0
 maxY-=1;
 //We've reached top leftmost square, move right, decrement maxX.
 } else if (x===baseX&&y===baseY) {
 vecX=0;
 vecY=1;
 maxX-=1;
 }
 //Increment x or y by the vector.
 x+=vecX;
 y+=vecY;
 }
 return nums
}
```

• Blindman67: Want to increase performance remove the JSON (super slow) copy hack. There is no reason to copy the array in this code. Nor should you ever use JSON for anything but data transport . To copy a 2D array const dup = array2D.map(subArray=>[...subArray]);
• Samuel Samuelson: You're right there isn't any reason to copy, however when I take out the copy the speed is increased to 72 ms, but if I use this 2d copy map function the speed increases up to 64 ms, weird.
• Blindman67: Not weird. Reason 1 Most likely, run the code several times, server load will effect run time at leetcode. Reason 2 unlikely but possible that there could be a proxy on the array

Answer 1

REVIEW

As a solution it is simple and performant which is the aim of all good code.

However there are many style issues likely due to inexperience

Code style review

• Way too many comments. Many of them stating the obvious, some inaccurate.

  Comments should only be used when the code can not describe what the code does, and generally when the code is such that it needs comments then it is best to change the code rather than add comments.

  Often comments are added to clarify poor variable names. If you are adding comments to clarify a name then don't add the comment, change the name.

• Spaces between operators.

• Take care to define all variables. The variable count is undefined when you assign 0 to it.

  JS will declare the variable for you but it will be declared in global scope and is thus slower to access and likely to clash with existing globals resulting in very hard to debug bugs. ALWAYS declare variables.

  The rewrite function adds the directive "use strict" to prevent undeclared variables from being used. For more on strict_mode

• Use const for variables that do not change.

• You can assign variables as you declare them.

• Be consistent in your use of semicolons. Some lines are missing semicolons, and each return is also missing semicolons.

• Always use the simplest style - i.e. don't write 4 lines of code when 1 will do.

• When using x,y coordinates on 2D arrays the x Axis is for columns and y for rows. In the rewrite I changed x and y to col and row.

Rewrite

The rewrite keeps the same logic (apart from added early exit when only one row).

• Added strict_mode directive "use strict"

• It removes the array copy at the top.

• Uses var rather than let but which to use is up to you.

• Uses a style that is focused on performance rather than source brevity.

  Eg if (row === 0 && col === 0) { could be if (!row && !col) { however that requires type coercion which is slower. Same with if (baseRow > 0) { can be if (baseRow) {

function spiralOrder1(matrix) {
 "use strict";
 var baseRow = 0, baseCol = 0, row = 0, col = 0, colStep = 0, rowStep = 0, count = 0;
 if (matrix.length === 1) { return matrix[0] } // Leetcode rules may need
 // [...matrix[0]] rather than matrix[0]
 if (matrix[0].length === 1) { return matrix.map(a => a[0]) }
 var width = matrix[0].length - 1;
 var height = matrix.length - 1;
 const total = matrix.length * matrix[0].length;
 const result = [];
 while (count++ < total) {
 result.push(matrix[row][col]);
 if (row === 0 && col === 0) {
 colStep = 1;
 rowStep = 0;
 } else if (row === baseRow && col === width) {
 colStep = 0;
 rowStep = 1;
 if (baseRow > 0) { baseCol ++ }
 } else if (row === height && col === width) {
 colStep = -1;
 rowStep = 0;
 baseRow ++;
 } else if (row === height && col === baseCol) {
 colStep = 0;
 rowStep = -1;
 width --;
 } else if (row === baseRow && col === baseCol) {
 colStep = 1;
 rowStep = 0;
 height --;
 }
 row += rowStep;
 col += colStep;
 }
 return result;
}

Performance

Leetcode has a focus on performance. Your function (with the array copy removed) is performant however there is room for some improvements.

Hints

The first row can be a straight copy of the first array e.g. result = [...matrix[0]] saving the need to execute all the statements in the while loop on the first row.

At each turn of the spiral you can know the distance to the next turn. This gives an opportunity to skip many of the (if) statements.

Each corner of the spiral is a right turn. The new direction can thus be computed as [col, row] = [-row, col] thus you only need to know when you are at a corner, not which corner you are at.

Gains

Implementing these optimization I get about a 10-20% performance increase on a 5 by 5 array.

That said there could be other algorithms that are even more performant.

Assuming that the array must not be changed in place the limiting factor is set by the best case time complexity of \$O(n)\$

• Samuel Samuelson: Missing the count var was definitely a huge mess-up on my end, I understand strict mode better now.