Rotate Array

Lesson: Array Manipulation

Question: Given an array, rotate the array to the right by k steps, where k is a non-negative integer.

Follow up:

  • Try to come up as many solutions as you can! (There are at least 3 different ways to solve this problem)

  • Could you do it in-place with O(1) extra space?

Solution

Approach 1: Brute Force

The simplest approach is to rotate all the elements of the array in k steps by rotating the elements by 1 unit in each step.

See Approach 1

Complexity Analysis

  • Time complexity: O(n×k) (All the numbers are shifted by one step(O(n)) k times)

  • Space complexity: O(1). No extra space is used.

Approach 2: Using An Extra Array

We can utilize an extra array in which we place every element of the array at its correct position i.e. the number at index i in the original array is placed at the index  (i+k)% length of array. Then we copy the new array into the original one.

See Approach 2

Complexity Analysis

  • Time complexity: O(n). One pass is used to put the numbers in the new array, and another pass is used to copy the new array to the original one.

  • Space complexity: O(n). Another array of the same size is used.

Approach 3: Using Reverse

This approach is based on the fact that when we rotate the array k times, k elements from the back end of the array come to the front and the rest of the elements from the front shift backwards.

In this approach, we firstly reverse all the elements of the array. Then, reversing the first k elements followed by reversing the rest nk elements gives us the required result.

Let n = 7 and k = 3.

Example:

  • Original List: 1 2 3 4 5 6 7

  • After reversing all numbers: 7 6 5 4 3 2 1

  • After reversing first k numbers: 5 6 7 4 3 2 1

  • After revering last n-k numbers : 5 6 7 1 2 3 4 --> Result

See Approach 3

Complexity Analysis

  • Time complexity: O(n). (n elements are reversed a total of three times)

  • Space complexity: O(1). (No extra space is used)

We’re done!


Interested in breaking into Computer Science? Eager to expand your knowledge base and learn new things? Enjoy problem solving? If so, this newsletter is for you. Subscribe to get fully explained interview prompts commonly given in engineering interviews, from Arrays to Dynamic Programming. Questions come out weekly and are also categorized by subject and difficulty.

Subscribe to get full access to the newsletter. Never miss an update.