Spiral Matrix: two separate algorithm challenge questions

August 1, 2022
Algorithms

Goals

  1. If given an integer N, return an n x n Matrix in a matrix spiral.

  2. Given an m x n matrix, return all elements in a spiral (clockwise order)

(Spoiler Alert: Below the fold, you’ll find the solutions so if you haven’t already tried them yourself then don’t scroll down. If you don’t mind seeing the approach and gaining some insight before you try or if you have already solved it, scroll on 🤘🏽)

The initiation Well, Quinta da Regaleir, Sintra, Portugal, 2022

The above items are actually two separate challenge questions. The algorithm for each is almost exactly the same, with a few minor modifications. I started working on item number 1 and initially, I made some good progress but after a few days of scratching my head, I decided it would be wiser to get some assistance and after some research realized a few important things.

Thoroughly whiteboarding the steps (on paper or on an actual whiteboard) toward a solution before coding is immensely valuable. If you can completely pseudocode it, you’re golden.

Breaking the problem into smaller sub-problems will help a lot.

I am a visual learner, so when I try to build a theoretical model of the solution, I have a better understanding of where I’m going.

Challenge 1

Create a function that takes an integer N and returns a NxN Matrix Spiral

For Example, a Function call with input of 3 matrix(3)

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

I did sub-divide the problem into smaller ones and was able to pass the initial test cases but eventually, the test cases got too big to solve, which is where I hit a wall.

One of the mistakes I made when starting my initial solution was to glaze over a matrix representation of the final solution. Inspecting a drawing of one more thoroughly would have given me more clues as to the pivotal pieces of this algorithm—counters.

Once you set up all your variables to represent all the four corners of the matrix or each start row, start column, end column, and end row, one while loop and four separate for loops within it are all that is needed.

n x n Matrix

The Psuedocode that helped me get my head around the challenge, courtesy of John Peña

  • Create an empty array of arrays called ‘results’
  • Create a counter variable, starting at 1
  • As long as (start column <= end column) AND (start row <= end row)
    • Loop from start column to end column
      • At results[start_row][i] assign counter variable
      • Increment counter
    • Increment start row
    • Loop from start row to end row
      • At results[i][end_column] assign counter variable
      • Increment counter
    • Decrement end row
    • …repeat for the other two sides

Starting with the first three bulleted items above

  const matrix = (n) => {  
  //Set the empty array
  const results = [];  

  //Starting our first loop
  //for each iteration here we are going to loop as long as i is          
  //less than n we are going to push an empty sub array into results
   for (let i = 0; i < n; i++) {
       results.push([])
   }
  //Set our starting variables
  let counter = 1; // what number we are pushing in
  let startColumn = 0; // keep track of start column
  let endColumn = n - 1; // keep track of last index
  let startRow = 0; // keep track of start row
  let endRow = n - 1; // keep track of last index
}

Once that is set up, insert a while loop as long as the conditions previously mentioned are met in the pseudo-code above (3rd bullet point) and start iterating the top row from left to right, assigning values per column as you move right.

Starting with the first three bulleted items above

while (startColumn <= endColumn && startRow <= endRow) 
    {
      // Start Top w/ row, iterating by each column and assigning values
      for (let i = startColumn; i <= endColumn; i++) { 
        //Assign values per 'column' on the startRow
        results[startRow][i] = counter;
      counter++;
    }
     startRow++; // once the for loop finishes here go down one row because you're done

Now move onto the next row and iterate from 'start row' to 'end row' going down, along right 'column'; decrement right col by 1

   // Right column
   for (let i = startRow; i <= endRow; i++) { 
        results[i][endColumn] = counter; 
   counter++;
   }
   endColumn--; // start moving from right to left at this point so we decrement this

Top row & right column are done; now build the bottom row going right to left

   // Bottom row
   for (let i = endColumn; i >= startColumn; i--) {
       results[endRow][i] = counter;
   counter++;
   }
   endRow--; // decrement because bottom row is done, move up one

Reach the end by returning to 'Start Column' (left most col) and build from the bottom up

   // start column
     for (let i = endRow; i >= startRow; i--) {
        results[i][startColumn] = counter;
     counter++;
     }
     startColumn++;

} // While Loop Ends Here

return results; // finally once all loops are finished we return the results array
}

Final Code

const matrix = (n) => {
  const results = [];for (let i = 0; i < n; i++) {
    results.push([]);
  }let counter = 1;
  let startColumn = 0;
  let endColumn = n - 1;
  let startRow = 0;
  let endRow = n - 1;
  while (startColumn <= endColumn && startRow <= endRow) {
    // Top row
    for (let i = startColumn; i <= endColumn; i++) {
      results[startRow][i] = counter;
      counter++;
    }
    startRow++;// Right column
    for (let i = startRow; i <= endRow; i++) {
      results[i][endColumn] = counter;
      counter++;
    }
    endColumn--;// Bottom row
    for (let i = endColumn; i >= startColumn; i--) {
      results[endRow][i] = counter;
      counter++;
    }
    endRow--;// start column
    for (let i = endRow; i >= startRow; i--) {
      results[i][startColumn] = counter;
      counter++;
    }
    startColumn++;
  }return results;
}
  • The complete code can be found on a Replit
    (Replit is currently having issues with Hacker and Teams so if you don’t see code right away, please check back or build out the above algorithm in your own IDE to test it and have fun).

Challenge 2

Given an m x n matrix, return all elements in a spiral (clockwise order)

The only difference between this challenge and the first one is the parameter requirement.

Challenge 1 asks us to return a spiral matrix when given an integer N and challenge 2 asks us to return a spiral matrix when given an m x n matrix, so the parameter will be a 2-dimensional array, which you’ll need to iterate through and output a spiral matrix for.

  • The algorithm for this challenge is basically identical save for very minor differences.
  • See the Replit solution and compare
    (Replit is currently having issues with Hacker and Teams so if you don’t see code right away, please check back or build out the above algorithm in your own IDE to test it and have fun).

Recent Posts

LinkedInTumblr

Share your thoughts

Discover more from O Web Designs

Subscribe now to keep reading and get access to the full archive.

Continue reading