885. Spiral Matrix III | LeetCode Medium | Python Solution | Array, Matrix, Simulation

Показать описание

Leetcode medium problem 885. Spiral Matrix III, detailed explanation and solution in python language.

#leetcode #python #solution

Problem Statement:
You start at the cell (rStart, cStart) of an rows x cols grid facing east. The northwest corner is at the first row and column in the grid, and the southeast corner is at the last row and column.

You will walk in a clockwise spiral shape to visit every position in this grid. Whenever you move outside the grid's boundary, we continue our walk outside the grid (but may return to the grid boundary later.). Eventually, we reach all rows * cols spaces of the grid.

Return an array of coordinates representing the positions of the grid in the order you visited them.
______________________________________________________________

LeetCode problem solving helps in improving one's problem solving and coding skills . Also, it helps in clearing technical interviews at top tech companies like Microsoft, Google, Amazon, Facebook, Walmart, Apple etc.
(FAANGM, MAANGM, Product based companies)

CC of video:
we are given number of rows and columns of a matrix and also a random starting cell indices inside the matrix.
from this particular cell, we need to traverse through the matrix in a spiral order till we visit all the cells in the matrix, and return the array of cell indices we have visited in order.
an important thing to note here is that, the spiral can even go out of the matrix.

before we move on to the solution, it would be better to watch these two previous videos for a better understanding.
first, lets take an example, and observe how the pattern of spiral is working.
lets say, we are given the number of rows 3 and number of columns 4.

so we will have a matrix containing 3*4=12 cells.
lets say, we are given the starting cell indices (1, 2).
for simplicity, we can rename rStart and cStart to i and j respectively.

now, from this cell, we need to traverse in spiral order.
if we look at it closely, we can observe that there is a repeating pattern in the spiral.
from the starting cell, the spiral visited 1 cell, then it took a right turn.
then again it visited 1 cell and took a right turn.

then it visited 2 cells, and took a right turn.
then again it visited 2 cells, and took a right turn.

then it visited 3 cells, and took a right turn.
then again it visited 3 cells, and took a right turn.

then it visited 4 cells, and took a right turn.
then again it visited 4 cells, and took a right turn.

here we can observe that, twice after visiting some number of cells and changing the direction, the number of cells visited in the next round is incremented by 1.
so all we have to do is to simulate this behavior from the given starting cell.

now lets code the solution.

using the given number of rows and columns, we will create a matrix.
since we need only the indices we are visiting in the final result, we can set all the elements to None.

for simplicity, we can refer to the starting indices rStart and cStart as i and j respectively.
we will be storing the result in this array, and at last we will be returning it.
since we are going to start the traversal with the given starting cell, we can include that cell in the result array initially.

we know that, the traversal starts towards the right direction.
so we can set the direction indices initially to 0 and 1 respectively.

as we observed, the pattern starts with visiting 1 cell, and then after doing it twice, it increments the number of cells visited in the next round.
we can store these initial values to these variables.

using an infinite while loop, we can loop through the matrix.
we will be breaking the loop once we have stored all the visited cells of the matrix in the result array.

to move to the next cell, we will add the direction indices to the cell indices i and j respectively.
now, since the spiral path can even go out of the matrix, we must make sure to add the indices to the result array only if the indices i and j are inside the matrix.

during each iteration, we will decrement the number of cell visited.
once it becomes zero, its time to take a right turn, so we will update the direction indices.
also we need to check whether, for the current cell visit number, we have done it twice or not.

if we have done it twice, the twiceCounter will be 0.
in that case, we will reset the twiceCounter to 2, and we will increment the number of cell visits to the next round.

and if we haven't done the current round twice, we will reset the number of cell visits, which is equal to the number in the next round - 1.