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.
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.
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 n−k 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
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.