Left Rotate Array by K Places

61.6k
0

Given an integer array nums and an integer k, rotate the array by k positions to the left.

Example 1

Input: nums = [1, 2, 3, 4, 5], k = 2

Output: [3, 4, 5, 1, 2]

Explanation: After rotating left by 2 places, 1 and 2 move to the end, and the remaining elements shift left.

Example 2

Input: nums = [10, 20, 30, 40, 50, 60], k = 3

Output: [40, 50, 60, 10, 20, 30]

Explanation: After rotating left by 3 places, 10, 20, and 30 move to the end.

Brute Force Approach

A left rotation by k positions can be performed as k consecutive one-place rotations.

During each rotation, preserve the first element, shift the remaining elements one position to the left, and place the preserved element at the end.

Since rotating an array of size N exactly N times restores its original arrangement, only k % N rotations are required.

Algorithm

  • If the array contains at most one element, return immediately because any rotation leaves its arrangement unchanged.

  • Normalize k using k % N, since every N left rotations bring the array back to its original arrangement.

  • Perform the one-position left rotation k times so that the array is shifted by the required number of positions.

  • During each rotation, store nums[0] before shifting because its value would otherwise be overwritten.

  • Shift every element from index 1 through N - 1 one position to the left, moving nums[index] to nums[index - 1].

  • Place the stored first element at index N - 1 to complete the current one-position rotation.Dry Run

Left Rotate Array by K Places Brute Force Dry Run.png

Left Rotate Array by K Places Brute Force Dry Run.png

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
void leftRotate(vector<int>& nums, int k) {
// Rotation does not change an array with at most one element.
if (nums.size() <= 1) {
return;
}
int n = nums.size();
// Remove complete rotation cycles.
k = k % n;
for (int rotation = 0; rotation < k; rotation++) {
// Preserve the first value before shifting overwrites it.
int first = nums[0];
for (int index = 1; index < n; index++) {
nums[index - 1] = nums[index];
}
nums[n - 1] = first;
}
}
};
int main() {
vector<int> nums = {1, 2, 3, 4, 5};
int k = 2;
Solution solution;
solution.leftRotate(nums, k);
cout << "Rotated array: ";
for (int value : nums) {
cout << value << " ";
}
return 0;
}

Complexity Analysis

Time Complexity: O(N × K), where N represents the array size and K represents the normalized rotation count. Each one-place rotation shifts N - 1 elements, and this process is repeated K times.

Space Complexity: O(1), because only one temporary variable is used during each rotation.

Better Approach

The first k elements must eventually appear at the end of the array.

Store these elements temporarily before shifting the remaining values toward the beginning. The stored block can then be copied into the vacant positions at the end.

This avoids repeatedly shifting the same elements.

Algorithm

  • If the array contains at most one element, return immediately because rotating it does not change the arrangement.

  • Normalize k using k % N to remove complete rotation cycles. If the normalized value is 0, no further changes are required.

  • Store the first k elements in an auxiliary array temp, since these values will be overwritten while the remaining elements are shifted left.

  • Traverse from index k through N - 1 and move nums[index] to nums[index - k], shifting the remaining block k positions toward the beginning.

  • Copy the elements stored in temp into the final k positions, placing the original first block at the end and completing the rotation.

Dry Run

Left Rotate Array by K Places Better Appraoch Dry Run .png

Left Rotate Array by K Places Better Appraoch Dry Run .png

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
void leftRotate(vector<int>& nums, int k) {
// Rotation does not change an array with at most one element.
if (nums.size() <= 1) {
return;
}
int n = nums.size();
// Remove complete rotation cycles.
k = k % n;
if (k == 0) {
return;
}
// Protect the first k elements before they are overwritten.
vector<int> temp(k);
for (int index = 0; index < k; index++) {
temp[index] = nums[index];
}
// Move the remaining block k positions to the left.
for (int index = k; index < n; index++) {
nums[index - k] = nums[index];
}
// Place the protected block in the final k positions.
for (int index = 0; index < k; index++) {
nums[n - k + index] = temp[index];
}
}
};
int main() {
vector<int> nums = {1, 2, 3, 4, 5};
int k = 2;
Solution solution;
solution.leftRotate(nums, k);
cout << "Rotated array: ";
for (int value : nums) {
cout << value << " ";
}
return 0;
}

Complexity Analysis

Time Complexity: O(N + K), which simplifies to O(N) because normalized K is smaller than N.

The operations require:

  • O(K) time to copy the first K elements into temp.

  • O(N - K) time to shift the remaining elements left.

  • O(K) time to copy the stored elements back.

Therefore:

O(K) + O(N - K) + O(K)
= O(N + K)
= O(N)

Space Complexity: O(K), because the auxiliary array stores the first K elements.

Optimal Approach

After a left rotation, the array contains the same elements, but two continuous parts exchange their positions.

For example:

[1, 2 | 3, 4, 5]

After rotating by 2 positions, the required arrangement is:

[3, 4, 5 | 1, 2]

The challenge is to exchange these two parts without storing either of them in another array. Reversing selected portions allows the two blocks to change positions while their original internal order is recovered at the end.

Algorithm

  • If the array contains at most one element, return immediately because its arrangement remains unchanged after rotation.

  • Normalize k using k % N to remove complete rotation cycles. If the normalized value is 0, the array is already in the required arrangement.

  • Reverse the first k elements so that the block that must eventually move to the end is reversed internally.

  • Reverse the remaining N - k elements, preparing the second block in the same way before the complete array is reversed.

  • Reverse the entire array. This exchanges the positions of the two blocks while restoring the original order within each block, producing the required left rotation.

Dry Run

Left Rotate Array by K Places optimal Dry Run .png

Left Rotate Array by K Places optimal Dry Run .png

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
// Reverses the elements inside the inclusive index range.
void reverseRange(vector<int>& nums, int left, int right) {
while (left < right) {
swap(nums[left], nums[right]);
left++;
right--;
}
}
public:
void leftRotate(vector<int>& nums, int k) {
// Rotation does not change an array with at most one element.
if (nums.size() <= 1) {
return;
}
int n = nums.size();
// Remove complete rotation cycles.
k = k % n;
if (k == 0) {
return;
}
// Prepare both blocks before exchanging their positions.
reverseRange(nums, 0, k - 1);
reverseRange(nums, k, n - 1);
// Restore internal order after the block positions are exchanged.
reverseRange(nums, 0, n - 1);
}
};
int main() {
vector<int> nums = {1, 2, 3, 4, 5};
int k = 2;
Solution solution;
solution.leftRotate(nums, k);
cout << "Rotated array: ";
for (int value : nums) {
cout << value << " ";
}
return 0;
}

Complexity Analysis

Time Complexity: O(N), where N represents the number of elements.

The first two reversals process K and N - K elements, while the final reversal processes N elements:

O(K) + O(N - K) + O(N)
= O(2N)
= O(N)

Space Complexity: O(1), because all swaps are performed directly inside the input array.

Interview follow-up Questions

Every N left rotations restore the original arrangement. Normalizing k removes these complete cycles. For example, rotating an array of size 5 by 7 positions produces the same result as rotating it by:

ArraysIntroduction to DSAData StructuresTwo Pointer

Read Similar Blogs

HashingData Structures

Count Distinct Elements

Given an integer array arr[] , return the count of all distinct elements in the array. Input: arr = [10, 20, 20, 10, 30, 10] Output: 3 Explanation: The different values are 10 , 20 , and 30 . 10 an...

76.5k
Arrays

Row wise traversal

Given a matrix with N rows and M columns, print all elements row by row from left to right. Input: mat = [[1, 2, 3], [4, 5, 6]] Output: 1 2 3 4 5 6 Explanation: First row prints as 1...

61.7k
Arrays

Main Diagonal Print

Given a matrix with N rows and M columns, print all elements present on the main diagonal. Input: mat = [[1, 2, 3], [4, 5, 6], [7, 8, 9]] Output: 1 5 9 Explanation: Main diagonal cell...

67.1k
Comments0