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
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
// 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--;
}
}
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)
let 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
You need to be logged in to participate in this discussion.
×
