the_prole the_prole - 9 months ago 41
Ruby Question

How to rotate a square matrix in place counter-clockwise ninety degrees in O(N) time using Ruby

How does one rotate a


  • square matrix represented by nested arrays e.g.
    [[1,2],[3,4]]

  • assuming the array elements are Integer objects

  • in place using arrays

  • counter-clockwise ninety degrees

  • in O(N) time

  • and implemented in Ruby

  • without using a special API like
    #transpose
    etc.



A visual illustration a possible rotation:

[1,2,3] [7,4,1]
[4,5,6] -> [8,5,2]
[7,8,9] [9,6,3]


EDIT

I really don't know how to be more specific. I want someone to provide a their own personal custom implementation in Ruby without using special APIs like
transpose
. Basic loops constructs like
#each
is fine. Please make it O(N).

Answer Source

Based on the answer to this question, the Ruby equivalent is:

a = [[1,2,3], [4,5,6], [7,8,9]]
size = a.size

r = Array.new(size) { Array.new(size) }

size.times { |i|
  size.times { |j|
    r[i][j] = a[size - j - 1][i]
  }
}

r
=> [[7,4,1], [8,5,2], [9,6,3]]

This is not an in-place rotation, but it takes O(N) time, assuming N = total elements in array.