Given an integer array arr[] of size N, the task is to print all possible rotations of the array.
Examples:
Input: arr[] = {1, 2, 3, 4}
Output: {1, 2, 3, 4}, {4, 1, 2, 3}, {3, 4, 1, 2}, {2, 3, 4, 1}
Explanation:
Initial arr[] = {1, 2, 3, 4}
After first rotation arr[] = {4, 1, 2, 3}
After second rotation arr[] = {3, 4, 1, 2}
After third rotation arr[] = {2, 3, 4, 1}
After fourth rotation, arr[] returns to its original form.Input: arr[] = [1]
Output: [1]
Approach 1:
Follow the steps below to solve the problem:
- Generate all possible rotations of the array, by performing a left rotation of the array one by one.
- Print all possible rotations of the array until the same rotation of array is encountered.
Below is the implementation of the above approach :
Javascript
<script>// javascript program to print// all possible rotations// of the given array// Global declaration of arrayarr = Array.from({length: 10000}, (_, i) => 0);// Function to reverse array // between indices s and efunction reverse(arr, s , e){ while(s < e) { var tem = arr[s]; arr[s] = arr[e]; arr[e] = tem; s = s + 1; e = e - 1; }}// Function to generate all// possible rotations of arrayfunction fun(arr , k){ var n = 4 - 1; var v = n - k; if (v >= 0) { reverse(arr, 0, v); reverse(arr, v + 1, n); reverse(arr, 0, n); }}// Driver code arr[0] = 1; arr[1] = 2; arr[2] = 3; arr[3] = 4; for(i = 0; i < 4; i++) { fun(arr, i); document.write("["); for(j = 0; j < 4; j++) { document.write(arr[j] + ", "); } document.write("]<br>"); }// This code is contributed by 29AjayKumar </script> |
[1, 2, 3, 4] [4, 1, 2, 3] [2, 3, 4, 1] [3, 4, 1, 2]
Time Complexity: O (N2)
Auxiliary Space: O (1)
Approach 2: Follow the steps below to solve the problem:
- Initialize an array arr and get its length.
- Create a new array rotatedArr of twice the length of arr.
- Copy the elements of arr into rotatedArr twice, once in the first half and then in the second half starting from the index equal to the length of arr.
- Iterate over the indices from 0 to the length of arr and generate all possible rotations by printing the sub-array starting from that index and having the length equal to the length of arr. The sub-array is formed by iterating over the elements of rotatedArr starting from the index i and ending at index i+n-1, where n is the length of arr.
Below is the implementation of the above approach:
Javascript
let arr = [1, 2, 3, 4];let n = arr.length;let rotatedArr = new Array(2*n);// Copy the array twice into the rotatedArrfor (let i = 0; i < n; i++) { rotatedArr[i] = arr[i]; rotatedArr[i+n] = arr[i];}// Nikunj Sonigara// Generate all possible rotationsfor (let i = 0; i < n; i++) { let str = "["; for (let j = i; j < i+n; j++) { str += rotatedArr[j]; if(j != i+n-1) str += " "; } str += "] "; console.log(str);} |
[1 2 3 4] [2 3 4 1] [3 4 1 2] [4 1 2 3]
Time Complexity: O(N2)
Auxiliary Space: O(N)
Please refer complete article on Print all possible rotations of a given Array for more details!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
