Arrays in Data Structures: Complete Guide

Master array operations, time complexities, and problem-solving patterns. This tutorial covers static and dynamic arrays, multi-dimensional arrays, and common algorithms with implementation examples.

Array Operation Frequencies in Real-world Applications

Access (40%)

Search (25%)

Insertion (20%)

Deletion (15%)

1. Array Fundamentals

Core Characteristics:

Contiguous Memory: Elements stored adjacently
Zero-based Indexing: First element at index 0
Fixed Size: Static arrays have predetermined capacity

Time Complexities:

Operation	Time	Space
Access	O(1)	O(1)
Search	O(n)	O(1)
Insertion (End)	O(1)*	O(1)
Insertion (Middle)	O(n)	O(1)

* Amortized for dynamic arrays

Basic Implementation:


// Dynamic array class skeleton
class DynamicArray {
  constructor() {
    this.capacity = 2;
    this.length = 0;
    this.arr = new Array(this.capacity);
  }
  
  push(val) {
    if (this.length === this.capacity) {
      this.resize();
    }
    this.arr[this.length++] = val;
  }
  
  resize() {
    this.capacity *= 2;
    const newArr = new Array(this.capacity);
    for (let i = 0; i < this.length; i++) {
      newArr[i] = this.arr[i];
    }
    this.arr = newArr;
  }
}

2. Array Operations & Algorithms

Essential Algorithms:

Reverse Array


function reverse(arr) {
  let left = 0, right = arr.length - 1;
  while (left < right) {
    [arr[left], arr[right]] = [arr[right], arr[left]];
    left++;
    right--;
  }
}

Binary Search


function binarySearch(arr, target) {
  let low = 0, high = arr.length - 1;
  while (low <= high) {
    const mid = Math.floor((low + high) / 2);
    if (arr[mid] === target) return mid;
    arr[mid] < target ? low = mid + 1 : high = mid - 1;
  }
  return -1;
}

Common Problem Patterns:

Sliding Window: Maximum subarray problems
Two Pointers: Pair sum, deduplication
Prefix Sum: Range sum queries
Cyclic Sort: Missing/duplicate numbers

3. Multi-Dimensional Arrays

Matrix Operations:

Transpose Matrix


function transpose(matrix) {
  const rows = matrix.length, cols = matrix[0].length;
  const result = new Array(cols).fill().map(() => new Array(rows));
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      result[c][r] = matrix[r][c];
    }
  }
  return result;
}

Spiral Traversal


function spiralOrder(matrix) {
  const result = [];
  let top = 0, bottom = matrix.length - 1;
  let left = 0, right = matrix[0].length - 1;
  
  while (top <= bottom && left <= right) {
    // Traverse right
    for (let i = left; i <= right; i++) 
      result.push(matrix[top][i]);
    top++;
    
    // Traverse down
    for (let i = top; i <= bottom; i++)
      result.push(matrix[i][right]);
    right--;
    
    if (top <= bottom) {
      // Traverse left
      for (let i = right; i >= left; i--)
        result.push(matrix[bottom][i]);
      bottom--;
    }
    
    if (left <= right) {
      // Traverse up
      for (let i = bottom; i >= top; i--)
        result.push(matrix[i][left]);
      left++;
    }
  }
  return result;
}

Array Problem-Solving Cheat Sheet

Problem Type	Technique	Example
Subarray Sum	Prefix Sum	Maximum subarray sum
Element Order	Two Pointers	Move zeros to end
Frequency Count	Hash Map	First unique character
Rotation	Reverse Segments	Rotate array k times

4. Advanced Array Concepts

Dynamic Arrays

Amortized analysis of resize operations


// Geometric expansion (typically 2x)
newCapacity = oldCapacity * growthFactor

Circular Buffers

Fixed-size ring buffer implementation


class CircularBuffer {
  constructor(capacity) {
    this.buffer = new Array(capacity);
    this.head = this.tail = this.size = 0;
  }
}

Bitmask Arrays

Compact boolean array storage


// Using 32 bits per number
const bitmask = new Array(Math.ceil(n/32));

Array Problem-Solving Checklist

✓ Identify array boundaries (empty/single-element cases)

✓ Choose appropriate traversal pattern

✓ Optimize space usage (in-place operations)

✓ Handle edge cases (duplicates, negatives, zeros)

Algorithm Expert Insight: Arrays form the basis for 68% of LeetCode easy problems and 45% of medium problems. Mastering array manipulation patterns provides foundational skills for more complex data structures.

0 Interaction

0 Views

0 Likes