Array Manipulation

Overview

Array Manipulation involves transforming, reorganizing, and modifying arrays to achieve desired configurations. This includes operations like adding/removing elements, rearranging, combining, splitting, and applying transformations.

Array manipulation techniques:

• Element operations - Add, remove, update
• Reorganization - Rearrange, partition, group
• Transformation - Map, filter, reduce
• Combination - Merge, concatenate, interleave
• Splitting - Partition, chunk, divide

Array manipulation is particularly useful for:

• Data preprocessing
• Algorithm preparation
• Format conversion
• Problem transformation
• Optimization

Pattern 1: Add Element at Index

Insert element at specific position.

function insertAt(nums: number[], index: number, value: number): number[] {
  const result = [...nums];
  result.splice(index, 0, value);
  return result;
}

// In-place version
function insertAtInPlace(nums: number[], index: number, value: number): void {
  nums.push(0); // Add space
  
  // Shift elements right
  for (let i = nums.length - 1; i > index; i--) {
    nums[i] = nums[i - 1];
  }
  
  nums[index] = value;
}

Time: O(n), Space: O(n) or O(1) in-place

Pattern 2: Remove Element at Index

Remove element at specific position.

function removeAt(nums: number[], index: number): number[] {
  return nums.filter((_, i) => i !== index);
}

// In-place version
function removeAtInPlace(nums: number[], index: number): void {
  for (let i = index; i < nums.length - 1; i++) {
    nums[i] = nums[i + 1];
  }
  nums.pop();
}

// Efficient in-place (order doesn't matter)
function removeAtSwap(nums: number[], index: number): void {
  nums[index] = nums[nums.length - 1];
  nums.pop();
}

Time: O(n), Space: O(n) or O(1) in-place

Pattern 3: Rotate Array Elements

Rotate array elements by K positions.

function rotate(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 4: Shuffle Array

Randomly shuffle array elements.

function shuffle(nums: number[]): number[] {
  const result = [...nums];
  
  for (let i = result.length - 1; i > 0; i--) {
    const j = Math.floor(Math.random() * (i + 1));
    [result[i], result[j]] = [result[j], result[i]];
  }
  
  return result;
}

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

Fisher-Yates shuffle algorithm.

Pattern 5: Chunk Array

Split array into chunks of specified size.

function chunkArray(nums: number[], size: number): number[][] {
  const chunks: number[][] = [];
  
  for (let i = 0; i < nums.length; i += size) {
    chunks.push(nums.slice(i, i + size));
  }
  
  return chunks;
}

// Using reduce
function chunkArrayReduce(nums: number[], size: number): number[][] {
  return nums.reduce((chunks: number[][], num, index) => {
    const chunkIndex = Math.floor(index / size);
    if (!chunks[chunkIndex]) chunks[chunkIndex] = [];
    chunks[chunkIndex].push(num);
    return chunks;
  }, []);
}

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

Pattern 6: Flatten Nested Array

Flatten multi-dimensional array.

function flatten(nums: any[]): number[] {
  const result: number[] = [];
  
  for (const item of nums) {
    if (Array.isArray(item)) {
      result.push(...flatten(item));
    } else {
      result.push(item);
    }
  }
  
  return result;
}

// Iterative version
function flattenIterative(nums: any[]): number[] {
  const result: number[] = [];
  const stack = [...nums];
  
  while (stack.length > 0) {
    const item = stack.pop()!;
    
    if (Array.isArray(item)) {
      stack.push(...item);
    } else {
      result.push(item);
    }
  }
  
  return result.reverse();
}

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

Pattern 7: Group Elements by Property

Group array elements by a property.

function groupBy<T>(arr: T[], keyFn: (item: T) => string): Record<string, T[]> {
  return arr.reduce((groups, item) => {
    const key = keyFn(item);
    if (!groups[key]) groups[key] = [];
    groups[key].push(item);
    return groups;
  }, {} as Record<string, T[]>);
}

// Example: Group by length
const strings = ['a', 'bb', 'ccc', 'dd', 'eee'];
const grouped = groupBy(strings, s => s.length.toString());
// { '1': ['a'], '2': ['bb', 'dd'], '3': ['ccc', 'eee'] }

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

Pattern 8: Interleave Arrays

Interleave elements from two arrays.

function interleave(arr1: number[], arr2: number[]): number[] {
  const result: number[] = [];
  const maxLen = Math.max(arr1.length, arr2.length);
  
  for (let i = 0; i < maxLen; i++) {
    if (i < arr1.length) result.push(arr1[i]);
    if (i < arr2.length) result.push(arr2[i]);
  }
  
  return result;
}

// Alternating pattern
function interleaveAlternating(arr1: number[], arr2: number[]): number[] {
  const result: number[] = [];
  const minLen = Math.min(arr1.length, arr2.length);
  
  for (let i = 0; i < minLen; i++) {
    result.push(arr1[i], arr2[i]);
  }
  
  result.push(...arr1.slice(minLen), ...arr2.slice(minLen));
  return result;
}

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

Pattern 9: Zip Arrays

Combine arrays element-wise.

function zip<T, U>(arr1: T[], arr2: U[]): [T, U][] {
  const result: [T, U][] = [];
  const minLen = Math.min(arr1.length, arr2.length);
  
  for (let i = 0; i < minLen; i++) {
    result.push([arr1[i], arr2[i]]);
  }
  
  return result;
}

// Zip multiple arrays
function zipMultiple<T>(...arrays: T[][]): T[][] {
  const result: T[][] = [];
  const minLen = Math.min(...arrays.map(arr => arr.length));
  
  for (let i = 0; i < minLen; i++) {
    result.push(arrays.map(arr => arr[i]));
  }
  
  return result;
}

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

Pattern 10: Transpose 2D Array

Transpose matrix (swap rows and columns).

function transpose(matrix: number[][]): number[][] {
  const rows = matrix.length;
  const cols = matrix[0].length;
  const result: number[][] = Array(cols).fill(null).map(() => Array(rows).fill(0));
  
  for (let i = 0; i < rows; i++) {
    for (let j = 0; j < cols; j++) {
      result[j][i] = matrix[i][j];
    }
  }
  
  return result;
}

// In-place for square matrix
function transposeInPlace(matrix: number[][]): void {
  const n = matrix.length;
  
  for (let i = 0; i < n; i++) {
    for (let j = i + 1; j < n; j++) {
      [matrix[i][j], matrix[j][i]] = [matrix[j][i], matrix[i][j]];
    }
  }
}

Time: O(rows cols), Space: O(rows cols) or O(1) in-place

Pattern 11: Array Difference and Intersection

Find difference and intersection of arrays.

function arrayDifference(arr1: number[], arr2: number[]): number[] {
  const set2 = new Set(arr2);
  return arr1.filter(x => !set2.has(x));
}

function arrayIntersection(arr1: number[], arr2: number[]): number[] {
  const set1 = new Set(arr1);
  return arr2.filter(x => set1.has(x));
}

function arrayUnion(arr1: number[], arr2: number[]): number[] {
  return [...new Set([...arr1, ...arr2])];
}

// With duplicates handling
function intersectionWithDuplicates(arr1: number[], arr2: number[]): number[] {
  const freq1 = new Map<number, number>();
  const freq2 = new Map<number, number>();
  
  for (const num of arr1) {
    freq1.set(num, (freq1.get(num) || 0) + 1);
  }
  for (const num of arr2) {
    freq2.set(num, (freq2.get(num) || 0) + 1);
  }
  
  const result: number[] = [];
  for (const [num, count1] of freq1) {
    const count2 = freq2.get(num) || 0;
    const minCount = Math.min(count1, count2);
    for (let i = 0; i < minCount; i++) {
      result.push(num);
    }
  }
  
  return result;
}

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

Pattern 12: Array Transformation Pipeline

Apply multiple transformations in sequence.

class ArrayPipeline<T> {
  private data: T[];
  
  constructor(data: T[]) {
    this.data = [...data];
  }
  
  map<U>(fn: (item: T) => U): ArrayPipeline<U> {
    return new ArrayPipeline(this.data.map(fn));
  }
  
  filter(fn: (item: T) => boolean): ArrayPipeline<T> {
    return new ArrayPipeline(this.data.filter(fn));
  }
  
  sort(compareFn?: (a: T, b: T) => number): ArrayPipeline<T> {
    return new ArrayPipeline([...this.data].sort(compareFn));
  }
  
  reverse(): ArrayPipeline<T> {
    return new ArrayPipeline([...this.data].reverse());
  }
  
  chunk(size: number): ArrayPipeline<T[]> {
    const chunks: T[][] = [];
    for (let i = 0; i < this.data.length; i += size) {
      chunks.push(this.data.slice(i, i + size));
    }
    return new ArrayPipeline(chunks);
  }
  
  toArray(): T[] {
    return [...this.data];
  }
}

// Usage
const result = new ArrayPipeline([1, 2, 3, 4, 5, 6])
  .filter(x => x % 2 === 0)
  .map(x => x * 2)
  .chunk(2)
  .toArray();
// [[4, 8], [12]]

Time: Depends on operations, Space: O(n)

Pattern 13: Array Window Operations

Apply operations to sliding windows.

function windowMap<T, U>(arr: T[], size: number, fn: (window: T[]) => U): U[] {
  const result: U[] = [];
  
  for (let i = 0; i <= arr.length - size; i++) {
    const window = arr.slice(i, i + size);
    result.push(fn(window));
  }
  
  return result;
}

// Example: Moving average
function movingAverage(nums: number[], windowSize: number): number[] {
  return windowMap(nums, windowSize, window => {
    return window.reduce((a, b) => a + b, 0) / window.length;
  });
}

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

Pattern 14: Array Permutations

Generate all permutations of array.

function permutations<T>(arr: T[]): T[][] {
  if (arr.length === 0) return [[]];
  if (arr.length === 1) return [[...arr]];
  
  const result: T[][] = [];
  
  for (let i = 0; i < arr.length; i++) {
    const rest = [...arr.slice(0, i), ...arr.slice(i + 1)];
    const perms = permutations(rest);
    
    for (const perm of perms) {
      result.push([arr[i], ...perm]);
    }
  }
  
  return result;
}

// Iterative version
function permutationsIterative<T>(arr: T[]): T[][] {
  const result: T[][] = [[]];
  
  for (const item of arr) {
    const newPerms: T[][] = [];
    
    for (const perm of result) {
      for (let i = 0; i <= perm.length; i++) {
        newPerms.push([...perm.slice(0, i), item, ...perm.slice(i)]);
      }
    }
    
    result.length = 0;
    result.push(...newPerms);
  }
  
  return result;
}

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

When to Use Array Manipulation

Use array manipulation when:

• Need to transform array structure
• Preprocess data for algorithms
• Combine or split arrays
• Reorganize elements
• Format conversion
• Data pipeline operations

Key principles:

• Prefer immutable operations when possible
• Use in-place when space is constrained
• Consider time complexity trade-offs

Template (Immutable Operations)

function manipulateImmutable<T>(arr: T[], operations: Array<(arr: T[]) => T[]>): T[] {
  return operations.reduce((acc, op) => op(acc), arr);
}

// Usage
const result = manipulateImmutable([1, 2, 3, 4], [
  arr => arr.filter(x => x % 2 === 0),
  arr => arr.map(x => x * 2),
  arr => arr.reverse()
]);

Template (In-Place Operations)

function manipulateInPlace<T>(arr: T[], operations: Array<(arr: T[]) => void>): void {
  operations.forEach(op => op(arr));
}

Time and Space Complexity Summary

• Add/Remove: O(n) time, O(n) or O(1) space
• Rotate: O(n) time, O(1) space
• Chunk: O(n) time, O(n) space
• Flatten: O(n) time, O(n) space
• Group: O(n) time, O(n) space
• Transpose: O(rows cols) time, O(rows cols) space
• Permutations: O(n! n) time, O(n! n) space

Practice Tips

1. Immutable vs mutable - Choose based on requirements
2. Space optimization - Use in-place when possible
3. Chaining - Build pipelines for complex transformations
4. Edge cases - Empty arrays, single element, duplicates
5. Performance - Consider time complexity for large arrays

Common Mistakes

1. Mutating original - Not copying when needed
2. Index errors - Off-by-one in loops
3. Memory leaks - Not cleaning up references
4. Inefficient operations - Using O(n²) when O(n) possible
5. Type errors - Not handling mixed types correctly

Related Concepts

• In-Place Operations - Space-efficient manipulation
• Functional Programming - Map, filter, reduce patterns
• Data Structures - Arrays as building blocks
• Algorithms - Many algorithms involve array manipulation

Array manipulation is fundamental to working with data. Master these patterns, and you'll efficiently transform and process arrays in coding interviews and real-world applications.