Hello all,
Link to Problem description: https://leetcode.com/problems/rotate-array/
Solution approach: multiple ways
Solution approach 1:
Brute force moving all elements by 1 position, k times. Time Complexity O(n*k). Not great! In-place, so space complexity O(1).
Solution Approach 2:
Making a temporary copy(tmp) of k rightmost elements. Move all preceding elements towards right maintaining order, by k positions i.e. towards the rightmost end. Copy all tmp elements towards k spaces created at the leftmost end.
class Solution { public void rotate(int[] nums, int k) { int n = nums.length; if (n < 2) return; k = k % n; int[] tmp = Arrays.copyOfRange(nums, n-k, n); for (int i=n-k; i>=1; i--) nums[i+k-1] = nums[i-1]; for (int i=tmp.length-1; i>=0; i--) nums[i] = tmp[i]; } }
Time Complexity: O(n)
Space Complexity: O(k)
Solution 3:
Using in-place reverse array custom method.
class Solution { public void rotate(int[] nums, int k) { int n = nums.length; if (n < 2) return; k = k % n; reverse(nums, 0, n-1-k); reverse(nums, n-k, n-1); reverse(nums, 0, n-1); } public void reverse(int[] arr, int st, int end) { int mid = (end-st+1)%2==0 ? (end+st)/2+1 : (end+st)/2; for (int i=st; i<mid; i++) { // < : don't reverse mid with itself on odd nElems arr[i] = arr[i] + arr[end-(i-st)]; arr[end-(i-st)] = arr[i] - arr[end-(i-st)]; arr[i] = arr[i] - arr[end-(i-st)]; } } }
Time Complexity: O(n)
Space: In-place; O(1).
No comments:
Post a Comment