How to rotate a matrix in place

I had a job interview once, and the guy dropped me a problem, I could not solve the problem.
This is partially because I get over emotional whenever I’m expected to live code some algorithm, low self esteem probably, but anyway the problem was something like this

You have a square matrix of NxN integers, come up with an algorithm to rotate the matrix 90 degrees clockwise without using an additional matrix.

After thinking and crunching for a while I tried something but my solution was not in place, meaning that I actually used a second matrix.

Some time after that I was practicing on InterviewBit, I was mostly learning Python and I needed some ideas for stuff to implement, and at some point the same old problem came back at me. This time I was alone, I had time, I was not emotional. It was revenge time.

How do you rotate a Matrix in place? Well you just do it, I spent some time trying to figure out the trick, turns out there is none.
This problem requires you to get your hands dirty.

The idea is the following, a square matrix is a series of concentric squares; the problem can be split into many smaller problems by rotating each square individually, starting from the outer square and going towards the center, and except for the first iteration, being careful not to mess up the outer squares which are already rotated.
For each concentric square, at each position, there is a precise sequence of four moves, or swaps, that when put together allow you to have the whole sub-square rotated by 90 degrees clockwise.

    A B C D
    E     F
    G     H
    I J K L

    First iteration:
        A goes to D which goes to L which goes to I which goes to A
        B goes to F which goes to K which goes to G which goes to B
        .... 

The position where you start swapping at each sub-square has to increase by one every time you move closer to the center of the matrix, or you’ll mess up the outer square. Same reasoning applies for the position where you stop swapping, which must decrease by one.

    A B C D
    E 1 2 F
    G 3 4 H
    I J K L

    First iteration:
        A goes to D which goes to L which goes to I which goes to A
        B goes to F which goes to K which goes to G which goes to B
        ....
    Second iteration:
        1 goes to 2 which goes to 4 which goes to 3 which goes to 1

    Done!

That’s it. It boils down to figuring out which element goes where for every sub-square.
You can find the full implementation at the end, this is some sample output.

With N = 3

Original matrix:
  [0, 1, 2]
  [3, 4, 5]
  [6, 7, 8]
Rotated matrix:
  [6, 3, 0]
  [7, 4, 1]
  [8, 5, 2]

With N = 8

Original matrix:
  [ 0,  1,  2,  3,  4,  5,  6,  7]
  [ 8,  9, 10, 11, 12, 13, 14, 15]
  [16, 17, 18, 19, 20, 21, 22, 23]
  [24, 25, 26, 27, 28, 29, 30, 31]
  [32, 33, 34, 35, 36, 37, 38, 39]
  [40, 41, 42, 43, 44, 45, 46, 47]
  [48, 49, 50, 51, 52, 53, 54, 55]
  [56, 57, 58, 59, 60, 61, 62, 63]
Rotated matrix:
  [56, 48, 40, 32, 24, 16,  8, 0]
  [57, 49, 41, 33, 25, 17,  9, 1]
  [58, 50, 42, 34, 26, 18, 10, 2]
  [59, 51, 43, 35, 27, 19, 11, 3]
  [60, 52, 44, 36, 28, 20, 12, 4]
  [61, 53, 45, 37, 29, 21, 13, 5]
  [62, 54, 46, 38, 30, 22, 14, 6]
  [63, 55, 47, 39, 31, 23, 15, 7]

This is the code, in python.

"""
You are given an N x N 2D matrix representing an image.
Rotate the image by 90 degrees (clockwise).
You need to do this in place.

Example:

If the array is

[
    [1, 2],
    [3, 4]
]
Then the rotated array becomes:

[
    [3, 1],
    [4, 2]
]
"""

import math

def swap(pos_a, pos_b, array, side_len):
    """
    Swaps two locations values
    """
    src_row = int(pos_a / side_len)
    src_col = int(pos_a % side_len)

    dst_row = int(pos_b / side_len)
    dst_col = int(pos_b % side_len)

    tmp = array[dst_row][dst_col]
    array[dst_row][dst_col] = array[src_row][src_col]
    array[src_row][src_col] = tmp


def rotate_outer(start_pos, count, sources, side_len):
    """
    Rotates an outer square by 90 degrees clockwise.
    Starting from start_pos, it rotates count-1 consecutive locations,
    the last location is not to be rotated as the first location will end up there.
    """
    for i in range(count - 1):
        actions = [0, 0, 0, 0]
        current_pos = start_pos
        for j in range(4):
            row = int(math.floor(current_pos / side_len))
            col = int(current_pos % side_len)
            destination_pos = (side_len - row) + (col * side_len) - 1
            actions[3 - j] = destination_pos
            current_pos = destination_pos

        for a in range(len(actions) - 1):
            # Swap every pair of locations
            swap(actions[a], actions[a + 1], sources, side_len)

        start_pos += 1


if __name__ == "__main__":

    N = 10
    A = [[y*N+x for x in range(N)] for y in range(N)]

    print "Original matrix:"
    for row in A:
        print " ", row

    n = len(A)
    length_to_rotate = n
    start_rotation_from = 0

    while length_to_rotate > 1:
        rotate_outer(start_rotation_from, length_to_rotate, A, n)
        start_rotation_from += 1 + n
        length_to_rotate -= 2

    print "Rotated matrix:"
    for row in A:
        print " ", row
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Blog at WordPress.com.

Up ↑

%d bloggers like this: