Array rotation

You are in a Microsoft phone screen and the interviewer asks you to rotate an array to the left by k positions, but with a twist: do it in constant space. This problem, also known as Rotate Array on other platforms, is a favorite because the brute-force solution is straightforward but the optimal in-place approach requires a clever trick that separates strong candidates from average ones.

TL;DR

Use the three-reversal technique: reverse the entire array, then reverse the left segment (indices 0 to n-1-k), then reverse the right segment (indices n-k to n-1). This rotates the array left by k positions in O(n) time and O(1) space. Handle k larger than the array length with modulo.

Why This Problem Matters

Array rotation appears in real systems more often than you might expect. Circular buffers, ring queues, and log rotation all rely on the same concept. The three-reversal trick is also a building block for other interview problems like rotating a string or rearranging elements around a pivot. Understanding how to manipulate arrays in place without allocating extra memory is a skill interviewers value highly.

Understanding the Problem

Given an array and a non-negative integer k, rotate the array to the left by k positions. Left rotation means each element shifts k positions toward the start, and elements that fall off the left end wrap around to the right end.

rotateLeft([1,2,3,4], 1) -> [2,3,4,1]
rotateLeft([1,2,3,4], 2) -> [3,4,1,2]
rotateLeft([1,2,3,4], 3) -> [4,1,2,3]
rotateLeft([1,2,3,4], 4) -> [1,2,3,4]
rotateLeft([1,2,3,4], 5) -> [2,3,4,1]

Edge Cases

1. Empty or single-element array: Already rotated, return as-is
2. k equals array length: Full rotation returns the original array
3. k larger than array length: Equivalent to k % n rotations, since every n rotations is a full cycle
4. k equals zero: No rotation needed

Solution Approach

The naive approach creates a new array and copies elements to their rotated positions. That works but uses O(n) extra space, violating the constant-space constraint.

The optimal approach uses three in-place reversals. Here is how it works for rotateLeft([1,2,3,4,5,6,7], 2):

Step 1 reverses the entire array. Step 2 reverses the left segment (indices 0 through n-1-k, which is 0 through 4). Step 3 reverses the right segment (indices n-k through n-1, which is 5 through 6). The result is the array rotated left by 2.

Why Three Reversals Work

Think of the array as two blocks: the first k elements [1,2] and the remaining elements [3,4,5,6,7]. After rotation, we want [3,4,5,6,7,1,2]. Reversing the entire array puts both blocks in reversed order at swapped positions. The second and third reversals then fix each block's internal ordering.

Handling Large k Values

When k exceeds the array length, the modulo operator finds the effective rotation count:

Rotating [1,2,3,4] by 5 positions is the same as rotating by 1, because 5 % 4 = 1. The modulo step also handles the case where k equals the array length: k % n = 0, so no rotation occurs.

Implementation

Prefer a different language? Jump to solutions in other languages.

public class Solution {
  public int[] rotateLeft(int[] arr, int k) {
    if (arr.length <= 1) return arr;

    int rotations = k % arr.length;

    reverse(arr, 0, arr.length - 1);
    reverse(arr, 0, arr.length - 1 - rotations);
    reverse(arr, arr.length - rotations, arr.length - 1);

    return arr;
  }

  private void reverse(int[] arr, int leftIndex, int rightIndex) {
    while (leftIndex < rightIndex) {
      int temp = arr[leftIndex];
      arr[leftIndex++] = arr[rightIndex];
      arr[rightIndex--] = temp;
    }
  }
}

Let's walk through the code:

1. Base case: If the array has 0 or 1 elements, no rotation is possible, so return immediately
2. Modulo: k % arr.length reduces k to an effective rotation count within the array bounds
3. Three reversals: Each reverse call swaps elements between two indices, walking inward until the pointers meet
4. Return: The array is modified in place and returned

The reverse helper uses a two-pointer swap. Here is how it processes a segment:

Left and right pointers start at the segment boundaries. At each step, the elements at those positions are swapped using a temp variable, and both pointers move inward. When they meet or cross, the segment is fully reversed.

Complexity Analysis

Time: O(n) where n is the array length. Each reversal visits at most n elements, and we perform exactly three reversals. The total number of swaps is at most 3n/2, but in Big-O terms this simplifies to O(n).

Space: O(1). The only extra storage is the rotations variable and the temp variable inside the reverse helper. No additional arrays or data structures are created.

Why Not Use a Temporary Array?

The temporary array approach looks like this:

// Works, but uses O(n) space
int[] result = new int[arr.length];
for (int i = 0; i < arr.length; i++) {
    result[(i - k + arr.length) % arr.length] = arr[i];
}
return result;

This copies each element to its new position in a fresh array. It is correct and runs in O(n) time, but the O(n) space makes it a weaker answer when the interviewer asks for constant space.

Common Pitfalls

1. Forgetting the modulo: Without k % arr.length, values of k larger than the array length cause index-out-of-bounds errors or incorrect results.

2. Wrong reversal boundaries: The left segment runs from 0 to arr.length - 1 - rotations, not arr.length - rotations. An off-by-one here produces a wrong answer.

3. Confusing left and right rotation: Left rotation by k moves the first k elements to the end. Right rotation by k moves the last k elements to the front. Make sure you know which direction the problem asks for.

4. Not handling empty arrays: An empty array passed to the modulo operation causes a division-by-zero error. The base case check prevents this.

Interview Tips

When presenting this solution:

• Start by confirming whether the rotation is left or right, and whether you may modify the input array
• Mention the naive O(n) space approach first, then explain the O(1) optimization
• Draw the three reversal steps on the whiteboard. Interviewers find visual demonstrations convincing.
• Explain why k % n is necessary before the interviewer has to ask about large k values
• If asked about right rotation, note that a right rotation by k is a left rotation by n-k

Key Takeaways

• The three-reversal technique rotates an array in-place with O(n) time and O(1) space. Reverse the whole array, then reverse each of the two resulting segments.
• Always apply k % arr.length before rotating. This handles k values larger than the array length and the case where k equals the array length.
• The reverse helper is a simple two-pointer swap that walks inward from both ends of a segment. It is reusable across many in-place array manipulation problems.
• This technique generalizes beyond rotation. It applies to any problem that requires rearranging contiguous blocks within an array without extra memory.
• Edge cases (empty array, single element, k = 0) should be handled before any computation to avoid division by zero and unnecessary work.

Practice and Related Problems

Once you are comfortable with array rotation, try these progressions:

• Rotate a string by k characters (same technique, different data type)
• Reverse words in a string (reverse all, then reverse each word)
• Circular array problems (ring buffers, Josephus problem)

This problem and hundreds of others are available on Firecode, where consistent daily practice helps you build the pattern recognition that top tech companies look for. Whether you are warming up for phone screens or preparing for on-site interviews, starting with fundamentals like this sets you up well.

Solutions in Other Languages

Python

from typing import List


class Solution:
    def rotate_left(self, arr: List[int], k: int) -> List[int]:
        size = len(arr)

        if size <= 1:
            return arr

        rotations = k % size

        self.reverse(arr, 0, size - 1)
        self.reverse(arr, 0, size - 1 - rotations)
        self.reverse(arr, size - rotations, size - 1)

        return arr

    def reverse(self, arr: List[int], left_index: int, right_index: int):
        while left_index < right_index:
            temp = arr[left_index]
            arr[left_index] = arr[right_index]
            arr[right_index] = temp
            left_index += 1
            right_index -= 1

JavaScript

class Solution {
  rotateLeft(arr, k) {
    if (arr.length <= 1) return arr;

    const rotations = k % arr.length;

    this.reverse(arr, 0, arr.length - 1);
    this.reverse(arr, 0, arr.length - 1 - rotations);
    this.reverse(arr, arr.length - rotations, arr.length - 1);

    return arr;
  }

  reverse(arr, leftIndex, rightIndex) {
    while (leftIndex < rightIndex) {
      const temp = arr[leftIndex];
      arr[leftIndex++] = arr[rightIndex];
      arr[rightIndex--] = temp;
    }
  }
}

module.exports = Solution;

TypeScript

class Solution {
  rotateLeft(arr: number[], k: number): number[] {
    if (arr.length <= 1) return arr;

    const rotations = k % arr.length;

    this.reverse(arr, 0, arr.length - 1);
    this.reverse(arr, 0, arr.length - 1 - rotations);
    this.reverse(arr, arr.length - rotations, arr.length - 1);

    return arr;
  }

  private reverse(arr: number[], leftIndex: number, rightIndex: number): void {
    while (leftIndex < rightIndex) {
      const temp = arr[leftIndex];
      arr[leftIndex++] = arr[rightIndex];
      arr[rightIndex--] = temp;
    }
  }
}

export { Solution };

C++

#include <vector>
#include <iostream>

class Solution {
public:
  std::vector<int> rotateLeft(std::vector<int> &arr, int k) {
    if (arr.size() <= 1) return arr;

    int rotations = k % arr.size();

    reverse(arr, 0, arr.size() - 1);
    reverse(arr, 0, arr.size() - 1 - rotations);
    reverse(arr, arr.size() - rotations, arr.size() - 1);

    return arr;
  }

private:
  void reverse(std::vector<int> &arr, int leftIndex, int rightIndex) {
    while (leftIndex < rightIndex) {
      std::swap(arr[leftIndex++], arr[rightIndex--]);
    }
  }
};

Go

package solution

func (s *Solution) RotateLeft(arr []int, k int) []int {
	if len(arr) <= 1 {
		return arr
	}

	rotations := k % len(arr)

	reverse(arr, 0, len(arr)-1)
	reverse(arr, 0, len(arr)-1-rotations)
	reverse(arr, len(arr)-rotations, len(arr)-1)

	return arr
}

func reverse(arr []int, leftIndex int, rightIndex int) {
	for leftIndex < rightIndex {
		arr[leftIndex], arr[rightIndex] = arr[rightIndex], arr[leftIndex]
		leftIndex++
		rightIndex--
	}
}

type Solution struct {
}

Scala

class Solution {
  def rotateLeft(arr: Array[Int], k: Int): Array[Int] = {
    if (arr.length <= 1) return arr

    val rotations = k % arr.length

    reverse(arr, 0, arr.length - 1)
    reverse(arr, 0, arr.length - 1 - rotations)
    reverse(arr, arr.length - rotations, arr.length - 1)

    arr
  }

  private def reverse(
    arr: Array[Int],
    leftIndex: Int,
    rightIndex: Int
  ): Unit = {
    var left = leftIndex
    var right = rightIndex
    while (left < right) {
      val temp = arr(left)
      arr(left) = arr(right)
      arr(right) = temp
      left += 1
      right -= 1
    }
  }
}

Kotlin

class Solution {
    fun rotateLeft(arr: IntArray, k: Int): IntArray {
        if (arr.size <= 1) return arr

        val rotations = k % arr.size

        reverse(arr, 0, arr.size - 1)
        reverse(arr, 0, arr.size - 1 - rotations)
        reverse(arr, arr.size - rotations, arr.size - 1)

        return arr
    }

    private fun reverse(arr: IntArray, leftIndex: Int, rightIndex: Int) {
        var left = leftIndex
        var right = rightIndex
        while (left < right) {
            val temp = arr[left]
            arr[left++] = arr[right]
            arr[right--] = temp
        }
    }
}

Swift

import Foundation

class Solution {
    func rotateLeft(_ arr: [Int], _ k: Int) -> [Int] {
        if arr.count <= 1 { return arr }

        var result = arr
        let rotations = k % result.count

        reverse(&result, 0, result.count - 1)
        reverse(&result, 0, result.count - 1 - rotations)
        reverse(&result, result.count - rotations, result.count - 1)

        return result
    }

    private func reverse(_ arr: inout [Int], _ leftIndex: Int, _ rightIndex: Int) {
        var left = leftIndex
        var right = rightIndex
        while left < right {
            arr.swapAt(left, right)
            left += 1
            right -= 1
        }
    }
}

Rust

pub struct Solution;

impl Solution {
    pub fn rotate_left(&self, mut arr: Vec<i32>, k: i32) -> Vec<i32> {
        if arr.len() <= 1 {
            return arr;
        }

        let len = arr.len();
        let rotations = k as usize % len;

        Self::reverse(&mut arr, 0, len - 1);
        Self::reverse(&mut arr, 0, len - 1 - rotations);
        Self::reverse(&mut arr, len - rotations, len - 1);

        arr
    }

    fn reverse(arr: &mut Vec<i32>, mut left_index: usize, mut right_index: usize) {
        while left_index < right_index {
            arr.swap(left_index, right_index);
            left_index += 1;
            right_index -= 1;
        }
    }
}

C#

public class Solution {
    public int[] rotateLeft(int[] arr, int k) {
        if (arr.Length <= 1) return arr;

        int rotations = k % arr.Length;

        Reverse(arr, 0, arr.Length - 1);
        Reverse(arr, 0, arr.Length - 1 - rotations);
        Reverse(arr, arr.Length - rotations, arr.Length - 1);

        return arr;
    }

    private void Reverse(int[] arr, int leftIndex, int rightIndex) {
        while (leftIndex < rightIndex) {
            int temp = arr[leftIndex];
            arr[leftIndex++] = arr[rightIndex];
            arr[rightIndex--] = temp;
        }
    }
}

Dart

class Solution {
  List<int> rotateLeft(List<int> arr, int k) {
    if (arr.length <= 1) return arr;

    int rotations = k % arr.length;

    _reverse(arr, 0, arr.length - 1);
    _reverse(arr, 0, arr.length - 1 - rotations);
    _reverse(arr, arr.length - rotations, arr.length - 1);

    return arr;
  }

  void _reverse(List<int> arr, int left, int right) {
    while (left < right) {
      int temp = arr[left];
      arr[left++] = arr[right];
      arr[right--] = temp;
    }
  }
}

PHP

<?php

class Solution {
    public function rotateLeft(array $arr, int $k): array {
        if (count($arr) <= 1) return $arr;

        $rotations = $k % count($arr);

        $this->reverse($arr, 0, count($arr) - 1);
        $this->reverse($arr, 0, count($arr) - 1 - $rotations);
        $this->reverse($arr, count($arr) - $rotations, count($arr) - 1);

        return $arr;
    }

    private function reverse(array &$arr, int $leftIndex, int $rightIndex): void {
        while ($leftIndex < $rightIndex) {
            $temp = $arr[$leftIndex];
            $arr[$leftIndex++] = $arr[$rightIndex];
            $arr[$rightIndex--] = $temp;
        }
    }
}

Ruby

class Solution
  def rotate_left(arr, k)
    return arr if arr.length <= 1

    rotations = k % arr.length

    reverse(arr, 0, arr.length - 1)
    reverse(arr, 0, arr.length - 1 - rotations)
    reverse(arr, arr.length - rotations, arr.length - 1)

    arr
  end

  private

  def reverse(arr, left_index, right_index)
    while left_index < right_index
      arr[left_index], arr[right_index] = arr[right_index], arr[left_index]
      left_index += 1
      right_index -= 1
    end
  end
end