CATEGORY 2 OF 13

Array Basics

Build fluency with arrays — the most fundamental data structure. Learn creation, traversal, mutation, and the built-in methods you will use in every coding problem.

Time: O(n)

Space: O(1) to O(n)

Learn & Reference

Understanding the Pattern

Array Basics

Arrays are the backbone of almost every coding problem. Whether the input is a list of numbers, a sequence of characters, or a collection of objects, you need to be comfortable creating, reading, modifying, and iterating over arrays before tackling any algorithmic pattern.

Core Operations

Creation & Access

Create arrays of fixed or dynamic size. Access elements by zero-based index. Know how to get the length, first element, and last element in your language.

Traversal

Iterate forward, backward, or with index tracking. Use for, for...of, forEach, or enumerate/range depending on what you need (index, value, or both).

Mutation

Add/remove elements at the beginning, end, or middle. Know the difference between methods that mutate in place vs. return a new array.

Search & Filter

Find elements, check existence, filter by condition. Know when to use built-in methods vs. manual loops.

Key Principles

Zero-based indexing — the first element is at index 0, the last is at length - 1
Bounds checking — always verify index is within [0, length) before access
In-place vs. copy — some methods mutate the original array; others return a new one. Know which is which in your language
Contiguous memory — arrays have O(1) random access but O(n) insertion/deletion in the middle

Common Problem Patterns

Linear scan — single pass to find max/min, count, or accumulate
Two-pass — first pass collects info, second pass builds result
In-place swap — rearrange elements without extra space using index swaps
Prefix computation — running sum/product as you iterate

Common Mistakes

Off-by-one errors: Array of length n has valid indices 0 to n-1, not 1 to n
Modifying while iterating: Adding/removing elements during a loop causes skipped elements or infinite loops — iterate over a copy or use indices carefully
Forgetting empty array check: Operations like arr[0] or Math.max(...arr) fail on empty arrays
Confusing slice vs. splice: In JavaScript, slice copies, splice mutates. Similar distinctions exist in other languages
Not considering negative numbers: Algorithms that assume positive values (like using array indices as markers) break with negatives

When to Use

Find the maximum, minimum, or sum of elements

Reverse or rotate an array

Remove or move specific elements

Merge two sorted arrays

Find duplicates or missing numbers

Split an array into chunks

Compute running sums or prefix arrays

Flatten nested arrays

Template

1# --- Linear Scan (find max) ---
2def find_max(arr):
3    result = arr[0]
4    for num in arr:
5        result = max(result, num)
6    return result
7
8# --- Build Result Array ---
9def transform(arr):
10    result = []
11    for num in arr:
12        result.append(num * 2)
13    return result
14
15# --- In-Place Swap ---
16def swap(arr, i, j):
17    arr[i], arr[j] = arr[j], arr[i]
18
19# --- Two-Pointer Technique ---
20def reverse_in_place(arr):
21    left, right = 0, len(arr) - 1
22    while left < right:
23        arr[left], arr[right] = arr[right], arr[left]
24        left += 1
25        right -= 1
26    return arr

{ }

Syntax Reference

1# === Creation ===
2arr = []                      # empty list
3arr = [1, 2, 3]              # literal
4arr = [0] * n                # n zeros
5arr = list(range(1, 6))      # [1, 2, 3, 4, 5]
6
7# === Access ===
8arr[0]                       # first element
9arr[-1]                      # last element
10len(arr)                     # length
11arr[1:4]                     # slice [1, 2, 3] (end exclusive)
12
13# === Add / Remove ===
14arr.append(x)                # add to end: O(1)
15arr.insert(i, x)             # insert at index: O(n)
16arr.pop()                    # remove last: O(1)
17arr.pop(i)                   # remove at index: O(n)
18arr.remove(x)                # remove first occurrence: O(n)
19
20# === Search ===
21x in arr                     # contains: O(n)
22arr.index(x)                 # index of first x (ValueError if missing)
23arr.count(x)                 # count occurrences
24
25# === Transform ===
26arr.reverse()                # reverse in place
27arr[::-1]                    # reversed copy
28arr.sort()                   # sort in place
29sorted(arr)                  # sorted copy
30arr.extend(other)            # append all from other
31
32# === Functional ===
33list(map(fn, arr))           # map
34list(filter(fn, arr))        # filter
35sum(arr)                     # sum
36min(arr), max(arr)           # min, max

📋

Common Recipes

1# --- Find Max and Min ---
2def find_max_min(arr):
3    return [max(arr), min(arr)]
4
5# --- Reverse In Place ---
6def reverse_array(arr):
7    left, right = 0, len(arr) - 1
8    while left < right:
9        arr[left], arr[right] = arr[right], arr[left]
10        left += 1
11        right -= 1
12    return arr
13
14# --- Move Zeros to End ---
15def move_zeros(arr):
16    write = 0
17    for read in range(len(arr)):
18        if arr[read] != 0:
19            arr[write], arr[read] = arr[read], arr[write]
20            write += 1
21    return arr
22
23# --- Running Sum ---
24def running_sum(arr):
25    result = []
26    total = 0
27    for num in arr:
28        total += num
29        result.append(total)
30    return result
31
32# --- Merge Two Sorted Arrays ---
33def merge_sorted(a, b):
34    result = []
35    i = j = 0
36    while i < len(a) and j < len(b):
37        if a[i] <= b[j]:
38            result.append(a[i]); i += 1
39        else:
40            result.append(b[j]); j += 1
41    result.extend(a[i:])
42    result.extend(b[j:])
43    return result

O(n)

Complexity

Operation	Time	Notes
Access by index	O(1)	Direct memory offset
Push / Append	O(1)*	Amortized — occasional resize
Pop (end)	O(1)	Remove last element
Insert (middle)	O(n)	Must shift elements right
Delete (middle)	O(n)	Must shift elements left
Search (unsorted)	O(n)	Linear scan
Search (sorted)	O(log n)	Binary search
Sort	O(n log n)	Built-in sort algorithms

Watch Out

✗Off-by-one errors: Array of length n has valid indices 0 to n-1, not 1 to n
✗Modifying while iterating: Adding/removing elements during a loop causes skipped elements or infinite loops — iterate over a copy or use indices carefully
✗Forgetting empty array check: Operations like `arr[0]` or `Math.max(...arr)` fail on empty arrays
✗Confusing slice vs. splice: In JavaScript, `slice` copies, `splice` mutates. Similar distinctions exist in other languages
✗Not considering negative numbers: Algorithms that assume positive values (like using array indices as markers) break with negatives

PRACTICE PROBLEMS

String Manipulation

Number & Math