[AlgoMastery]
Topics›Array›Circular Array
📖

Circular Array

Array
~20 min read
5 practice problems

Overview

Circular Array problems involve arrays where the end wraps around to the beginning, creating a circular structure. Elements can be accessed using modular arithmetic: index % array.length to handle wraparound.

The key insight: use modulo operator to handle circular indexing. When index exceeds array bounds, wrap around using (index % n + n) % n to handle negative indices correctly.

Circular array is particularly useful for:

  • Rotating arrays
  • Circular buffers
  • Ring data structures
  • Wraparound indexing
  • Circular queue/stack
  • Next/previous element queries

Pattern 1: Circular Index Access

Access elements with wraparound.

class CircularArray<T> {
  private data: T[];
  
  constructor(data: T[]) {
    this.data = [...data];
  }
  
  get(index: number): T {
    const n = this.data.length;
    const normalizedIndex = ((index % n) + n) % n;
    return this.data[normalizedIndex];
  }
  
  set(index: number, value: T): void {
    const n = this.data.length;
    const normalizedIndex = ((index % n) + n) % n;
    this.data[normalizedIndex] = value;
  }
  
  next(index: number): number {
    return (index + 1) % this.data.length;
  }
  
  previous(index: number): number {
    return (index - 1 + this.data.length) % this.data.length;
  }
}

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

Pattern 2: Search in Circular Sorted Array

Search target in rotated sorted array.

function searchCircular(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)

Pattern 3: Next Greater Element (Circular)

Find next greater element in circular array.

function nextGreaterElementsCircular(nums: number[]): number[] {
  const n = nums.length;
  const result = new Array(n).fill(-1);
  const stack: number[] = [];
  
  // Process array twice for circular
  for (let i = 0; i < n * 2; i++) {
    const index = i % n;
    
    while (stack.length > 0 && nums[index] > nums[stack[stack.length - 1]]) {
      const top = stack.pop()!;
      result[top] = nums[index];
    }
    
    if (i < n) {
      stack.push(index);
    }
  }
  
  return result;
}

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

Pattern 4: Circular Array Loop

Detect cycle in circular array.

function circularArrayLoop(nums: number[]): boolean {
  const n = nums.length;
  
  for (let i = 0; i < n; i++) {
    if (nums[i] === 0) continue;
    
    let slow = i;
    let fast = i;
    
    // Check if cycle exists
    do {
      slow = getNext(nums, slow);
      fast = getNext(nums, getNext(nums, fast));
    } while (slow !== fast);
    
    // Check if cycle is valid (same direction, length > 1)
    if (slow === getNext(nums, slow)) {
      continue; // Length 1 cycle
    }
    
    let current = slow;
    let direction = nums[current] > 0;
    let valid = true;
    
    do {
      if ((nums[current] > 0) !== direction) {
        valid = false;
        break;
      }
      current = getNext(nums, current);
    } while (current !== slow);
    
    if (valid) return true;
  }
  
  return false;
}

function getNext(nums: number[], index: number): number {
  const n = nums.length;
  return ((index + nums[index]) % n + n) % n;
}

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

Pattern 5: Circular Queue

Implement circular queue.

class CircularQueue<T> {
  private data: (T | undefined)[];
  private head: number;
  private tail: number;
  private size: number;
  private capacity: number;
  
  constructor(k: number) {
    this.capacity = k;
    this.data = new Array(k);
    this.head = 0;
    this.tail = 0;
    this.size = 0;
  }
  
  enQueue(value: T): boolean {
    if (this.isFull()) return false;
    
    this.data[this.tail] = value;
    this.tail = (this.tail + 1) % this.capacity;
    this.size++;
    return true;
  }
  
  deQueue(): boolean {
    if (this.isEmpty()) return false;
    
    this.data[this.head] = undefined;
    this.head = (this.head + 1) % this.capacity;
    this.size--;
    return true;
  }
  
  Front(): T | -1 {
    if (this.isEmpty()) return -1;
    return this.data[this.head]!;
  }
  
  Rear(): T | -1 {
    if (this.isEmpty()) return -1;
    const rearIndex = (this.tail - 1 + this.capacity) % this.capacity;
    return this.data[rearIndex]!;
  }
  
  isEmpty(): boolean {
    return this.size === 0;
  }
  
  isFull(): boolean {
    return this.size === this.capacity;
  }
}

Time: O(1) for all operations, Space: O(k)

Pattern 6: Rotate Circular Array

Rotate elements in circular array.

function rotateCircular(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)

Pattern 7: Maximum Sum Circular Subarray

Find maximum sum subarray in circular array.

function maxSubarraySumCircular(nums: number[]): number {
  // Case 1: Maximum subarray in linear array (normal Kadane)
  let maxSum = nums[0];
  let currentMax = nums[0];
  
  // Case 2: Maximum sum wraps around (total - minimum subarray)
  let minSum = nums[0];
  let currentMin = nums[0];
  let totalSum = nums[0];
  
  for (let i = 1; i < nums.length; i++) {
    totalSum += nums[i];
    
    // Maximum subarray
    currentMax = Math.max(nums[i], currentMax + nums[i]);
    maxSum = Math.max(maxSum, currentMax);
    
    // Minimum subarray
    currentMin = Math.min(nums[i], currentMin + nums[i]);
    minSum = Math.min(minSum, currentMin);
  }
  
  // If all negative, return maxSum
  if (maxSum < 0) return maxSum;
  
  // Maximum is either normal max or (total - min)
  return Math.max(maxSum, totalSum - minSum);
}

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

Pattern 8: Circular Permutation

Generate circular permutations.

function circularPermutations(nums: number[]): number[][] {
  const result: number[][] = [];
  const n = nums.length;
  
  // Generate all rotations
  for (let i = 0; i < n; i++) {
    const rotated: number[] = [];
    for (let j = 0; j < n; j++) {
      rotated.push(nums[(i + j) % n]);
    }
    result.push(rotated);
  }
  
  return result;
}

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

Pattern 9: Circular Buffer

Implement circular buffer.

class CircularBuffer<T> {
  private buffer: (T | undefined)[];
  private writeIndex: number;
  private readIndex: number;
  private count: number;
  private capacity: number;
  
  constructor(capacity: number) {
    this.capacity = capacity;
    this.buffer = new Array(capacity);
    this.writeIndex = 0;
    this.readIndex = 0;
    this.count = 0;
  }
  
  write(value: T): boolean {
    if (this.isFull()) return false;
    
    this.buffer[this.writeIndex] = value;
    this.writeIndex = (this.writeIndex + 1) % this.capacity;
    this.count++;
    return true;
  }
  
  read(): T | undefined {
    if (this.isEmpty()) return undefined;
    
    const value = this.buffer[this.readIndex];
    this.buffer[this.readIndex] = undefined;
    this.readIndex = (this.readIndex + 1) % this.capacity;
    this.count--;
    return value;
  }
  
  peek(): T | undefined {
    if (this.isEmpty()) return undefined;
    return this.buffer[this.readIndex];
  }
  
  isEmpty(): boolean {
    return this.count === 0;
  }
  
  isFull(): boolean {
    return this.count === this.capacity;
  }
}

Time: O(1) for all operations, Space: O(capacity)

Pattern 10: Circular Array Traversal

Traverse circular array from any starting point.

function traverseCircular<T>(arr: T[], startIndex: number, direction: 'forward' | 'backward' = 'forward'): T[] {
  const result: T[] = [];
  const n = arr.length;
  
  if (direction === 'forward') {
    for (let i = 0; i < n; i++) {
      const index = (startIndex + i) % n;
      result.push(arr[index]);
    }
  } else {
    for (let i = 0; i < n; i++) {
      const index = (startIndex - i + n) % n;
      result.push(arr[index]);
    }
  }
  
  return result;
}

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

Pattern 11: Circular Array Range Query

Query range in circular array.

function circularRangeQuery(
  arr: number[],
  start: number,
  end: number
): number[] {
  const n = arr.length;
  const result: number[] = [];
  
  if (start <= end) {
    // Normal range
    for (let i = start; i <= end; i++) {
      result.push(arr[i % n]);
    }
  } else {
    // Wraps around
    for (let i = start; i < n; i++) {
      result.push(arr[i]);
    }
    for (let i = 0; i <= end; i++) {
      result.push(arr[i]);
    }
  }
  
  return result;
}

Time: O(end - start), Space: O(end - start)

Pattern 12: Circular Array Maximum Distance

Find maximum distance between two elements in circular array.

function maxCircularDistance(arr: number[]): number {
  const n = arr.length;
  let maxDist = 0;
  
  for (let i = 0; i < n; i++) {
    for (let j = i + 1; j < n; j++) {
      // Distance going forward
      const forwardDist = j - i;
      // Distance going backward (circular)
      const backwardDist = i + (n - j);
      
      const minDist = Math.min(forwardDist, backwardDist);
      maxDist = Math.max(maxDist, minDist);
    }
  }
  
  return maxDist;
}

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

When to Use Circular Array Techniques

Use circular array techniques when:

  • Array wraps around (end connects to beginning)
  • Need circular buffer or queue
  • Rotating array elements
  • Circular permutations or rotations
  • Ring data structures
  • Wraparound indexing required

Key insight: Use modulo operator (index % n + n) % n for safe circular indexing.

Template (Circular Index Access)

function getCircularIndex<T>(arr: T[], index: number): T {
  const n = arr.length;
  const normalizedIndex = ((index % n) + n) % n;
  return arr[normalizedIndex];
}

function setCircularIndex<T>(arr: T[], index: number, value: T): void {
  const n = arr.length;
  const normalizedIndex = ((index % n) + n) % n;
  arr[normalizedIndex] = value;
}

Template (Circular Traversal)

function traverseCircularTemplate<T>(
  arr: T[],
  start: number,
  steps: number,
  direction: 'forward' | 'backward'
): T[] {
  const result: T[] = [];
  const n = arr.length;
  
  for (let i = 0; i < steps; i++) {
    const offset = direction === 'forward' ? i : -i;
    const index = ((start + offset) % n + n) % n;
    result.push(arr[index]);
  }
  
  return result;
}

Time and Space Complexity Summary

  • Circular index access: O(1) time, O(1) space
  • Search circular sorted: O(log n) time, O(1) space
  • Next greater circular: O(n) time, O(n) space
  • Circular queue: O(1) time per operation, O(k) space
  • Rotate circular: O(n) time, O(1) space
  • Max sum circular: O(n) time, O(1) space

Practice Tips

  1. Modulo arithmetic - Use (index % n + n) % n for safe indexing
  2. Handle wraparound - Consider both forward and backward paths
  3. Circular vs linear - Distinguish when wraparound matters
  4. Edge cases - Empty array, single element, full rotation
  5. Visualization - Draw circular structure to understand

Common Mistakes

  1. Index errors - Not handling negative indices correctly
  2. Off-by-one - Errors in circular calculations
  3. Not normalizing - Forgetting to normalize indices
  4. Direction confusion - Mixing forward and backward traversal
  5. Boundary handling - Not handling wraparound correctly

Related Concepts

  • Modular Arithmetic - Core technique
  • Array Rotation - Related operation
  • Circular Queue - Data structure application
  • Ring Buffer - Real-world application

Circular array is essential for ring data structures and wraparound problems. Master modulo arithmetic and circular indexing, and you'll efficiently solve circular array problems in coding interviews.

← PreviousArray TransformationNext →Binary Search