☕ DSA Java Articles

Topics › Arrays › Easy

Left Rotate Array by K Places

Easy TUF ID 39 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

You are given an array of integers nums and a non-negative integer k. Rotate the array left by k positions in place: the element at index i moves to index (i - k) mod n, so the first k elements wrap around to the end. k may be 0, equal to n, or much larger than n.

LeetCode’s “Rotate Array” rotates to the right by k; a right rotation by k is a left rotation by n - k, so every method below adapts with a one-line change.

Constraints: 0 ≤ n ≤ 10^5, 0 ≤ k ≤ 10^9, values fit in a 32-bit signed integer.

Example 1

nums = [1, 2, 3, 4, 5, 6, 7], k = 3
after  = [4, 5, 6, 7, 1, 2, 3]       // 1, 2, 3 leave the front and reappear at the back in the same order

Example 2

nums = [1, 2, 3, 4, 5, 6, 7], k = 10
after  = [4, 5, 6, 7, 1, 2, 3]       // rotating by 7 is the identity, so k = 10 behaves like k = 3

Example 3

nums = [1, 2, 3], k = 0
after  = [1, 2, 3]                   // no rotation

Every approach begins with k %= n. Rotating by exactly n positions puts every element back where it started, so only k mod n matters. This single line turns k = 10^9 from a time-limit problem into a trivial one, and it also prevents out-of-range indices in the approaches that index with k directly. The one thing to guard before it is n == 0, because k % 0 throws ArithmeticException.

Approach 1: Brute force, rotate by one k times

Intuition. We already know how to rotate left by one (Left Rotate Array by One): save the first element, shift everything left, put the saved element at the end. Rotating by k is doing that k times. Correct and obvious, but each single rotation touches the whole array, so the total work is k full passes.

Algorithm.

  1. If n == 0, return. Reduce k %= n.
  2. Repeat k times: first = nums[0]; shift nums[1..n-1] one slot left; nums[n - 1] = first.
static void bruteForce(int[] nums, int k) {
    int n = nums.length;
    if (n == 0) return;
    k %= n;                                      // rotating by n is the identity
    for (int t = 0; t < k; t++) {
        int first = nums[0];
        for (int i = 1; i < n; i++) nums[i - 1] = nums[i];
        nums[n - 1] = first;
    }
}

Complexity. Time O(n × k) after the reduction, which is O(n^2) in the worst case k ≈ n / 2. Space O(1).

For n = 10^5 and k = 5 × 10^4 that is 5 × 10^9 element moves; too slow. The waste is that each element is moved k times when it only needs to be moved once.

Approach 2: Better, stash the first k elements

Intuition. In the final arrangement, nums[k..n-1] simply slides left by k to occupy nums[0..n-k-1], and the original nums[0..k-1] lands in the last k slots in its original order. Those first k elements are the only ones that would be overwritten before they are read, so copy them to a temporary array, slide the rest, then append the copy. Every element now moves exactly once.

Algorithm.

  1. If n == 0, return. Reduce k %= n.
  2. Copy nums[0..k-1] into temp.
  3. For i from k to n - 1: nums[i - k] = nums[i] (left to right, so the destination has already been read).
  4. For i from 0 to k - 1: nums[n - k + i] = temp[i].
static void better(int[] nums, int k) {
    int n = nums.length;
    if (n == 0) return;
    k %= n;
    int[] temp = new int[k];
    for (int i = 0; i < k; i++) temp[i] = nums[i];
    for (int i = k; i < n; i++) nums[i - k] = nums[i];
    for (int i = 0; i < k; i++) nums[n - k + i] = temp[i];
}

Complexity. Time O(n): k + (n - k) + k = n + k ≤ 2n moves. Space O(k) for the stash, which is O(n) in the worst case.

This is the natural “one buffer” solution. The only remaining cost is the extra memory, and interviewers will ask for O(1).

Approach 3: Optimal, three reversals

Intuition. Write the array as two blocks, A = nums[0..k-1] and B = nums[k..n-1]. The target is B A. Reversal has a useful algebraic property: reversing a concatenation reverses the blocks and swaps their order, reverse(A B) = reverse(B) reverse(A). So if we first reverse each block individually, obtaining reverse(A) reverse(B), and then reverse the whole thing, we get reverse(reverse(B)) reverse(reverse(A)) = B A. Three in-place reversals, no extra memory.

Algorithm.

  1. If n == 0, return. Reduce k %= n.
  2. Reverse nums[0..k-1].
  3. Reverse nums[k..n-1].
  4. Reverse nums[0..n-1].
static void optimal(int[] nums, int k) {
    int n = nums.length;
    if (n == 0) return;
    k %= n;
    reverse(nums, 0, k - 1);
    reverse(nums, k, n - 1);
    reverse(nums, 0, n - 1);
}

with the standard two-pointer reversal:

static void reverse(int[] a, int lo, int hi) {
    while (lo < hi) {
        int t = a[lo];
        a[lo] = a[hi];
        a[hi] = t;
        lo++;
        hi--;
    }
}

Dry run on nums = [1, 2, 3, 4, 5, 6, 7], k = 3:

step range array
start   [1, 2, 3, 4, 5, 6, 7]
reverse A 0..2 [3, 2, 1, 4, 5, 6, 7]
reverse B 3..6 [3, 2, 1, 7, 6, 5, 4]
reverse all 0..6 [4, 5, 6, 7, 1, 2, 3]

Complexity. Time O(n): each element is swapped at most twice (once inside its block, once in the full reversal), so about n swaps total. Space O(1).

For a right rotation by k, swap the roles: reverse nums[0..n-k-1], reverse nums[n-k..n-1], then reverse everything; or, equivalently, call the left rotation with n - k.

Edge cases and pitfalls