Arrays, strings and hashing

Arrays and dynamic arrays

Also called list, ArrayList, vector, resizable array, dynamic array

What

An array stores items side by side in memory, so reading or writing index i is O(1). A dynamic array grows by allocating a bigger block and copying, so appending is O(1) amortised, while inserting or removing in the middle is O(n).

Why

It is the default container for sequences and the backing store for strings, stacks and heaps. Its contiguous layout also makes it fast in practice thanks to the CPU cache.

nums = [3, 1, 4]
nums.append(1)       # amortised O(1)
nums[0] = 9          # O(1)
nums.insert(0, 2)    # O(n): shifts every item
nums.pop()           # O(1) at the end
nums.pop(0)          # O(n) at the front

Strings

What

A string is a sequence of characters. In Python, Java and JavaScript strings are immutable, so every change builds a new string; C++ std::string is mutable. Taking a substring or slice copies it, costing O(k) for k characters.

Why

String problems are array problems with extra costs hidden in concatenation, slicing and comparison, and those costs decide whether a solution is O(n) or O(n^2).

parts = []
for word in words:
    parts.append(word.upper())
result = ' '.join(parts)     # O(total length)
chars = list(s)              # mutable copy
chars[0] = 'X'
s2 = ''.join(chars)

Hash maps

Also called hash table, dictionary, dict, HashMap, unordered_map, Map

What

A hash map stores key-value pairs in buckets chosen by a hash of the key, giving O(1) average insert, lookup and delete. Collisions are handled by chaining or probing, and the table resizes as it fills.

Why

It is the first tool for counting, grouping, caching and checking whether you have seen something before in one pass, often turning an O(n^2) search into O(n).

from collections import Counter, defaultdict

counts = Counter(words)          # O(n)
counts['apple'] += 1
top3 = counts.most_common(3)
by_len: defaultdict[int, list[str]] = defaultdict(list)
for w in words:
    by_len[len(w)].append(w)

Hash sets

Also called set, HashSet, unordered_set, Set

What

A hash set stores unique keys without values, with O(1) average add, remove and membership check.

Why

Use it for de-duplication, visited markers and membership checks. Checking membership in a list is O(n); in a set it is O(1) on average.

def has_duplicate(nums: list[int]) -> bool:
    seen = set()
    for x in nums:
        if x in seen:
            return True
        seen.add(x)
    return False

Composite and custom keys

Also called tuple key, pair key, composite key

What

When a key is made of several values, like a grid cell or a sorted word, it must be hashable and compare by value. Each language has a safe choice: tuples, records, packed integers or joined strings.

Why

Visited sets on grids and grouping anagrams depend on it, and a wrong key type fails silently by never matching.

visited: set[tuple[int, int]] = set()
visited.add((r, c))               # tuples are hashable
groups: dict[str, list[str]] = {}
key = ''.join(sorted(word))
groups.setdefault(key, []).append(word)

Prefix sums

Also called cumulative sum, running total

What

A prefix sum array stores running totals, so prefix[i] is the sum of the first i items. The sum of any range i..j is prefix[j + 1] - prefix[i]: O(1) per query after an O(n) build.

Why

It answers many range-sum queries fast, and combined with a hash map of earlier prefix values it counts subarrays with a given sum in O(n), even with negative numbers.

from itertools import accumulate

prefix = [0, *accumulate(nums)]  # prefix[i] = sum(nums[:i])

def range_sum(i: int, j: int) -> int:  # nums[i..j] inclusive
    return prefix[j + 1] - prefix[i]

Integer limits and overflow

Also called overflow, MAX_SAFE_INTEGER, INT_MAX, integer overflow

What

Java and C++ int holds up to about 2.1 billion (2^31 - 1); past that Java wraps around and C++ has undefined behaviour. JavaScript numbers are exact integers only up to 2^53 - 1. Python integers grow without limit.

Why

Sums, products and midpoints of large values overflow quietly and give wrong answers with no error, a common cause of failing hidden tests.

big = 2**64 + 1        # never overflows, just gets slower
mid = (lo + hi) // 2   # safe in Python
q = -7 // 2            # -4: floor division
r = -7 % 2             # 1: takes the sign of the divisor
t = int(-7 / 2)        # -3: truncates toward zero

Python built-in collections

Also called collections module, deque, heapq, bisect

What

list is a dynamic array, dict and set are hash tables (a dict keeps insertion order), collections.deque gives O(1) at both ends, heapq turns a list into a min-heap and bisect binary searches a sorted list.

Why

Matching each structure to its built-in keeps Python solutions short and fast enough. There is no built-in balanced tree, so sorted order comes from sorting, bisect or a heap.

from collections import defaultdict, deque
import bisect
import heapq

stack = [1, 2]
stack.pop()                      # O(1) at the end
queue = deque([1, 2])
queue.popleft()                  # O(1); list.pop(0) is O(n)
graph: defaultdict[int, list[int]] = defaultdict(list)
heap: list[int] = []
heapq.heappush(heap, 3)          # min-heap, O(log n)
i = bisect.bisect_left(sorted_nums, 3)