Keep and Share logo     Log In  |  Mobile View  |  Help  
 
Visiting
 
Select a Color
   
 












01.DS.02.04. Rotate an Array by N Elements.html -- 1.9 meg
 Rotate an Array by N Elements - Coderust: Hacking the Coding Interview
Log InJoin for free
Back To Module Home
Data Structures
0% completed
Prelude
Arrays
Rotate an Array by N Elements
Linked Lists
Strings
Stacks and Queues
Trees
Graphs
Further Reading
Mark Module as Completed
Ask a Question

Rotate an Array by N Elements

Given an integer array, rotate it by 'n' elements.

We'll cover the following

Statement#

We’re given an array of integers, nums. Rotate the array by n elements, where n is an integer:

  • For positive values of n, perform a right rotation.
  • For negative values of n, perform a left rotation.

Make sure we make changes to the original array.

Example#

Let’s look at the original array below:

garray012345678911020059863211940

On the original array, we perform a left rotation when n is equal to −1-1−1. The modified array looks like this:

garray012345678910200598632119401

Similarly, when n is equal to 222, we perform two right rotations one after the other. The modified array looks like this:

garray012345678994011020059863211

Sample input#

nums = [1, 10, 20, 0, 59, 86, 32, 11, 9, 40]
n = 2

Expected output#

[9, 40, 1, 10, 20, 0, 59, 86, 32, 11]

Try it yourself#

C++
Java
Python
JS
Ruby
Go
1
2
3
4
5
6
7
8
#include <iostream>
#include <vector>
using namespace std;
void RotateArray(vector<int>& nums, int n) {
    //TODO: Write - Your - Code
}
#
#include <iostream> #include <vector> using namespace std; void RotateArray(vector<int>& nums, int n) { //TODO: Write - Your - Code }
Enter to Rename, Shift+Enter to Preview
Test
Save
Reset

Solution 1#

Here’s how the solution works:

  • Normalize the rotations, so they do not exceed the length of the array. For example, for an array of length 101010, rotating by 141414 elements is the same as rotating by (14%10) 4 elements.

  • Convert negative rotations to positive rotations.

  • Reverse the elements of the original array.

  • Reverse the elements from 000 to n−1n-1n−1.

  • Reverse the elements from nnn to length−1length-1length−1.

Let’s run this on the array below for n=2n=2n=2:

Created with Fabric.js 3.6.6Let's run an example on the above array that requires n = 2 rotations.012345678911020059863211940
1 of 4
C++
Java
Python
JS
Ruby
Go
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
#include <iostream>
#include <vector>
using namespace std;
void ReverseArray(vector<int>& nums, int start, int end) {
    while (start < end) {
        int temp = nums[start];
        nums[start] = nums[end];
        nums[end] = temp;
        ++start;
        --end;
    }
}
void RotateArray(vector<int>& nums, int n) {
    int len = nums.size();
    // Normalizing the 'n' rotations
    n = n % len;
    if (n < 0) {
        n = n + len;
    }
    // Let's partition the array based on rotations 'n'
    ReverseArray(nums, 0, len - 1);
    ReverseArray(nums, 0, n - 1);
    ReverseArray(nums, n, len - 1);
}
int main() {
    vector<int> nums = {1, 10, 20, 0, 59, 86, 32, 11, 9, 40};
#
#include <iostream> #include <vector> using namespace std; void ReverseArray(vector<int>& nums, int start, int end) { while (start < end) { int temp = nums[start]; nums[start] = nums[end]; nums[end] = temp;
Enter to Rename, Shift+Enter to Preview
Run
Save
Reset

Time complexity#

The time complexity of the code is linear, O(n)O(n)O(n).

Space complexity#

The space complexity of the code is constant, O(1)O(1)O(1).

Solution 2#

Here is how the solution works:

  • Normalize the rotations, so they do not exceed the length of the array.
  • Convert negative rotations to positive rotations.
  • Store the last nnn elements into a temporary array.
  • Shift the original array towards the right by l−nl-nl−n places. Here, lll is the length of the ​array.
  • Copy the temporary array at the beginning of the original array.

Let’s run this on the array below for n=−3n=-3n=−3.​

Created with Fabric.js 3.6.6012345678911020059863211940Let's run an example on the above array that requires n = -3 rotations.Input array
1 of 5
C++
Java
Python
JS
Ruby
Go
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
#include <iostream>
#include <vector>
using namespace std;
void RotateArray(vector<int>& nums, int n) {
    int len = nums.size();
    // Let's normalize rotations
    n = n % len;
    if (n < 0) {
        n = n + len;
    }
    vector<int> temp(n);
    // copy last 'n' elements of array into temp
    for (int i = 0; i < n; i++) {
        temp[i] = nums[len - n + i];
    }
    // shift original array
    for (int i = len - 1; i >= n; i--) {
        nums[i] = nums[i - n];
    }
    // copy temp into original array
    for (int i = 0; i < n; i++) {
        nums[i] = temp[i];
    }
}
#
#include <iostream> #include <vector> using namespace std; void RotateArray(vector<int>& nums, int n) { int len = nums.size(); // Let's normalize rotations n = n % len;
Enter to Rename, Shift+Enter to Preview
Run
Save
Reset

Time complexity#

The time complexity of this code is O(n)O(n)O(n), where n is the number of elements in the array.

Space complexity#

The space complexity of this code is O(n)O(n)O(n) because we use another temporary array of the same size.

Back
Find the Smallest Common Number
Next
Find Low/High Index of a Key in a Sorted Array
Mark as Completed
Report an Issue


Creation date: Oct 7, 2022 7:32pm     Last modified date: Oct 7, 2022 7:32pm   Last visit date: Nov 12, 2024 7:50am
    Report Objectionable Content