LeetCode Medium: Rotate Array

Hello all,

Problem of the day: Rotate Array (rotate towards right, k times)

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).

Happy Coding!

Become a Patron!