LeetCode Entry
48. Rotate Image
Rotate square matrix
48. Rotate Image medium substack youtube
https://dmitrysamoylenko.com/leetcode/
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/1348
Problem TLDR
Rotate square matrix
Intuition
Go layer by layer and do 4-swaps in place on a single side
Approach
- reverse + transpose also works (in any order)
Complexity
-
Time complexity: \(O(n)\)
-
Space complexity: \(O(1)\)
Code
fun rotate(m: Array<IntArray>): Unit {
val n = m.size;
for (l in 0..<n / 2) for (s in l..<n - l - 1) {
val oi = n - 1 - l; val oj = n - 1 - s; val t = m[oi][oj]
m[oi][oj] = m[s][oi]; m[s][oi] = m[l][s]
m[l][s] = m[oj][l]; m[oj][l] = t
}
}
pub fn rotate(m: &mut Vec<Vec<i32>>) {
m.reverse();
for i in 0..m.len() { for j in i+1..m.len() {
let t = m[i][j]; m[i][j]=m[j][i]; m[j][i] = t
}}
}