Report Content

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;
  }
}


# Dynamic array class skeleton
class DynamicArray:
    def __init__(self):
        self.capacity = 2
        self.length = 0
        self.arr = [None] * self.capacity

    def push(self, val):
        if self.length == self.capacity:
            self.resize()
        self.arr[self.length] = val
        self.length += 1

    def resize(self):
        self.capacity *= 2
        newArr = [None] * self.capacity
        for i in range(self.length):
            newArr[i] = self.arr[i]
        self.arr = newArr


class DynamicArray {
    private int capacity = 2;
    private int length = 0;
    private int[] arr = new int[capacity];

    public void push(int val) {
        if (length == capacity) {
            resize();
        }
        arr[length++] = val;
    }

    private void resize() {
        capacity *= 2;
        int[] newArr = new int[capacity];
        for (int i = 0; i < length; i++) {
            newArr[i] = arr[i];
        }
        arr = newArr;
    }
}


class DynamicArray {
private:
    int capacity = 2;
    int length = 0;
    int* arr = new int[capacity];

public:
    void push(int val) {
        if (length == capacity) {
            resize();
        }
        arr[length++] = val;
    }

    void resize() {
        capacity *= 2;
        int* newArr = new int[capacity];
        for (int i = 0; i < length; i++) {
            newArr[i] = arr[i];
        }
        arr = newArr;
    }
};

2. Array Operations & Algorithms

Essential Algorithms:

Reverse Array


// JS 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--;
  }
}


# Python reverse array
def reverse(arr):
    left, right = 0, len(arr)-1
    while left < right:
        arr[left], arr[right] = arr[right], arr[left]
        left += 1
        right -= 1


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


void reverse(vector<int>& arr) {
    int left = 0, right = arr.size() - 1;
    while (left < right) {
        swap(arr[left], arr[right]);
        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;
}


def binary_search(arr, target):
    low, high = 0, len(arr) - 1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid
        if arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1


int binarySearch(int[] arr, int target) {
    int low = 0, high = arr.length - 1;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (arr[mid] == target) return mid;
        if (arr[mid] < target)
            low = mid + 1;
        else
            high = mid - 1;
    }
    return -1;
}


int binarySearch(const vector<int>& arr, int target) {
    int low = 0, high = arr.size() - 1;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (arr[mid] == target) return mid;
        if (arr[mid] < target)
            low = mid + 1;
        else
            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;
}


def transpose(matrix):
    rows, cols = len(matrix), len(matrix[0])
    result = [[0] * rows for _ in range(cols)]
    for r in range(rows):
        for c in range(cols):
            result[c][r] = matrix[r][c]
    return result


int[][] transpose(int[][] matrix) {
    int rows = matrix.length;
    int cols = matrix[0].length;
    int[][] result = new int[cols][rows];

    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            result[c][r] = matrix[r][c];
        }
    }
    return result;
}


vector<vector<int>> transpose(const vector<vector<int>>& matrix) {
    int rows = matrix.size();
    int cols = matrix[0].size();
    vector<vector<int>> result(cols, vector<int>(rows));

    for (int r = 0; r < rows; r++) {
        for (int 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;
}


def spiral_order(matrix):
    result = []
    top, bottom = 0, len(matrix) - 1
    left, right = 0, len(matrix[0]) - 1

    while top <= bottom and left <= right:
        for i in range(left, right + 1):
            result.append(matrix[top][i])
        top += 1

        for i in range(top, bottom + 1):
            result.append(matrix[i][right])
        right -= 1

        if top <= bottom:
            for i in range(right, left - 1, -1):
                result.append(matrix[bottom][i])
            bottom -= 1

        if left <= right:
            for i in range(bottom, top - 1, -1):
                result.append(matrix[i][left])
            left += 1

    return result


List spiralOrder(int[][] matrix) {
    List result = new ArrayList<>();
    int top = 0, bottom = matrix.length - 1;
    int left = 0, right = matrix[0].length - 1;

    while (top <= bottom && left <= right) {
        for (int i = left; i <= right; i++)
            result.add(matrix[top][i]);
        top++;

        for (int i = top; i <= bottom; i++)
            result.add(matrix[i][right]);
        right--;

        if (top <= bottom) {
            for (int i = right; i >= left; i--)
                result.add(matrix[bottom][i]);
            bottom--;
        }

        if (left <= right) {
            for (int i = bottom; i >= top; i--)
                result.add(matrix[i][left]);
            left++;
        }
    }
    return result;
}


vector<int> spiralOrder(vector<vector<int>>& matrix) {
    vector<int> result;
    int top = 0, bottom = matrix.size() - 1;
    int left = 0, right = matrix[0].size() - 1;

    while (top <= bottom && left <= right) {
        for (int i = left; i <= right; i++)
            result.push_back(matrix[top][i]);
        top++;

        for (int i = top; i <= bottom; i++)
            result.push_back(matrix[i][right]);
        right--;

        if (top <= bottom) {
            for (int i = right; i >= left; i--)
                result.push_back(matrix[bottom][i]);
            bottom--;
        }

        if (left <= right) {
            for (int i = bottom; i >= top; i--)
                result.push_back(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)
let newCapacity = oldCapacity * growthFactor;


# Geometric expansion (typically 2x)
new_capacity = old_capacity * growth_factor


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


// Geometric expansion (typically 2x)
int 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;
  }
}


class CircularBuffer:
    def __init__(self, capacity):
        self.buffer = [None] * capacity
        self.head = self.tail = self.size = 0


class CircularBuffer {
    private int[] buffer;
    private int head, tail, size;

    public CircularBuffer(int capacity) {
        buffer = new int[capacity];
        head = tail = size = 0;
    }
}


class CircularBuffer {
private:
    std::vector<int> buffer;
    int head, tail, size;

public:
    CircularBuffer(int capacity) : buffer(capacity), head(0), tail(0), size(0) {}
};

Bitmask Arrays

Compact boolean array storage


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


# Using 32 bits per number
bitmask = [0] * ((n + 31) // 32)


// Using 32 bits per number
int[] bitmask = new int[(int)Math.ceil(n / 32.0)];


// Using 32 bits per number
std::vector<int> bitmask((n + 31) / 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.

You need to be logged in to participate in this discussion.