Rotate Image - Leetcode 48 - Arrays & Strings (Python)

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

Please check my playlists for free DSA problem solutions:

My Favorite Courses:

Data Structures & Algorithms:

Python:

Web Dev / Full Stack:

Cloud Development:

Game Development:

SQL & Data Science:

Machine Learning & AI:

Рекомендации по теме

Комментарии

Master Data Structures & Algorithms For FREE at AlgoMap.io!

GregHogg

I love this series. Helps in understanding DSA a bit optimized way.

Kainum

Step 1 take transpose
Step 2 reverse row

jyotirmaysingh

When transposing the inner loop (i+1, n) definitely takes some extra thought. Wouldn't have been able to come up with that in an interview setting.

brandonblackwell

To conceptualize this, I tried flipping my notebook without rotating it. In every case this worked.

teostorm

Also, from the transposed matrix mT:
>>>list(map(operator.methodcaller('reverse'), mT))
does it inplace.

DrDeuteron

Without knowing this, what I found out is that you can rotate elements by "levels". Imagine the matrix as an onion, the first level would be the outermost layer consisting of the first and last row, and first and last column. So after rotating every element in the first level, you are left with an inner matrix of size N-1. So all you need to do is repeat the same process N // 2 times. N being the matrix' size.

Here's the code:
```
level = 1
N = len(matrix)
while level <= N // 2:
for i in range(level - 1, N - level):

tmp = matrix[level-1][i]
matrix[level-1][i] = matrix[-i-1][level-1]
matrix[-i-1][level-1] = matrix[-level][-i-1]
matrix[-level][-i-1] = matrix[i][-level]
matrix[i][-level] = tmp
level += 1
return matrix
```

I took advantage of python's negative indexing. The range keeps getting smaller until you reach the center of the matrix :)

ayrtoncoelho