Arrays

Intro

An array is a contiguous block of memory storing elements of the same type, indexed from 0. Because elements are contiguous and fixed-size, the offset of any index can be computed in constant time, which makes random access $O(1)$ . Arrays are the substrate beneath many higher-level data structures (strings, stacks, queues, heaps, hash-table buckets), so time spent mastering array manipulation pays off everywhere.

In-depth description

A static array has a fixed size chosen at allocation time (C int a[10]). A dynamic array, Python list, Java ArrayList, C++ std::vector, Go slice, JavaScript Array, resizes automatically, typically by doubling capacity when the backing store fills up. This gives amortized $O(1)$ append: most appends are $O(1)$ , with the occasional $O(n)$ copy amortized across the preceding n cheap appends.

Because elements are contiguous, inserting or deleting in the middle requires shifting everything after that index, $O(n)$ . If the array is sorted, binary search reduces lookup to $O(log n)$ . Many interview problems exploit one of three array-specific patterns:

Two pointers: walk from both ends or at different speeds; common when the array is sorted or when pairing elements.
Sliding window: maintain a contiguous range [left, right] and move the boundaries to satisfy a constraint; converts many $O(n²)$ brute forces to $O(n)$ .
Prefix sums: precompute prefix[i] = sum of elements up to i once, then answer any range-sum query in $O(1)$ .

Multi-dimensional arrays are rows-of-rows (C-style), or use strides for $O(1)$ slicing (NumPy). In-place algorithms (Dutch National Flag, reverse, rotate) are a frequent source of interview questions because they force careful pointer bookkeeping.

Time complexity

Operation	Average	Worst
Access by index	$O(1)$	$O(1)$
Search (unsorted)	$O(n)$	$O(n)$
Search (sorted, binary)	$O(log n)$	$O(log n)$
Append (dynamic array)	$O(1)$ amortized	$O(n)$ (resize)
Insert at index	$O(n)$	$O(n)$
Delete at index	$O(n)$	$O(n)$
Space	$O(n)$	$O(n)$

Common uses in DSA

Two-pointer problems: Two Sum II (sorted), Valid Palindrome, 3Sum, Container With Most Water.
Sliding window: Longest Substring Without Repeating Characters, Maximum Sum Subarray of Size K, Minimum Size Subarray Sum.
Binary search on an array or on the answer: Search in Rotated Sorted Array, Find Peak Element, Koko Eating Bananas, Median of Two Sorted Arrays.
Prefix sums / difference arrays: Range Sum Query, Subarray Sum Equals K, Product of Array Except Self.
In-place rearrangement and sorting: Dutch National Flag (Sort Colors), Move Zeroes, Rotate Array, Next Permutation.

Canonical LeetCode problems: #1 Two Sum, #11 Container With Most Water, #15 3Sum, #42 Trapping Rain Water, #53 Maximum Subarray, #56 Merge Intervals, #238 Product of Array Except Self.

Python example

# Dynamic array basics
arr = [1, 2, 3]
arr.append(4)           # O(1) amortized
arr.insert(0, 0)        # O(n), shifts everything right
arr.pop()               # O(1) from end
arr.pop(0)              # O(n) from front

# Two-pointer: Two Sum on a sorted array
def two_sum_sorted(nums, target):
    l, r = 0, len(nums), 1
    while l < r:
        s = nums[l] + nums[r]
        if s == target:
            return [l, r]
        if s < target:
            l += 1
        else:
            r -= 1
    return [-1, -1]

# Sliding window: longest substring with at most k distinct characters
from collections import Counter
def longest_k_distinct(s, k):
    counts, left, best = Counter(), 0, 0
    for right, ch in enumerate(s):
        counts[ch] += 1
        while len(counts) > k:
            counts[s[left]] -= 1
            if counts[s[left]] == 0:
                del counts[s[left]]
            left += 1
        best = max(best, right, left + 1)
    return best

# Binary search over a sorted array
def binary_search(nums, target):
    lo, hi = 0, len(nums), 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if nums[mid] == target:
            return mid
        if nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid, 1
    return -1

# Prefix sums: answer range-sum queries in O(1) after O(n) preprocessing
def range_sum_array(nums):
    prefix = [0] * (len(nums) + 1)
    for i, x in enumerate(nums):
        prefix[i + 1] = prefix[i] + x
    def range_sum(i, j):   # inclusive sum of nums[i..j]
        return prefix[j + 1], prefix[i]
    return range_sum

LeetCode problems

Arrays are the most referenced data structure in the NeetCode 150, 74 problems across 17 categories.

Arrays & Hashing:

Two Pointers:

Sliding Window:

Stack:

Binary Search:

Linked List:

287. Find the Duplicate Number, array indexed as implicit linked list

Heap / Priority Queue:

Backtracking:

39. Combination Sum
40. Combination Sum II
46. Permutations
51. N-Queens, board as array
78. Subsets
79. Word Search, grid DFS + in-place visited
90. Subsets II
131. Palindrome Partitioning, 2-D palindrome DP table

Tries:

212. Word Search II, grid with in-place visited marker

Graphs:

Advanced Graphs:

778. Swim in Rising Water, grid with modified Dijkstra

1-D Dynamic Programming:

2-D Dynamic Programming:

Greedy:

Intervals:

Math & Geometry:

43. Multiply Strings, digit array accumulator
48. Rotate Image
50. Pow(x, n)
54. Spiral Matrix
66. Plus One
73. Set Matrix Zeroes

Bit Manipulation: