Array

A contiguous block of memory storing elements of the same type, accessible by index in O(1) time.

Complexity

Time (Best)

O(1)

Time (Avg)

O(n)

Time (Worst)

O(n)

Space

O(n)

Key Points

›Random access in O(1) — any element by index instantly
›Cache-friendly: elements stored contiguously in memory
›Insertion/deletion at the front is O(n) — all elements must shift
›Dynamic arrays (ArrayList, Vec) double capacity when full — O(1) amortized append
›Best choice when index-based access is the primary operation

Code Examples

Swift

var arr = [1, 2, 3, 4, 5]

// Access — O(1)
let val = arr[2]           // 3

// Append — O(1) amortized
arr.append(6)

// Insert at index — O(n)
arr.insert(0, at: 0)

// Remove at index — O(n)
arr.remove(at: 0)

// Search — O(n)
if let idx = arr.firstIndex(of: 3) {
    print("Found at index \(idx)")
}

// Slice
let sub = arr[1...3]       // [2, 3, 4]

// Iterate — O(n)
for num in arr { print(num) }

Practice Problems

Two Sum

EasyLeetCode ↗

Best Time to Buy and Sell Stock

EasyLeetCode ↗

Maximum Subarray

MediumLeetCode ↗

Product of Array Except Self

MediumLeetCode ↗