☕ DSA Java Articles

Topics › Arrays › Easy

Left Rotate Array by One

Easy TUF ID 40 A2Z

Java source ↗ Edit this article ↗

Problem

You are given an array of integers nums. Rotate it left by one position: every element moves one index towards the front, and the element that was at index 0 wraps around to the last index. Do it in place.

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

Example 1

nums = [1, 2, 3, 4, 5]
after  = [2, 3, 4, 5, 1]        // 1 leaves the front and reappears at the back

Example 2

nums = [1, 2]
after  = [2, 1]                 // with two elements a rotation is just a swap

Example 3

nums = [7]
after  = [7]                    // a single element rotates onto itself

The problem is tiny, but it introduces the idea that defines in-place array manipulation: when you move elements around inside one buffer, the order of the moves decides whether you overwrite something before you have read it. Getting this right here is the foundation for rotating by k, for deleting from an array, and for every two-pointer compaction later on.

Approach 1: Brute force, build the answer in a second array

Intuition. If overwriting is the danger, avoid it entirely: write the rotated arrangement into a fresh array, where no slot is ever read after being written, then copy that array back over the original. The index mapping is rotated[i - 1] = nums[i] for i ≥ 1, and rotated[n - 1] = nums[0].

Algorithm.

  1. If n == 0, there is nothing to do.
  2. Allocate rotated of size n.
  3. For i from 1 to n - 1, set rotated[i - 1] = nums[i].
  4. Set rotated[n - 1] = nums[0].
  5. Copy rotated back into nums.
static void bruteForce(int[] nums) {
    int n = nums.length;
    if (n == 0) return;
    int[] rotated = new int[n];
    for (int i = 1; i < n; i++) rotated[i - 1] = nums[i];
    rotated[n - 1] = nums[0];
    for (int i = 0; i < n; i++) nums[i] = rotated[i];
}

Complexity. Time O(n): two linear passes. Space O(n) for the temporary array, which is the part worth eliminating. Rotating a 100 MB array should not need another 100 MB.

Approach 2: Optimal, save the first element and shift

Intuition. Only one element, nums[0], is going to be overwritten before it reaches its destination. Save it in a variable. Then shift the remaining elements left one at a time, going from left to right: when we write nums[i - 1] = nums[i], the slot nums[i - 1] has already been read (it was moved one step earlier), so nothing is lost. Finally place the saved value at the end.

Had we shifted from right to left, nums[n - 2] = nums[n - 1] would destroy the old nums[n - 2] before it was moved, and the array would fill up with copies of the last element. Direction is the entire algorithm.

Algorithm.

  1. If n == 0, return.
  2. first = nums[0].
  3. For i from 1 to n - 1: nums[i - 1] = nums[i].
  4. nums[n - 1] = first.
static void optimal(int[] nums) {
    int n = nums.length;
    if (n == 0) return;
    int first = nums[0];
    for (int i = 1; i < n; i++) nums[i - 1] = nums[i];   // left to right, so nothing is overwritten before it is read
    nums[n - 1] = first;
}

Dry run on nums = [1, 2, 3, 4, 5], with first = 1:

i write array
1 nums[0] = nums[1] [2, 2, 3, 4, 5]
2 nums[1] = nums[2] [2, 3, 3, 4, 5]
3 nums[2] = nums[3] [2, 3, 4, 4, 5]
4 nums[3] = nums[4] [2, 3, 4, 5, 5]
end nums[4] = first [2, 3, 4, 5, 1]

Notice that after each step the array temporarily holds a duplicate; that is normal, it is the slot about to be overwritten next.

Complexity. Time O(n): n - 1 moves plus one write. Space O(1): one saved value.

Approach 3: The same shift with System.arraycopy

Intuition. Shifting a contiguous block is so common that the JDK provides a native routine for it. System.arraycopy(src, srcPos, dest, destPos, length) copies length elements, and the specification guarantees correct behaviour even when src and dest are the same array and the ranges overlap: it behaves as if the source range were first copied to a temporary buffer. So the whole shift collapses to one call, and we keep only the wrap-around step by hand.

Algorithm.

  1. If n == 0, return.
  2. first = nums[0].
  3. System.arraycopy(nums, 1, nums, 0, n - 1).
  4. nums[n - 1] = first.
static void optimalArraycopy(int[] nums) {
    int n = nums.length;
    if (n == 0) return;
    int first = nums[0];
    System.arraycopy(nums, 1, nums, 0, n - 1);
    nums[n - 1] = first;
}

Complexity. Time O(n), space O(1); the call is a tight native memory move and is noticeably faster than the hand-written loop on large arrays.

The explicit loop in Approach 2 is what you should be able to write on a whiteboard; arraycopy is what you should write in production. Knowing that the overlapping case is safe is the useful fact here, because ArrayList.remove(0) and many ring-buffer implementations rely on exactly that.

Edge cases and pitfalls