Left Rotate Array by K Places

Given an integer array nums and a non-negative integer k, rotate the array to the left by k steps.

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

Output: nums = [3, 4, 5, 6, 1, 2]

Brute Force#

Repeatedly apply a single left rotation k times. Each rotation shifts every element one position to the left and wraps the first element to the end, which takes O(n) work. Doing this k times gives O(k*n) overall time. For large k, this is extremely slow; modular arithmetic and the reversal trick below eliminate the issue.

• K times rotate by One

class Solution {
public:
    void rotateArrayByOne(vector<int>& nums) {
        int n = nums.size();
        int firstEle = nums[0];

        for(int i=1;i<n;i++){
            nums[i-1] = nums[i];
        }
        nums[n-1] = firstEle;
    }
    void rotateArray(vector<int>& nums, int k) {
        for(int i=0;i<k;i++){
            rotateArrayByOne(nums);
        }
    }
};

Time Complexity: O(k*n)

Space Complexity: O(1)

Optimal Approach: Segment Reversal#

The trick is to observe that a left rotation by k places puts elements [0..k-1] at the end and [k..n-1] at the front. We achieve this with three in-place reversals: reverse the first k elements, reverse the remaining n-k elements, then reverse the whole array. Each reversal undoes the unwanted flip introduced by the previous one, leaving exactly the rotated order. We also reduce k modulo n first to handle cases where k <= n. This runs in O(n) time with O(1) extra space, a major improvement over the brute-force O(k*n).

• Reversal Property: Reversing a segment of the array changes the order but keeps the elements intact. By reversing the segments first and then the entire array, you rearrange the elements correctly without needing extra space.

class Solution {
public:

    void rotateArray(vector<int>& nums, int k) {
        int n = nums.size();
        k = k%n;
        reverse(nums.begin(), nums.begin() + k);
        reverse(nums.begin() + k, nums.end());
        reverse(nums.begin(), nums.end());
    }
};

Time Complexity: O(n)

Space Complexity: O(1)