Solving array rotation problem is one of my favourite problem. You have to rotate a 2D array with certain conditions. This simple question has been asked in many different interviews in companies including Amazon, Microsoft, Apple. But the requirement might get different, such as:

  • Right rotate the elements of an array
  • Right rotate an array k times
  • Given an array, rotate the array to the right by k steps, where k is non-negative

But let's tart with the simplest one, rotating only once. Hope you will have an idea how to solve others

Rotate 2D Array Image

You are given an n x n 2D matrix that represents an image. Rotate the image by 90 degrees (clockwise).

Example

For

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

the output should be

rotateImage(a) =
    [[7, 4, 1],
     [8, 5, 2],
     [9, 6, 3]]

Solution

  • Start reading from last item of the first column and read all the values of the column, so for our example in the first iteration of our loop we will read [7,4,1]
  • Create temporary array for each iteration
  • Push this temporary array to the main array
  • End of the loop we will have our rotated array

Complexity: O(N^2)