Arrays — The Foundation of Data Structures

What is an Array?

An array is a contiguous block of memory storing elements of the same type, accessed by index.

arr = [10, 20, 30, 40, 50]
#      0    1   2   3   4   ← indices

Because elements are stored contiguously, accessing any element by index is O(1) — the CPU can jump directly to base_address + index * element_size.

Core Operations

Access — O(1)

arr[2]   # direct access, always instant

Search — O(n)

def linear_search(arr, target):
    for i, val in enumerate(arr):
        if val == target:
            return i
    return -1

Insert at middle — O(n)

Inserting shifts all elements to the right.

arr.insert(2, 99)  # shifts arr[2], arr[3]... right

Delete at middle — O(n)

Deleting shifts all elements to the left.

arr.pop(2)  # shifts arr[3], arr[4]... left

Static vs Dynamic Arrays

Dynamic arrays (Python lists, Java ArrayList) double in size when full — this makes append O(1) amortized even though occasional resizes are O(n).

Two Pointers — The Most Important Array Pattern

Two pointers is used in ~30% of array interview problems.

Pattern 1 — Opposite ends

def two_sum_sorted(arr, target):
    left, right = 0, len(arr) - 1
    while left < right:
        total = arr[left] + arr[right]
        if total == target:
            return [left, right]
        elif total < target:
            left += 1
        else:
            right -= 1
    return []

Pattern 2 — Fast and slow (Floyd's)

def remove_duplicates(arr):
    if not arr: return 0
    slow = 0
    for fast in range(1, len(arr)):
        if arr[fast] != arr[slow]:
            slow += 1
            arr[slow] = arr[fast]
    return slow + 1

Sliding Window — Second Most Important Pattern

def max_sum_subarray(arr, k):
    # Find max sum of any subarray of size k
    window_sum = sum(arr[:k])
    max_sum = window_sum
 
    for i in range(k, len(arr)):
        window_sum += arr[i] - arr[i - k]  # slide window
        max_sum = max(max_sum, window_sum)
 
    return max_sum

Prefix Sum — O(1) Range Queries

def build_prefix(arr):
    prefix = [0] * (len(arr) + 1)
    for i, val in enumerate(arr):
        prefix[i+1] = prefix[i] + val
    return prefix
 
def range_sum(prefix, left, right):
    return prefix[right+1] - prefix[left]  # O(1) query!

Common Interview Patterns

Pattern	When to use	Example problems
Two pointers	Sorted array, pairs	Two Sum, Container With Most Water
Sliding window	Subarray/substring	Max sum subarray, Longest substring
Prefix sum	Range sum queries	Subarray sum equals K
Kadane's algorithm	Max subarray sum	Maximum Subarray
Binary search	Sorted array search	Search in rotated array

Kadane's Algorithm — Max Subarray

def max_subarray(arr):
    max_sum = current_sum = arr[0]
    for num in arr[1:]:
        current_sum = max(num, current_sum + num)
        max_sum = max(max_sum, current_sum)
    return max_sum

Key Takeaway

Arrays give O(1) access but O(n) insert/delete in the middle
Two pointers and sliding window solve most array problems
Prefix sums turn O(n) range queries into O(1)
When stuck on an array problem, ask: can I sort it first? Can I use two pointers?