[AlgoMastery]
Topics›Array›Array Rotation
📖

Array Rotation

Array
~20 min read
5 practice problems

Overview

Array Rotation involves shifting elements of an array by a certain number of positions. Elements that fall off one end wrap around to the other end, creating a circular shift effect. This is a fundamental operation in many algorithms and data structures.

Rotation can be done left (elements move left, wrap to right) or right (elements move right, wrap to left). The challenge is to perform rotation efficiently, often in-place with O(1) space.

Array rotation is particularly useful for:

  • Rotating arrays by K positions
  • Finding minimum in rotated sorted array
  • Searching in rotated sorted array
  • Reversing array segments
  • Cyclic permutations

Pattern 1: Rotate Array Right by K Positions

Rotate array to the right by K positions.

Method 1: Using Extra Array

function rotateRight(nums: number[], k: number): void {
  const n = nums.length;
  k = k % n; // Handle k > n
  
  const rotated = new Array(n);
  
  for (let i = 0; i < n; i++) {
    rotated[(i + k) % n] = nums[i];
  }
  
  for (let i = 0; i < n; i++) {
    nums[i] = rotated[i];
  }
}

Time: O(n), Space: O(n)

Method 2: Reverse Approach (In-Place)

function rotateRightInPlace(nums: number[], k: number): void {
  const n = nums.length;
  k = k % n;
  
  // Reverse entire array
  reverse(nums, 0, n - 1);
  // Reverse first k elements
  reverse(nums, 0, k - 1);
  // Reverse remaining elements
  reverse(nums, k, n - 1);
}

function reverse(nums: number[], start: number, end: number): void {
  while (start < end) {
    [nums[start], nums[end]] = [nums[end], nums[start]];
    start++;
    end--;
  }
}

Time: O(n), Space: O(1)

Example: [1,2,3,4,5] rotate right by 2:

  1. Reverse all: [5,4,3,2,1]
  2. Reverse first 2: [4,5,3,2,1]
  3. Reverse last 3: [4,5,1,2,3] ✓

Pattern 2: Rotate Array Left by K Positions

Rotate array to the left by K positions.

function rotateLeft(nums: number[], k: number): void {
  const n = nums.length;
  k = k % n;
  
  // Reverse entire array
  reverse(nums, 0, n - 1);
  // Reverse last k elements
  reverse(nums, n - k, n - 1);
  // Reverse first (n-k) elements
  reverse(nums, 0, n - k - 1);
}

Time: O(n), Space: O(1)

Example: [1,2,3,4,5] rotate left by 2:

  1. Reverse all: [5,4,3,2,1]
  2. Reverse last 2: [5,4,3,1,2]
  3. Reverse first 3: [3,4,5,1,2] ✓

Pattern 3: Find Minimum in Rotated Sorted Array

Find minimum element in rotated sorted array (no duplicates).

function findMin(nums: number[]): number {
  let left = 0;
  let right = nums.length - 1;
  
  while (left < right) {
    const mid = Math.floor((left + right) / 2);
    
    // Right half is sorted, minimum is in left half
    if (nums[mid] < nums[right]) {
      right = mid;
    } else {
      // Left half is sorted, minimum is in right half
      left = mid + 1;
    }
  }
  
  return nums[left];
}

Time: O(log n), Space: O(1)

With duplicates:

function findMinWithDuplicates(nums: number[]): number {
  let left = 0;
  let right = nums.length - 1;
  
  while (left < right) {
    const mid = Math.floor((left + right) / 2);
    
    if (nums[mid] < nums[right]) {
      right = mid;
    } else if (nums[mid] > nums[right]) {
      left = mid + 1;
    } else {
      // nums[mid] === nums[right], can't decide, shrink right
      right--;
    }
  }
  
  return nums[left];
}

Time: O(n) worst case, O(log n) average, Space: O(1)

Pattern 4: Search in Rotated Sorted Array

Search target in rotated sorted array (no duplicates).

function search(nums: number[], target: number): number {
  let left = 0;
  let right = nums.length - 1;
  
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    
    if (nums[mid] === target) return mid;
    
    // Left half is sorted
    if (nums[left] <= nums[mid]) {
      if (target >= nums[left] && target < nums[mid]) {
        right = mid - 1;
      } else {
        left = mid + 1;
      }
    } else {
      // Right half is sorted
      if (target > nums[mid] && target <= nums[right]) {
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }
  }
  
  return -1;
}

Time: O(log n), Space: O(1)

With duplicates:

function searchWithDuplicates(nums: number[], target: number): boolean {
  let left = 0;
  let right = nums.length - 1;
  
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    
    if (nums[mid] === target) return true;
    
    // Handle duplicates
    if (nums[left] === nums[mid] && nums[mid] === nums[right]) {
      left++;
      right--;
      continue;
    }
    
    if (nums[left] <= nums[mid]) {
      if (target >= nums[left] && target < nums[mid]) {
        right = mid - 1;
      } else {
        left = mid + 1;
      }
    } else {
      if (target > nums[mid] && target <= nums[right]) {
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }
  }
  
  return false;
}

Time: O(n) worst case, O(log n) average, Space: O(1)

Pattern 5: Rotate Array Using Cyclic Replacements

Rotate array using cyclic replacement (in-place).

function rotateCyclic(nums: number[], k: number): void {
  const n = nums.length;
  k = k % n;
  
  let count = 0;
  
  for (let start = 0; count < n; start++) {
    let current = start;
    let prev = nums[start];
    
    do {
      const next = (current + k) % n;
      const temp = nums[next];
      nums[next] = prev;
      prev = temp;
      current = next;
      count++;
    } while (start !== current);
  }
}

Time: O(n), Space: O(1)

Explanation: Move elements in cycles. Each cycle moves elements by k positions until we return to start.

Pattern 6: Rotate Matrix 90 Degrees Clockwise

Rotate 2D matrix 90 degrees clockwise in-place.

function rotateMatrix(matrix: number[][]): void {
  const n = matrix.length;
  
  // Transpose matrix
  for (let i = 0; i < n; i++) {
    for (let j = i; j < n; j++) {
      [matrix[i][j], matrix[j][i]] = [matrix[j][i], matrix[i][j]];
    }
  }
  
  // Reverse each row
  for (let i = 0; i < n; i++) {
    matrix[i].reverse();
  }
}

Time: O(n²), Space: O(1)

Counter-clockwise:

function rotateMatrixCounterClockwise(matrix: number[][]): void {
  const n = matrix.length;
  
  // Transpose
  for (let i = 0; i < n; i++) {
    for (let j = i; j < n; j++) {
      [matrix[i][j], matrix[j][i]] = [matrix[j][i], matrix[i][j]];
    }
  }
  
  // Reverse each column (or reverse rows then transpose)
  for (let i = 0; i < Math.floor(n / 2); i++) {
    for (let j = 0; j < n; j++) {
      [matrix[i][j], matrix[n - 1 - i][j]] = [matrix[n - 1 - i][j], matrix[i][j]];
    }
  }
}

Pattern 7: Rotate List (Linked List)

Rotate linked list to the right by K places.

class ListNode {
  val: number;
  next: ListNode | null;
  constructor(val: number) {
    this.val = val;
    this.next = null;
  }
}

function rotateRight(head: ListNode | null, k: number): ListNode | null {
  if (!head || !head.next) return head;
  
  // Calculate length
  let length = 1;
  let tail = head;
  while (tail.next) {
    tail = tail.next;
    length++;
  }
  
  k = k % length;
  if (k === 0) return head;
  
  // Find new tail (length - k - 1 from start)
  let newTail = head;
  for (let i = 0; i < length - k - 1; i++) {
    newTail = newTail.next!;
  }
  
  // Rotate
  const newHead = newTail.next!;
  newTail.next = null;
  tail.next = head;
  
  return newHead;
}

Time: O(n), Space: O(1)

Pattern 8: Rotate String

Check if one string is rotation of another.

function isRotation(s1: string, s2: string): boolean {
  if (s1.length !== s2.length) return false;
  
  // Concatenate s1 with itself, check if s2 is substring
  const doubled = s1 + s1;
  return doubled.includes(s2);
}

Time: O(n), Space: O(n)

Using KMP for O(n) time:

function isRotationKMP(s1: string, s2: string): boolean {
  if (s1.length !== s2.length) return false;
  const doubled = s1 + s1;
  return kmpSearch(doubled, s2) !== -1;
}

function kmpSearch(text: string, pattern: string): number {
  const lps = buildLPS(pattern);
  let i = 0, j = 0;
  
  while (i < text.length) {
    if (text[i] === pattern[j]) {
      i++;
      j++;
      if (j === pattern.length) return i - j;
    } else if (j > 0) {
      j = lps[j - 1];
    } else {
      i++;
    }
  }
  
  return -1;
}

function buildLPS(pattern: string): number[] {
  const lps = new Array(pattern.length).fill(0);
  let len = 0;
  
  for (let i = 1; i < pattern.length; i++) {
    while (len > 0 && pattern[i] !== pattern[len]) {
      len = lps[len - 1];
    }
    if (pattern[i] === pattern[len]) len++;
    lps[i] = len;
  }
  
  return lps;
}

Pattern 9: Rotate Array by Reversing Segments

Rotate using multiple reverse operations.

function rotateByReversing(nums: number[], k: number, direction: 'left' | 'right'): void {
  const n = nums.length;
  k = k % n;
  
  if (direction === 'right') {
    reverse(nums, 0, n - 1);
    reverse(nums, 0, k - 1);
    reverse(nums, k, n - 1);
  } else {
    reverse(nums, 0, n - 1);
    reverse(nums, 0, n - k - 1);
    reverse(nums, n - k, n - 1);
  }
}

Time: O(n), Space: O(1)

Pattern 10: Find Rotation Count

Find number of rotations in rotated sorted array.

function findRotationCount(nums: number[]): number {
  let left = 0;
  let right = nums.length - 1;
  
  while (left < right) {
    const mid = Math.floor((left + right) / 2);
    
    // If mid element is greater than right, rotation is in right half
    if (nums[mid] > nums[right]) {
      left = mid + 1;
    } else {
      // Rotation is in left half or at mid
      right = mid;
    }
  }
  
  return left;
}

Time: O(log n), Space: O(1)

Example: [4,5,6,7,0,1,2] → rotation count is 4 (index of minimum).

Pattern 11: Rotate Array Using Block Swap

Rotate array using block swap algorithm.

function rotateBlockSwap(nums: number[], k: number): void {
  const n = nums.length;
  k = k % n;
  
  if (k === 0) return;
  
  rotateBlockSwapHelper(nums, 0, n - k, n - k, k);
}

function rotateBlockSwapHelper(
  nums: number[],
  start1: number,
  end1: number,
  start2: number,
  end2: number
): void {
  const len1 = end1 - start1 + 1;
  const len2 = end2 - start2 + 1;
  
  if (len1 === len2) {
    // Swap blocks of equal size
    for (let i = 0; i < len1; i++) {
      [nums[start1 + i], nums[start2 + i]] = [nums[start2 + i], nums[start1 + i]];
    }
  } else if (len1 < len2) {
    // Swap first len1 elements
    for (let i = 0; i < len1; i++) {
      [nums[start1 + i], nums[start2 + i]] = [nums[start2 + i], nums[start1 + i]];
    }
    // Recurse on remaining
    rotateBlockSwapHelper(nums, start1, end1, start2 + len1, end2);
  } else {
    // Swap last len2 elements
    for (let i = 0; i < len2; i++) {
      [nums[start1 + i], nums[start2 + i]] = [nums[start2 + i], nums[start1 + i]];
    }
    // Recurse on remaining
    rotateBlockSwapHelper(nums, start1 + len2, end1, start2, end2);
  }
}

Time: O(n), Space: O(1)

Pattern 12: Rotate Array Multiple Times

Rotate array multiple times efficiently.

class RotatableArray {
  private nums: number[];
  private rotation: number;
  
  constructor(nums: number[]) {
    this.nums = nums;
    this.rotation = 0;
  }
  
  rotate(k: number): void {
    this.rotation = (this.rotation + k) % this.nums.length;
  }
  
  get(index: number): number {
    const n = this.nums.length;
    const actualIndex = (index - this.rotation + n) % n;
    return this.nums[actualIndex];
  }
  
  set(index: number, value: number): void {
    const n = this.nums.length;
    const actualIndex = (index - this.rotation + n) % n;
    this.nums[actualIndex] = value;
  }
}

Time: O(1) for rotate/get/set, Space: O(n)

Explanation: Track rotation offset instead of actually rotating, compute virtual index.

When to Use Array Rotation Techniques

Use array rotation when:

  • Problem involves shifting elements circularly
  • Need to rotate sorted array and search
  • In-place rotation required (space constraint)
  • Problem asks for minimum in rotated array
  • Matrix rotation problems
  • Cyclic permutations or circular shifts

Template (Reverse-Based Rotation)

function rotateTemplate(nums: number[], k: number, direction: 'left' | 'right'): void {
  const n = nums.length;
  k = k % n;
  
  if (direction === 'right') {
    reverse(nums, 0, n - 1);
    reverse(nums, 0, k - 1);
    reverse(nums, k, n - 1);
  } else {
    reverse(nums, 0, n - 1);
    reverse(nums, 0, n - k - 1);
    reverse(nums, n - k, n - 1);
  }
}

function reverse(nums: number[], start: number, end: number): void {
  while (start < end) {
    [nums[start], nums[end]] = [nums[end], nums[start]];
    start++;
    end--;
  }
}

Template (Binary Search in Rotated Array)

function searchRotated(nums: number[], target: number): number {
  let left = 0;
  let right = nums.length - 1;
  
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    
    if (nums[mid] === target) return mid;
    
    // Determine which half is sorted
    if (nums[left] <= nums[mid]) {
      // Left half is sorted
      if (target >= nums[left] && target < nums[mid]) {
        right = mid - 1;
      } else {
        left = mid + 1;
      }
    } else {
      // Right half is sorted
      if (target > nums[mid] && target <= nums[right]) {
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }
  }
  
  return -1;
}

Time and Space Complexity Summary

  • Reverse-based rotation: O(n) time, O(1) space
  • Cyclic replacement: O(n) time, O(1) space
  • Extra array: O(n) time, O(n) space
  • Search in rotated: O(log n) time, O(1) space
  • Find minimum: O(log n) time, O(1) space
  • Matrix rotation: O(n²) time, O(1) space

Practice Tips

  1. Handle k > n - Always use k % n
  2. Reverse technique - Most elegant in-place solution
  3. Binary search - For rotated sorted arrays
  4. Edge cases - Empty array, k = 0, k = n
  5. Direction - Left vs right rotation logic differs

Common Mistakes

  1. Not handling k > n - Forgetting to mod k
  2. Index errors - Off-by-one in reverse operations
  3. Wrong direction - Confusing left vs right rotation
  4. Binary search - Not checking which half is sorted
  5. Duplicates - Not handling duplicate elements in rotated search

Related Concepts

  • Two Pointers - Used in reverse operations
  • Binary Search - For searching in rotated arrays
  • In-Place Operations - Rotation often requires in-place
  • Modular Arithmetic - For circular indexing

Array rotation is essential for many algorithms. Master these patterns, and you'll efficiently solve rotation and circular array problems in coding interviews.

← PreviousKadane's AlgorithmNext →In-Place Operations