Efficient way to cycle left through an array by n positions using only one 1D array.
Given an array of n integers and d, perform left rotations on the array. an example of a given array is [1,2,3,4,5], and the shifts will always be <= the size of the array and ask for a shift by 1, then the output will be → [2,3,4,5,1]. I wrote below code which works fine, this can be further optimized as the time complexity for mine is O (n ^ 2)
code:
public static int [] arrayLeftRotation (int [] a, int n, int k) {
if (n == 1 || n == k)
return a;
else {
int track = 0;
while (track < k) {
int start = a[0];
for (int i = 0; i < n - 1; i++) {
a[i] = a[i + 1];
}
a[n - 1] = start;
track++;
}
return a;
}
}
source to share
There's a neat trick to do it locally, in O(n)
time:
- Invert the entire array (i.e. between indices
0
(inclusive) andn
(exclusive) `; - Reverse the part of the array between the indices
0
(inclusive) and(n-k)
(exclusive) - Reverse the part of the array between the indices
(n-k)
(inclusive) andn
(exclusive)
(It is assumed that 0 <= k <= n
if it is not, just find another value k
for the value that gives the equivalent rotation as above, for example k = k % n
if k >= 0
)
Each of the reversal operations O(n)
, there are 3 of them, so it is still O(n)
a whole. It's also easy to modify the array in place, so there is no additional memory overhead.
source to share