S023 · Arrays & Strings — Indexing, Slicing, Two-Pointer

Module M03: Data Structures & Algorithms · Session 23 of 130 · Track: SW 🧵

What you'll be able to do after this session

• Explain Arrays & Strings to a friend in one minute, out loud, no notes.
• Recognise it when you see it in real code / systems / papers.
• Complete the hands-on exercise at the end without looking up help.

Prerequisites

If you can't answer these in 30 seconds each, redo the linked session first:

• S015 — Big-O Notation — Reasoning About Scale

Pre-read (skim before the session)

• 🎥 Intuition (5–15 min) · Arrays vs Linked Lists — the fundamental trade-off (NeetCode) — memory layout matters.
• 🎥 Deep dive (30–60 min) · Two Pointer Technique — full walkthrough (NeetCode) — the pattern behind half of the "easy" interview questions.
• 🎥 Hands-on demo (10–20 min) · Python lists: not what you think they are (mCoding) — how CPython actually stores your list.
• 📖 Canonical article · Python docs — Lists tutorial — slicing, indexing, negative indexing.
• 📖 Book chapter / tutorial · Wikipedia — Array (data structure) — the concept, cross-language.
• 📖 Engineering blog · Facebook Engineering — Data Infrastructure category — see how arrays underpin real storage engines.

(a) Intuition · 5 min

The one-paragraph mental model. Why this concept exists, what problem it solves, and the analogy that makes it stick.

In one sentence: The workhorse data structure.

An array is a row of numbered mailboxes standing shoulder to shoulder in memory. The magic property: because every mailbox is the same size and they're glued together, you can find mailbox #7 instantly — the address is just start + 7 * size. No searching, no traversing. That's what "O(1) random access" means, and it's the single biggest reason arrays are the foundation of almost every other data structure.

A string is just an array of characters (sometimes with slightly fancier bookkeeping for Unicode). Indexing, slicing, reversing — same rules as arrays.

Two-pointer is the technique that turns many "quadratic" problems into "linear" ones. Instead of a nested loop scanning every pair, you keep two indices and move them cleverly — sometimes both forward, sometimes one from each end. If you spot a problem where the input is sorted, or you need to compare/pair elements, two-pointer is usually the first thing to try.

One-sentence gotcha to carry forever: Python lists are not contiguous arrays of ints — they're arrays of pointers to PyObjects. That's why they're slower than NumPy arrays for numeric work and why appending is amortised O(1) rather than truly O(1). If you write arr[i] in Python you touch two memory locations; in C or NumPy you touch one.

(b) Visual walkthrough · 15 min

Diagrams, worked examples, step-by-step visuals.

Memory layout — the whole reason arrays win:

One arithmetic step, one memory read. No matter if the array has 5 elements or 5 billion.

Worked example 1 — Two-Sum in a sorted array (two pointer):

Given [1, 3, 4, 5, 7, 11], find two numbers that sum to 9.

We looked at each element at most once → O(n). Naive nested loop would be O(n²).

Worked example 2 — reverse a string in place:

Given ['h','e','l','l','o']. Two pointers at ends, swap, march inward:

Stop when left ≥ right. Total swaps = n/2, so O(n) time, O(1) extra space.

Slicing gotcha table:

(c) Hands-on · 20 min

Code you type and run. Not pseudo-code — real, runnable, copy-pasteable.

# arrays_strings_playground.py
from time import perf_counter
 
# ---- 1. Random access is O(1) regardless of size ----
small = list(range(1_000))
big = list(range(10_000_000))
t0 = perf_counter(); _ = small[500];        t1 = perf_counter()
t2 = perf_counter(); _ = big[9_999_999];    t3 = perf_counter()
print(f"access small[500]      : {(t1-t0)*1e9:8.1f} ns")
print(f"access big[9_999_999]  : {(t3-t2)*1e9:8.1f} ns  # same order!")
 
# ---- 2. Two-pointer: two-sum in a sorted array ----
def two_sum_sorted(arr, target):
    left, right = 0, len(arr) - 1
    while left < right:
        s = arr[left] + arr[right]
        if s == target: return (left, right)
        if s < target:  left += 1
        else:           right -= 1
    return None
 
print("
two_sum([1,3,4,5,7,11], 9) =", two_sum_sorted([1,3,4,5,7,11], 9))
 
# ---- 3. Two-pointer: reverse a list in place ----
def reverse_inplace(a):
    left, right = 0, len(a) - 1
    while left < right:
        a[left], a[right] = a[right], a[left]
        left += 1; right -= 1
 
xs = list("hello")
reverse_inplace(xs)
print("reversed:", "".join(xs))
 
# ---- 4. Sliding window: longest substring of unique chars ----
def longest_unique_substring(s):
    seen = {}
    left = best = 0
    for right, ch in enumerate(s):
        if ch in seen and seen[ch] >= left:
            left = seen[ch] + 1
        seen[ch] = right
        best = max(best, right - left + 1)
    return best
 
for s in ["abcabcbb", "bbbbb", "pwwkew", "dvdf"]:
    print(f"longest_unique({s!r}) = {longest_unique_substring(s)}")
 
# ---- 5. The classic gotcha: insert at front is O(n) ----
n = 50_000
t0 = perf_counter()
xs = []
for i in range(n): xs.append(i)          # O(1) amortised
t1 = perf_counter()
xs = []
for i in range(n): xs.insert(0, i)       # O(n)!
t2 = perf_counter()
print(f"
append {n} items : {(t1-t0)*1000:6.1f} ms")
print(f"insert(0) {n}     : {(t2-t1)*1000:6.1f} ms  <-- watch it explode")

Checklist:

1. Random access times are near-identical for tiny and huge lists.
2. two_sum_sorted returns (2, 3).
3. reverse_inplace prints olleh.
4. Sliding-window outputs: 3, 1, 3, 3.
5. insert(0, ...) is roughly 100–1000× slower than append for 50k items.

Try this modification: implement two_sum_sorted but return the actual values instead of indices, and handle the "no pair found" case gracefully. Then rewrite it using nested loops and time both on a list of 10,000 random ints to see the O(n) vs O(n²) gap for yourself.

(d) Production reality · 10 min

How this shows up in real systems, gotchas, war stories, common bugs.

Arrays and strings feel "basic" but production systems live and die on their edge cases. Three recurring stories:

1. The "insert-at-front" performance mystery. A junior engineer prepends events to a Python list to keep the newest first: events.insert(0, evt). Works fine at 100 items; at 100k items the ingest thread is at 90% CPU. The fix is collections.deque (O(1) at both ends) or just append + reverse when reading. This exact anti-pattern has been the root cause of countless "why is our pipeline slow" post-mortems.

2. Unicode strings ≠ arrays of bytes. Emoji, combining accents, and grapheme clusters mean that s[3] in Python gives a code point, not necessarily "the fourth thing a human would count." Netflix, Slack, and Twitter have all had incidents where a truncation by "N characters" cut through a multi-byte character and produced invalid UTF-8, crashing downstream parsers. Rule: for user-visible truncation use a proper grapheme library; for byte-length budgets, encode first and count bytes.

3. Off-by-one in slicing. Python's arr[i:j] is exclusive of j, but C-style APIs (Kafka offsets, S3 range headers, database LIMIT/OFFSET) mix conventions freely. Confluent's Kafka consumer bugs list is full of "why did we skip the last message" stories rooted in exactly this. The habit to build: whenever you write a slice, say out loud whether the endpoint is inclusive or exclusive.

Perf angle: cache locality. A sequential scan over a list of Python ints is much slower than the same scan over a NumPy array or a Pandas column, because Python objects are scattered across the heap while NumPy stores raw bytes contiguously. High-throughput services (search ranking, feature stores, real-time bidding) push everything hot into contiguous columnar layouts (Arrow, Parquet, Velox) for this reason. The mental model: the CPU doesn't slow down when your data grows — it slows down when your data stops fitting in cache.

(e) Quiz + exercise · 10 min

1. Why is arr[i] O(1) but x in arr O(n)?
2. When would you reach for collections.deque instead of list?
3. Explain the two-pointer technique in one sentence, and give one problem it solves cleanly.
4. What is the time complexity of arr[a:b] in Python, and why?
5. Give one real-world bug that comes from treating a Unicode string like a byte array.

Stretch (connects to S015 — Big-O): For each of these operations on a Python list of length n, state the amortised time complexity: append, pop(), pop(0), insert(0, x), x in list, list[i], list[i:j], list.sort(). Which two would you refuse to use in a hot loop?

Explain-out-loud test

If you can't teach these 3 things to a friend without notes, redo the session:

1. What is Arrays & Strings? (one sentence, no jargon)
2. When would you use it? (one concrete example)
3. When would you NOT use it? (one anti-pattern)

What comes next

• Next session (S024): Hashmaps & Sets — Hash Functions, Collisions
• Previous (S022): Statistics — CLT, Hypothesis Testing, Confidence Intervals
• Hub: The 6-Month Learning Plan

Part of a 130-session evergreen learning series. Session structure: (a) intuition · (b) visual walkthrough · (c) hands-on · (d) production reality · (e) quiz + exercise. Duration: 60 minutes.