Phase 2: Linear Data Structures

In Phase 1 you learned to make Python do things: store values, make decisions, repeat work and package it into functions. In this phase you learn how to organise data so that the work becomes easy. Almost every interview problem starts with a question hiding underneath the story: "which container makes this operation cheap?" A list makes indexing cheap. A set makes "have I seen this?" cheap. A stack makes "what did I open most recently?" cheap. A queue makes "who has waited longest?" cheap. A linked list makes "splice this in" cheap.

By the end of this phase you will be able to pick the right container for a problem, explain roughly how fast each of its operations is, and solve the standard easy problems on arrays, strings, hash maps, stacks, queues, linked lists and matrices. The problems are ordered from easiest to hardest, and every section below ends with the ones that practise it.

Lists and arrays

A Python list is what other languages call a dynamic array: the elements sit next to each other in memory, and the list keeps track of how many there are. That layout decides what is fast and what is slow.

The "O(...)" notation is Big-O: a rough count of how the work grows with the input size n. O(1) means "the same no matter how big the list is"; O(n) means "proportional to the size"; O(n²) means "a loop inside a loop", which is fine for 100 elements and hopeless for a million. You do not need to prove anything formally in this phase, but you should be able to look at a loop and say which of these it is.

Most easy array problems are a single pass with a little memory. You walk the list once and carry a few variables that summarise what you have seen so far:

def largest_and_sum(nums):
    best = None
    total = 0
    for x in nums:
        total += x
        if best is None or x > best:
            best = x
    return best, total

print(largest_and_sum([3, 1, 4, 1, 5]))

Output:

(5, 14)

Notice the best is None check. Starting best at 0 would be wrong for a list of negative numbers; starting it at nums[0] crashes on an empty list. Using None as "nothing seen yet" handles both.

Changing a list in place

Some problems ask you to rearrange a list in place, which means changing the list you were given rather than building a new one. The standard tool is the read/write (or slow/fast) pattern: one index reads every element, another index marks where the next kept element should go.

def keep_evens(nums):
    write = 0
    for read in range(len(nums)):
        if nums[read] % 2 == 0:
            nums[write] = nums[read]
            write += 1
    return write          # the first `write` slots hold the evens

data = [1, 2, 3, 4, 6, 7]
k = keep_evens(data)
print(k, data[:k])

Output:

3 [2, 4, 6]

Returning the count and leaving junk after it looks odd at first, but it is exactly how "remove element" style problems are specified, and it avoids the O(n) cost of deleting from the middle.

Common mistakes

• Deleting elements from a list while looping over it with for x in nums. Elements get skipped. Loop over a copy, loop by index backwards, or use the read/write pattern.
• Confusing nums.sort() (sorts in place, returns None) with sorted(nums) (returns a new list). x = nums.sort() leaves x as None.
• Writing if best == None or starting a running maximum at 0.

Practice: Second Largest Number, Move Zeroes, Remove Element

Strings and immutability

A string behaves like a list of characters for reading: s[i], s[1:4], len(s) and for c in s all work. The big difference is that a string is immutable. You cannot write s[0] = 'x'; every string method returns a new string and leaves the old one alone.

s = "hello"
t = s.upper()
print(s, t)
print(s[::-1])            # slicing with step -1 reverses

Output:

hello HELLO
olleh

Because strings cannot be changed, the usual pattern is: pull the string apart into a list, work on the list, then glue it back together with join.

sentence = "  the   quick  brown fox "
words = sentence.split()          # no argument: split on any whitespace, drop empties
print(words)
print("-".join(words))

Output:

['the', 'quick', 'brown', 'fox']
the-quick-brown-fox

A handful of methods answer most string questions: c.isalnum(), c.isdigit(), c.isalpha(), s.lower(), s.strip(), s.split(), sep.join(parts), s.count(x), s.find(x). When you need to filter characters, a list comprehension is the cleanest tool:

raw = "A man, a plan!"
cleaned = "".join(c.lower() for c in raw if c.isalnum())
print(cleaned)

Output:

amanaplan

Common mistakes

• Building a string with result += c inside a loop over thousands of characters. Each += copies the whole string, so the loop is O(n²). Collect pieces in a list and join once.
• s.split(" ") versus s.split(). With an explicit space, "a b".split(" ") gives ['a', '', 'b']; with no argument you get ['a', 'b'].
• Forgetting that comparisons are case-sensitive: 'A' == 'a' is False.

Practice: Reverse Words in a String, Valid Palindrome

Hash maps and sets

A hash map (Python dict) stores key/value pairs and finds a key in O(1) on average, regardless of how many pairs it holds. A set is a dict without values: it stores keys only and answers x in s in O(1). These are the two most important tools for turning an O(n²) nested loop into an O(n) single pass, because they let you remember what you have seen instead of searching for it again.

seen = set()
for x in [4, 7, 4, 9]:
    if x in seen:
        print("duplicate:", x)
    seen.add(x)

Output:

duplicate: 4

Compare that with the nested-loop version, which checks every pair: for 10,000 numbers that is 50 million comparisons instead of 10,000 set lookups.

Dictionaries are the natural way to count things. counts.get(key, 0) returns 0 when the key is missing, which avoids a KeyError:

counts = {}
for c in "banana":
    counts[c] = counts.get(c, 0) + 1
print(counts)

from collections import Counter
print(Counter("banana"))
print(Counter("banana") == Counter("nabana"))

Output:

{'b': 1, 'a': 3, 'n': 2}
Counter({'a': 3, 'n': 2, 'b': 1})
True

Counter and defaultdict from the collections module are already imported for you in every problem on this site.

The other classic use is mapping a value to where you saw it. "Find two numbers that add up to target" becomes "for each number, is target - x in my dictionary of earlier numbers?" That single reframing turns a pair search into one pass.

Keys must be hashable: numbers, strings and tuples are fine; lists are not. If you need a pair of values as a key, use a tuple (r, c) rather than a list [r, c].

Common mistakes

• Using a list where a set would do: if x in some_list inside a loop is a hidden O(n²).
• counts[c] += 1 without a default; use counts.get(c, 0) + 1, a defaultdict(int) or a Counter.
• Inserting into the dictionary before checking it in Two Sum style problems, which lets an element pair with itself.

Practice: Contains Duplicate, Valid Anagram, Two Sum

Stacks

A stack is a container you can only touch at one end, the top. You push onto the top and pop from the top, so the last thing in is the first thing out (LIFO). Python has no separate stack class because a list already is one: append pushes, pop() pops, stack[-1] peeks, and not stack tests for empty. All four are O(1).

stack = []
stack.append("a")
stack.append("b")
stack.append("c")
print(stack[-1])      # peek
print(stack.pop())    # remove and return the top
print(stack)

Output:

c
c
['a', 'b']

Reach for a stack whenever the problem involves nesting or "the most recent unfinished thing": matching brackets, undo history, evaluating expressions, or tracking function calls. Brackets are the canonical example. Push every opener; when a closer arrives, the top of the stack must be its matching opener, otherwise the string is invalid. At the end the stack must be empty.

pairs = {')': '(', ']': '[', '}': '{'}
stack = []
for c in "{[()]}":
    if c in pairs:
        print("closer", c, "matches top", stack.pop())
    else:
        stack.append(c)
print("leftover:", stack)

Output:

closer ) matches top (
closer ] matches top [
closer } matches top {
leftover: []

Stacks also evaluate postfix (Reverse Polish) expressions: push numbers, and when an operator appears pop two operands, apply it, push the result. Note that the first value popped is the right-hand operand.

Finally, a stack can carry extra information alongside each element. If every push also records "the minimum so far", the minimum of the whole stack is always sitting on top of that second list, so a get_min query is O(1) instead of scanning.

Common mistakes

• Popping from an empty list raises IndexError. Check if not stack before popping when the input might be unbalanced.
• Using stack.pop(0); that is the front, costs O(n), and makes your "stack" a queue.
• Forgetting the final check: "((" has no mismatches but is still invalid because openers are left over.
• In RPN, computing b - a instead of a - b, and using // where the problem wants truncation toward zero (int(a / b)).

Practice: Valid Parentheses, Evaluate Reverse Polish Notation, Min Stack

Queues

A queue is first-in, first-out (FIFO): elements leave in the order they arrived. Think of a line at a shop, print jobs, or tasks waiting for a worker. The two operations are enqueue (add at the back) and dequeue (remove from the front).

You could use a list, but list.pop(0) shifts every remaining element and costs O(n). The right tool is collections.deque (a "double-ended queue"), which appends and pops from both ends in O(1). It is imported for you on this site.

from collections import deque

q = deque()
q.append("alice")     # enqueue
q.append("bob")
q.append("carol")
print(q[0])           # peek at the front
print(q.popleft())    # dequeue
print(q)

Output:

alice
alice
deque(['bob', 'carol'])

deque also has appendleft and pop, so it doubles as a stack. You will use it constantly in Phase 4 and 5 for breadth-first search, so get comfortable with it now.

A queue can also be built out of two stacks, which is a favourite interview question because it tests whether you really understand both orders. Pushes go onto an inbox stack. When you need the front, and the outbox stack is empty, pour the inbox into the outbox: popping from one and pushing onto the other reverses the order, so the oldest element ends up on top. Each element is moved at most once, so the cost is O(1) on average.

inbox, outbox = [], []
for x in (1, 2, 3):
    inbox.append(x)
while inbox:
    outbox.append(inbox.pop())
print(outbox)          # top of the outbox (last item) is the queue's front
print(outbox.pop())

Output:

[3, 2, 1]
1

Common mistakes

• Refilling the outbox while it still has elements. That interleaves old and new items and breaks the order. Only pour when the outbox is empty.
• list.pop(0) in a loop; use deque.popleft().
• Returning len(x) == 0 from empty() is fine, but returning 0/1 or None is not: the tests expect real booleans.

Practice: Implement Queue using Stacks

Linked lists

A linked list is a chain of small objects called nodes. Each node stores a value and a reference to the next node; the last node points to None. The list is known only by its first node, the head. On this site every linked-list problem uses this class, which is defined for you:

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

Because there is no index, everything is a traversal: start at the head and follow .next until you hit None.

head = ListNode(1, ListNode(2, ListNode(3)))

node = head
while node is not None:
    print(node.val, end=" -> ")
    node = node.next
print("None")

Output:

1 -> 2 -> 3 -> None

Why bother, when a Python list does all this and more? Because linked lists make splicing O(1): inserting or removing a node anywhere is one or two pointer changes, with no shifting. That is why merging two sorted lists, or reversing a list, can be done by re-linking the existing nodes without allocating anything new.

The site's helpers

Typing out nested ListNode(...) calls is tedious, so the test harness gives you two converters, available in your code and in the tests:

head = list_to_linked([1, 2, 3])     # ListNode chain 1 -> 2 -> 3
print(linked_to_list(head))          # back to a Python list
print(list_to_linked([]))            # an empty list is just None

Output:

[1, 2, 3]
None

A test such as linked_to_list(reverse_list(list_to_linked([1, 2, 3]))) builds the chain, hands you its head, and turns whatever node you return back into a list for comparison. Remember that an empty list is represented by None, so your functions must cope with head being None.

Two patterns that solve most easy problems

Previous/current re-linking. To reverse a list, walk it with current while carrying prev. At each node, save current.next first, then point current.next back at prev, then advance both. If you flip the pointer before saving the next node, the rest of the list is gone.

def reverse(head):
    prev = None
    current = head
    while current:
        nxt = current.next
        current.next = prev
        prev = current
        current = nxt
    return prev

print(linked_to_list(reverse(list_to_linked([1, 2, 3]))))

Output:

[3, 2, 1]

Fast and slow pointers. Move slow one step and fast two steps per iteration. When fast runs off the end, slow is in the middle. The same idea (with a different stopping condition) later detects cycles.

Dummy head. When building a result list, start with a throwaway dummy = ListNode() and a tail pointer. Attach nodes to tail.next, advance tail, and return dummy.next at the end. This removes the special case of "is this the first node?".

Common mistakes

• AttributeError: 'NoneType' object has no attribute 'next': you followed .next past the end. Check while node and node.next when you look two steps ahead.
• Losing the rest of the list by overwriting .next before saving it.
• Returning head after reversing. The old head is now the tail; return prev.
• Building a Python list of the values and returning it. The tests expect a ListNode, and the problem is asking you to re-link nodes.

Practice: Reverse Linked List, Middle of the Linked List, Merge Two Sorted Lists

2D lists and matrices

A matrix (grid, board, image) is a list of lists. mat[r] is row r, and mat[r][c] is the cell in row r, column c. Rows are counted from the top, columns from the left, both starting at 0. The number of rows is len(mat) and the number of columns is len(mat[0]).

mat = [[1, 2, 3],
       [4, 5, 6],
       [7, 8, 9]]

print(mat[1][2])                              # row 1, column 2
print([sum(row) for row in mat])              # row sums
print([sum(mat[r][c] for r in range(3)) for c in range(3)])   # column sums

Output:

6
[6, 15, 24]
[12, 15, 18]

The standard traversal is two nested loops, and the standard trick is to notice patterns in the indices. On the main diagonal the row equals the column, mat[i][i]. On the anti-diagonal the column is n - 1 - i. The transpose swaps the two indices: transposed[c][r] = mat[r][c].

n = len(mat)
print([mat[i][i] for i in range(n)])
print([mat[i][n - 1 - i] for i in range(n)])
print([[mat[r][c] for r in range(n)] for c in range(n)])   # transpose

Output:

[1, 5, 9]
[3, 5, 7]
[[1, 4, 7], [2, 5, 8], [3, 6, 9]]

Common mistakes

• Creating a grid with [[0] * n] * n. That makes n references to the same row, so changing one cell changes the whole column. Use [[0] * n for _ in range(n)].
• Mixing up mat[r][c] and mat[c][r]; the first index is always the row.
• Counting the centre cell twice when a problem combines both diagonals of an odd-sized matrix.

Practice: Matrix Diagonal Sum

Checklist

Before moving on to Phase 3, make sure you can:

• Say whether a list operation is O(1) or O(n), and explain why insert(0, x) is slow.
• Solve a "single pass with a running value" problem, including empty input and negative numbers.
• Rearrange a list in place with a read index and a write index, and return a count of kept elements.
• Explain why strings are immutable and build a new string with split, a comprehension and join.
• Filter a string to alphanumeric characters and check it from both ends with two indices.
• Use a set to detect repeats and a dict or Counter to count occurrences.
• Reframe "find a pair" as "look up the partner in a dictionary" and avoid pairing an element with itself.
• Use a list as a stack (append, pop, [-1]) to match brackets and evaluate postfix expressions.
• Write a class whose methods share state through self, and keep auxiliary data so a query is O(1).
• Use collections.deque as a queue and explain how two stacks simulate one.
• Traverse a ListNode chain, reverse it with prev/current pointers, find its middle with fast/slow pointers and merge two sorted chains with a dummy head.
• Index a matrix with mat[r][c], compute row/column/diagonal sums and build a transpose.