Problem

Given an array, rotate the array to the left by k steps, where k is non-negative. Follow up: Rotate an array in place.

Examples

Example 1:

1
2
3
4
5
6

Input: nums = [1,2,3,4,5,6,7], k = 3
Output: [4,5,6,7,1,2,3]
Explanation:
rotate 1 steps to the right: [2,3,4,5,6,7,1]
rotate 2 steps to the right:  [3,4,5,6,7,1,2]
rotate 3 steps to the right: [4,5,6,7,1,2,3]

Similar problem

We have already seen Rotate an Array to Right.

Lets use reverse function again.

Solution

Method 1 - Trivial Solution Using Extra Space

To rotate an array left by k positions, we need to shift the array to the left by k % n, making space on the right for the first k % n elements of the original array. The simple solution involves using a temporary array of size k % n to store the leftmost k % n elements. Then, shift the original array to the left by k % n positions, and finally copy the saved elements from the temporary array to the right side of the original array.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class Solution {
    public void rotateLeft(int[] nums, int k) {
        int n = nums.length;
        k = k % n; // Ensure k is within the bounds of the array size
    
        int[] result = new int[nums.length];
    
        for (int i = 0; i < n - k; i++) {
            result[i] = nums[k + i];
        }
    
        for (int i = 0; i < k; i++) {
            result[n - k + i] = nums[i];
        }
    
        System.arraycopy(result, 0, nums, 0, nums.length);
    }
    
    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] arr = {1, 2, 3, 4, 5};
        int k = 2;
        sol.rotateLeft(arr, k);
        for (int num : arr) {
            System.out.print(num + " ");
        }
        // Expected output: [3, 4, 5, 1, 2]
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution:
    def rotateLeft(self, nums: List[int], k: int) -> None:
        n = len(nums)
        k = k % n  # Ensure k is within the bounds of the array size

        # Create a temporary array to store the result
        result = [0] * n

        # Copy the elements after the first k elements to the beginning of the result array
        for i in range(n - k):
            result[i] = nums[k + i]

        # Copy the first k elements to the end of the result array
        for i in range(k):
            result[n - k + i] = nums[i]

        # Copy the result array back into the original array
        for i in range(n):
            nums[i] = result[i]

# Example usage
sol = Solution()
arr = [1, 2, 3, 4, 5]
k = 2
sol.rotateLeft(arr, k)
print(arr)  # Expected output: [3, 4, 5, 1, 2]

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(n), due to the temporary array

Method 2 - In Place Using Bubble Sort

To rotate an array left in place with O(1) space, this solution performs bubble sort-like operations k times.

Here is an example (length=7, k=3):

1
2
3
4
5
6
7

i=0
0 1 2 3 4 5 6
1 2 3 4 5 6 0
...
2 3 4 5 6 0 1
...
3 4 5 6 0 1 2

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

class Solution {
    public void rotateLeft(int[] arr, int k) {
        if (arr == null || k < 0) {
            throw new IllegalArgumentException("Illegal argument!");
        }

        int n = arr.length;
        k = k % n; // Ensure k is within the bounds of the array size

        for (int i = 0; i < k; i++) {
            for (int j = 0; j < n - 1; j++) {
                swap(arr, j, j + 1);
            }
        }
    }

    void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] arr = {1, 2, 3, 4, 5};
        int k = 2;
        sol.rotateLeft(arr, k);
        for (int num : arr) {
            System.out.print(num + " ");
        }
        // Expected output: [3, 4, 5, 1, 2]
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution:
    def rotateLeft(self, arr: list[int], k: int) -> None:
        if arr is None or k < 0:
            raise ValueError("Illegal argument!")

        n = len(arr)
        k = k % n  # Ensure k is within the bounds of the array size

        for i in range(k):
            for j in range(n - 1):
                self.swap(arr, j, j + 1)
    
    def swap(self, arr: list[int], i: int, j: int) -> None:
        arr[i], arr[j] = arr[j], arr[i]

Complexity

  • ⏰ Time complexity: O(n * k)
  • 🧺 Space complexity: O(1)

Method 3 - In Place Using Reversal

To perform a left rotation on an array, we can use the reverse operation which involves three main steps. This method is efficient as it reverses segments of the array in place.

Algorithm

To rotate an array to the left by a given index, the algorithm involves three simple reversing steps:

  1. Reverse the portion of the array from the start to k-1.
  2. Reverse the portion of the array from k to the end.
  3. Reverse the entire array.

For example, given the array [1, 2, 3, 4, 5, 6] and k = 2:

  1. Reverse the first part [1, 2] → [2, 1], resulting in [2, 1, 3, 4, 5, 6].
  2. Reverse the second part [3, 4, 5, 6] → [6, 5, 4, 3], resulting in [2, 1, 6, 5, 4, 3].
  3. Reverse the whole array [2, 1, 6, 5, 4, 3] → [3, 4, 5, 6, 1, 2].

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

class Solution {
    public void rotateArrayLeft(int[] arr, int k) {
        int n = arr.length;
        k = k % n; // Ensure k is within bounds

        reverse(arr, 0, k - 1);        // Reverse the first part
        reverse(arr, k, n - 1);        // Reverse the second part
        reverse(arr, 0, n - 1);        // Reverse the whole array
    }
    
    public void reverse(int[] arr, int start, int end) {
        while (start < end) {
            swap(arr, start, end);
            start++;
            end--;
        }
    }

    public void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] arr = {1, 2, 3, 4, 5, 6};
        int k = 2;
        sol.rotateArrayLeft(arr, k);
        for (int num : arr) {
            System.out.print(num + " ");
        }
        // Expected output: [3, 4, 5, 6, 1, 2]
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution:
    def rotate_left(self, arr: list[int], k: int) -> None:
        n = len(arr)
        k = k % n   # Ensure k is within bounds

        self.reverse(arr, 0, k - 1)    # Reverse the first part
        self.reverse(arr, k, n - 1)    # Reverse the second part
        self.reverse(arr, 0, n - 1)    # Reverse the whole array

    def reverse(self, arr: list[int], start: int, end: int) -> None:
        while start < end:
            self.swap(arr, start, end)
            start += 1
            end -= 1

    def swap(self, arr: list[int], i: int, j: int) -> None:
        arr[i], arr[j] = arr[j], arr[i]

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(1)