54. Spiral Matrix | LeetCode Medium | Python Solution | Array, Matrix, Simulation

Опубликовано: 22 Февраль 2025
на канале: Shaheer Shukur

206

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

LeetCode Problem Link: https://leetcode.com/problems/spiral-...
Solution (Python Code): https://github.com/shaheershukur/Leet...

Spiral Matrix II:    • 59. Spiral Matrix II | LeetCode Mediu...
Spiral Matrix III:    • 885. Spiral Matrix III | LeetCode Med...
Spiral Matrix IV:    • 2326. Spiral Matrix IV | LeetCode Med...

#leetcode #python #solution

Problem Statement:
Given an m x n matrix, return all elements of the matrix in spiral order.
______________________________________________________________

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 an m x n matrix, and we need to go through its elements in a spiral order and return the result.
with the help of an example, lets closely look at how the spiral traversal works.

the spiral path starts at the indices 0, 0. i.e., from the first element.
after visiting a cell, we will store that value in the result and empty that cell, so that we can identify it as already visited cell.
from here, we will be moving towards the right direction.

we know that in a matrix, in order to move in any 4 direction, we must add some value to either i or j index.
so, for moving towards the right direction, we must add 0 and 1 to the i and j indices respectively.

in this case, the next i and next j will be 0 and 1.
so we will move to the indices 0, 1.

after noting down the value, we will continue moving in the same direction.
from the cell 3, we cannot move forward in the same direction, because the next cell is outside the matrix.
therefore, at this point, we need to take a right turn to form a spiral.

since we are currently moving in the right direction, after taking the right turn, we will be moving downwards.
ie, the values to be added to the i and j indices are 1 and 0 respectively.
so, for moving down, we must add 1 and 0 to the i and j indices respectively.
now the next i and next j are 1 and 2.
so we will move to the indices 1, 2.

similarly, we will be taking right turns at cell 9 and cell 7.
at cell 4, we can see that the next cell is already visited, and therefore we cannot move in that direction.
so we will take a right turn again.

at cell 5, we cannot move forward because the cell 6 is already visited.
therefore we will take a right turn again.
now, even after taking a right turn we cannot move forward, because the cell 8 is also already visited.
and therefore, we can stop here, and this is the final result we have.

now lets take one more example.
here, after reaching the cell 3, we cannot move forward because the next cell is out of the matrix.
therefore, we will take a right turn.
even after taking a right turn, the next cell is out of the matrix.
therefore we can stop here, and this is the final result.

now lets code the solution.
we will store the number of rows and columns in these variables.
we will be storing the result in this variable, and at last we will be returning it.
we will start from the first cell 0, 0. so we will set both i and j to 0.
since we will be in the right direction initially, we will set the direction i and direction j to 0 and 1 respectively.

we will use an infinite while loop to go through the matrix.
during each loop, we will first add the current element to the result.
and since we have visited the current element, we will empty the cell by setting it to None.

we need the indices of the next cell.
so we will add the direction indices with the current indices and store it in these variables.

to check whether a cell indices are inside the matrix and not yet visited, we will write a separate function.
now we will check whether the next indices we are about to visit are inside the matrix and not yet visited.
if yes, then we can use those next indices.
so we will be setting it to i and j.

else, we need to take a right turn from the current cell.
one interesting thing to note about taking right turn is that, we can deduce a formulae for updating the direction indices.
here from the table, we can see that, the direction index i after taking a right turn is equal to the direction index j.
and the direction index j after taking a right turn is equal to the negative direction index i.
so we can write this statement for taking a right turn.

after updating the direction indices, we add it to the respective cell indices.
and also, we need to check, whether we are able to move forward after taking a right turn.
if not, then we have already reached the end, and therefore we can break the loop.