An efficient way to cycle an array left n positions using only a single one-dimensional array.
Given an array containing n integers and a number d, a left rotation is performed on the array. Given the example of array [1,2,3,4,5], the shift will always be <= size of the array and ask for shift 1, then the output will be -> [2,3,4,5,1]. I wrote the code below and it works fine, can it be optimized further because my time complexity 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;
}
}
Solution
There is a clever trick in O(n)
to do this in place time:
- invert the entire array (i.e. between indices
0
(inclusive) andn
(exclusive)’; - Inverts the array parts between
0
(inclusive) and(n-k)
(exclusive). - Inverts the array parts between
indexes (n-k
) (inclusive) andn
(exclusive).
(This assumes 0 <= k <= n
; If this is not the case, simply find a different value of
k to a value that produces an equivalent rotation according to the above, such as k = k % n
if k >= 0
).
Each reversal operation is O(n), there are 3, so O(n
)
is still comprehensive. Inverting arrays in place is also easy, so there is no additional memory overhead.