the_prole the_prole - 1 year ago 69
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.

  • 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

A visual illustration a possible rotation:

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


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
. Basic loops constructs like
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 = { }

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

=> [[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.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download