Arrays, hash maps, and prefix sums from the inside

1How do we compare the cost of two pieces of code?

Every prerequisite on this page exists to make some operation cheaper, so we first need a way to measure cost. Timing a program with a stopwatch gives a number that changes with the machine. Counting the steps gives a number that depends only on the code and the size of the input.

Here are two functions that answer two different questions about a list of names. Read them and count the comparisons, where n is the number of names.

def contains(names, target):
    for name in names:              # runs at most n times
        if name == target:          # 1 comparison per pass
            return True
    return False

def has_repeat(names):
    for i in range(len(names)):             # n passes
        for j in range(i + 1, len(names)):  # fewer passes each time
            if names[i] == names[j]:        # 1 comparison per inner pass
                return True
    return False

When the target is absent, contains does n comparisons. In the worst case, has_repeat compares each pair of names once. With 6 names, the inner loop runs 5, then 4, 3, 2, 1, and 0 times, so the count is 6 × 5 / 2 = 15. In general, the count is n(n − 1) / 2, which is about n²/2.

Big-O notation keeps only how the count grows when n grows. It drops constant factors, because they depend on the details of each step, and it drops smaller terms, because the largest term dominates at large n. So contains is O(n), has_repeat is O(n²), and a fixed number of steps for any input is O(1).

The last row shows why this difference matters in interview problems. Take a computer that does about a billion simple steps per second. It finishes the O(n) column in about a millisecond, and it needs several minutes for the O(n²) column. The billion is a rough scale and not a measurement.

Big-O has a limit. It leaves out the constant factors, so an O(1) step can be slower than a short O(n) scan. For a list of five names, the cost difference does not matter. Memory is counted in the same way, as space. If a function builds a second list of n items, it uses O(n) extra space.

Count the steps of a loop

1. Count the passes. A loop over n items makes n passes.
2. Count the work per pass. A comparison is one step, and a call to a function has the cost of that function.
3. Combine. Multiply for a loop inside a loop. Add for loops that run one after the other.

2Why can an array read any position in one step?

Computer memory is a long row of numbered bytes, and each number is called an address. An array reserves a block of neighboring slots in that row, and every slot has the same size. The block is static when its number of slots cannot change after it is created.

Because the slots are neighbors of equal size, the address of any slot can be calculated. If the block starts at address 1000 and each slot takes 8 bytes, index 3 is at 1000 + 3 × 8 = 1024. That is one multiplication and one addition, whether the array has ten slots or ten million. So reading or writing by index is O(1). This calculation is also why indices start at 0: index 0 is zero slots after the start.

Python's list stores references to objects in such a block. A reference is a number that says where an object sits in memory. The objects can have different sizes, but every reference has the same size, which is 8 bytes on a 64-bit build. That is how a list can hold mixed values and still read any position in one step.

Find a slot's address

1. Find the distance. Multiply the index by the slot size.
2. Add the start. Add the distance to the start address.

Inserting in the middle moves values

The address calculation only works if the values stay in consecutive slots with no gaps. That rule has a cost. To insert 15 at index 1 of [10, 20, 30, 40], the values at index 1 and later must first move one slot to the right.

Inserting at index i of an array with n values moves n − i values. Inserting at index 0 moves all of them, so it is O(n), and inserting at the end moves none. Removal works in the same way in the other direction. After removing index i, the n − i − 1 values after it move left to close the gap.

Count the shifted values

1. Find the values at or after the position. For an insert at index 1 of 4 values, these are indices 1, 2, and 3.
2. Count them. That gives 3 moves, which is 4 − 1.

3How can an array grow if its block cannot?

We want to call append without deciding the size in advance. A static array prevents this, because the memory right after the block may belong to something else, so the block cannot extend in place. The only way to get more slots is to allocate a new, larger block and copy the values across. The question is how much larger the new block should be, because that choice sets the cost of the copies.

A dynamic array keeps two numbers that a beginner can easily mix up. length is how many values you stored, and it is what len() reports. capacity is how many slots exist. The difference between them is free room, so most pushes only write one value. Here is the core of the lesson's class. A class bundles data with the functions that use it, and self means the object itself, so self.length is that object's length. A list stands in for the fixed block of slots. Section 8 shows the full class, with notes on each line and a panel on classes.

    def push_back(self, value):
        block_is_full = self.length == self.capacity
        if block_is_full:
            self._resize()
        self.slots[self.length] = value
        self.length += 1

    def _resize(self):
        self.capacity *= 2
        bigger_slots = [None] * self.capacity
        for index in range(self.length):
            bigger_slots[index] = self.slots[index]
            self.copies += 1
        self.slots = bigger_slots

Track length and capacity

1. Check for room. A push finds the block full when length equals capacity.
2. Double if needed. From capacity 2, the capacities are 2, 4, 8, 16.
3. Write the value. Length grows by 1 on every push, and capacity changes only in step 2.

Why doubling makes append cheap on average

One push can copy the whole array, so the worst single push is O(n). That sounds bad until you count the whole sequence. In Fig. 3.1, 9 pushes caused resizes that copied 2, 4, and 8 values, which gives 2 + 4 + 8 = 14 copies in total.

Here is the general argument. Let c be the number of values copied by the last resize. Because the array was full at that moment, c is less than n. The resize before it copied c/2, the one before that c/4, and so on. These halves add to less than 2c, so the total is less than 2n copies. Add the n writes, and n pushes cost fewer than 3n steps. So the average cost per push stays below a constant, however long the array gets.

This kind of average has its own name. Amortized cost is the total cost of a sequence of operations divided by the number of operations. It is a guarantee about the sequence and involves no chance. That is what append is amortized O(1) means: one append can be slow, but a long run of appends cannot be slow on average.

Now compare a rule that looks more careful: add one slot at each resize. It wastes almost no memory, but after capacity 2 every push finds the block full. So 9 pushes copy 2 + 3 + 4 + 5 + 6 + 7 + 8 = 35 values, and n pushes copy about n²/2 values.

Doubling has a cost too: right after a resize, nearly half of the slots are empty, so a dynamic array can use about twice the memory of its values. A resize also needs the old and the new block at the same moment.

Add up the copies

1. List the resizes. Find each push that finds the block full, and note how many values it copies.
2. Add them. Compare the total with 2n.

What Python's real list does

Python's list uses the same mechanism with a smaller growth factor. CPython's source computes the new capacity as about n + n/8 + 6, rounded down to a multiple of 4, so it grows by about 12.5% and not 100%. Any constant growth factor above 1 keeps append amortized O(1). A larger factor copies less often, and a smaller factor wastes less memory. You can measure the real capacities:

import sys

values = []
empty_size = sys.getsizeof(values)
capacity = 0
for number in range(30):
    values.append(number)
    now = (sys.getsizeof(values) - empty_size) // 8
    if now != capacity:
        print(f"length {len(values)}: capacity {now}")
        capacity = now

length 1: capacity 4
length 5: capacity 8
length 9: capacity 16
length 17: capacity 24
length 25: capacity 32

The first table lists the costs that this section explains. The second table measures a real list, and its numbers show the difference that the costs predict.

Median time per pair of calls, on one Windows laptop. Exact values differ by machine, and the growth is what matters.

Predict the cost of list operations

1. Find the cost of one call. Use the table in this section.
2. Multiply by the number of calls. If the cost depends on the current size, add the costs as the size changes.

4What can sets and dictionaries do in one step?

So far, the only way to find a value in an array is to read the values one by one. Python's set and dict answer the question directly, and the table shows the difference on real data. This section treats them as tools, and section 5 opens them up.

Median time per lookup, on the same laptop as the list table in section 3.

The list's time grows with its size, and the set's time stays flat. A set holds unique values, and a dictionary maps each unique key to a value. Both are built on a structure called a hash table, so they have the same costs.

The speed is paid for with memory. A list of 1,000 small integers takes 8 KB for its slots here, and a set of the same integers takes 33 KB, because a hash table keeps many slots empty on purpose. So these patterns usually trade O(n) extra space for a large saving in time.

Almost every use of a hash table in interview problems is one of three patterns. Each pattern starts from a question that you can spot in a problem statement.

Pattern 1: have I seen this before?

The cue is a question about whether a value already appeared. A set answers it in one step, so the whole scan is O(n) and not O(n²). The order of the two lines inside the loop matters: check first, then add.

def first_repeated(items):
    seen = set()
    for item in items:
        if item in seen:
            return item
        seen.add(item)
    return None

1. Check. Ask whether the current item is in the set.
2. Record. If it is absent, add it, and move to the next item.

Pattern 2: how many times?

The cue is a question about frequency. A set cannot answer it, because a set stores only yes or no. A dictionary stores a number for each item. The method d.get(key, default) returns the value for key, or default when the key is absent, so a first sighting counts from 0.

def count_items(items):
    counts = {}
    for item in items:
        counts[item] = counts.get(item, 0) + 1
    return counts

Pattern 3: which items belong together?

The cue is a request to group items that share a property. Choose a key that is equal for items in the same group and different for items in other groups, and store a list of members under each key. When the property has several parts, a tuple such as ("a", 5) combines them into one key. A tuple is written with parentheses and works like a list that cannot change after creation.

def group_by_shape(words):
    groups = {}
    for word in words:
        shape = (word[0], len(word))
        if shape not in groups:
            groups[shape] = []
        groups[shape].append(word)
    return groups

This code uses a tuple and not a list, because a list as a key raises TypeError. The rule is that a key must be hashable: it needs a hash value that never changes during its lifetime. Numbers, strings, and tuples of hashable values qualify. Lists, dictionaries, and sets do not, because they can change. Section 5 shows what would go wrong. Python also treats values that compare equal as one key, so 1 and 1.0 share an entry.

print(len({1: "a", 1.0: "b"}))
print({("a", 5): 1}[("a", 5)])
try:
    {[1, 2]: "x"}
except TypeError as error:
    print("TypeError:", error)

1
1
TypeError: unhashable type: 'list'

Choose keys and structures

1. Ask what a lookup must return. Yes or no needs a set, and a stored value needs a dictionary.
2. Check the key. It must be hashable, and it must be equal exactly when you want two items treated as the same.

5How does a hash table find a key in one step?

We want to read a value by key in O(1). The only O(1) tool we have is an array read by index, and our key is a string, not an index. So we need a function that turns a key into a slot number, and that always gives the same number for the same key. Then a store and a later search both go to the same slot, without a scan.

From a key to a slot

This takes two separate steps. A hash function turns the key into a whole number, called the hash value. The remainder operator % then turns that number into a slot of the current table, because a % b always lies from 0 to b − 1. Every character has a number called its code, which ord() returns, so ord("c") is 99. The lesson uses a simple hash function that adds the codes of a key. For "cat", the sum is 99 + 97 + 116 = 312, and with 8 slots, 312 % 8 = 0.

A good hash function spreads keys evenly across the slots. This teaching function is weak, because addition ignores letter order, so anagrams always get the same slot. That weakness makes collisions easy to see here. Python's real string hash mixes in every character's position.

Turn a key into a slot

1. Hash. Add the character codes: for "dog", 100 + 111 + 103 = 314.
2. Reduce. Take the remainder by the number of slots: 314 % 8 = 2.

When two keys reach the same slot

A collision happens when two different keys reach one slot. Collisions cannot be avoided, because far more possible keys exist than slots. So the table must have a rule that stores both keys and finds each one later. There are two standard rules, and both must compare the actual keys, because equal slots do not mean equal keys.

• Chaining makes each slot hold a list of entries. A colliding key joins the list in its slot.
• Open addressing stores one entry per slot and walks to another slot on a collision. The simplest walk is linear probing: try the next slot, and wrap around at the end of the table.

Python's walk differs from linear probing: it jumps around by a formula that mixes in the whole hash value, which avoids long runs of neighbors. The principle is the same as the one in this lesson. The lesson's probing class is short enough to read in one sitting, and here is its search. DELETED is a marker for a removed entry, which this section explains after the next two practice sets. The word is tests whether two names refer to the same object.

    def get(self, key):
        index = self._hash(key)
        while self.slots[index] is not None:
            slot = self.slots[index]
            slot_holds_key = slot is not DELETED and slot[0] == key
            if slot_holds_key:
                return slot[1]
            index = (index + 1) % self.capacity
        return None

You can run both classes and compare them. The three keys all have the sum 312, so they all start at slot 0:

from dsa_basics.hash_map import ChainedHashMap, HashMap

probing = HashMap(capacity=16)
chained = ChainedHashMap(capacity=16)
for key in ["cat", "act", "tac"]:
    probing.put(key, len(key))
    chained.put(key, len(key))

print([slot[0] for slot in probing.slots if slot is not None])
print(chained.buckets[312 % 16])
print(probing.get("tac"), chained.get("tac"), probing.get("emu"))

['cat', 'act', 'tac']
[['cat', 3], ['act', 3], ['tac', 3]]
3 3 None

Resolve a collision

1. Find the start slot. Hash the key and take the remainder.
2. Apply the rule. With chaining, join the list. With probing, read slots forward until one is free, wrapping with % capacity.

Why the table must grow

The load factor is the number of entries divided by the number of slots. As it rises, collisions become more common and searches get longer. The next figure measures that by simulation. Each slot was chosen at random, which models a good hash function, and each search looks for a key that is absent, which is the longest kind of search.

So the table grows before it gets slow. The lesson's HashMap doubles when half of its slots are used. CPython's dictionary resizes at about two-thirds full. Growing is called rehashing, and it differs from the array's resize in one way: an entry cannot keep its position, because its slot depends on the capacity. "emu" has the hash value 327. With 4 slots, 327 % 4 = 3, but with 8 slots, 327 % 8 = 7, and a later search starts at slot 7. So every entry goes through the store logic again.

A rehash costs O(n), and it happens only after the entries have doubled. That is the argument from section 3 again, so stores are amortized O(1). The O(1) average of a hash table therefore rests on two conditions: the hash function spreads the keys, and resizing keeps the load factor bounded.

When the first condition fails, the average disappears. If all keys collide, each search walks past the others, so it costs O(n). The lesson's weak hash shows this directly. With 500 anagrams of "abcdefg" in a table of 2,048 slots, the load factor is low, and a search still reads 250.5 slots on average. A hash that uses letter order reads 3.23 slots on average with the same keys and table. This worst case can be forced on purpose, so Python salts its string hashes with a random value per process, and hash("cat") changes between runs of the program.

Know when the table grows

1. Compute the load. Divide the used slots by the capacity.
2. Apply the rule. For the lesson's class, double when the load reaches 0.5, and check again after each store.

Why removal needs a marker

Removal looks simple until you follow a later search. A probing search stops at a never-used slot, because a stored key would have been placed there or earlier on its path. So writing None into a removed slot can cut the path of another key. In the first version below, get("act") returns None, even though "act" is still in the table.

The fix leaves a marker, also called a tombstone, which means "used, keep walking". With the marker, get("act") returns 9. A later store may reuse a marker's slot, but only after the walk has shown that the key is not further along the path. Markers lengthen searches as much as live entries do, so the lesson's class counts them in used, and a rehash clears them. Chaining needs no markers, because removing an item from a list breaks no path.

The same path logic explains the hashable rule from section 4. Suppose that a list could be a key, hashed by adding its numbers. The key [1, 2] has the sum 3, so it is stored in slot 3 of an 8-slot table. If the program then appends 4, the sum becomes 7, so a search starts at slot 7 and never finds the entry in slot 3. The entry is lost while still stored. Python prevents this by raising TypeError for a changeable key. For the same reason, two values that compare equal must have equal hashes, or the search for one would start in the wrong place for the other.

Remove without breaking a path

1. Find the key's slot. Walk the same path that a search walks.
2. Write the marker. Lower size, and leave used unchanged.

6How can a range question be answered with one subtraction?

Suppose that an array never changes, and many questions arrive that ask for the sum from position left to position right. Adding the numbers for each question costs O(n) per question, and the additions repeat, because the ranges overlap. The cue is the overlap. Any range can be written as the difference between two ranges that start at position 0, and those can all be computed once.

A prefix sum is a running total: the sum of the numbers from the start up to some position. Store them in an array called prefix, where prefix[i] is the sum of the first i numbers. The first entry is 0, the sum of no numbers. So nums = [2, -1, 3, 5, 1] gives [0, 2, 1, 4, 9, 10], which has one more entry than nums.

class PrefixSum:
    def __init__(self, nums):
        self.prefix = [0]
        for value in nums:
            self.prefix.append(self.prefix[-1] + value)

    def range_sum(self, left, right):
        return self.prefix[right + 1] - self.prefix[left]

To sum positions 1 to 3, take everything up to and including position 3, and remove everything before position 1. That is prefix[4] - prefix[1] = 9 - 2 = 7, and direct addition agrees: −1 + 3 + 5 = 7. Each question costs two reads and one subtraction, so q questions cost O(n + q) in total, compared with up to O(n × q) by re-adding.

The leading 0 is a design choice. Without it, a range that starts at position 0 has nothing to subtract, so the code needs a special case. You will see both versions in solutions. Each is correct, but the shifted version has no if, at the price of the + 1 in the query.

Prefix sums have clear limits. Changing one number makes every later total wrong, so an update costs O(n). When updates and questions alternate, a different structure called a segment tree is the usual choice, and NeetCode teaches it later. The array also costs O(n) extra space. Negative numbers cause no problem, because subtraction does not depend on the totals going up.

Build the running totals

1. Start with 0. That entry is the sum of no numbers.
2. Add each number to the last total. For [3, 1, 4], the array grows as 0, 3, 4, 8.

Answer a range question

1. Read the upper total. prefix[right + 1] includes position right.
2. Read the lower total. prefix[left] stops just before position left.
3. Subtract. Only the range remains.

Running totals from both ends

Some questions ask about everything except the current position. That question has two parts, the numbers before the position and the numbers after it, and each part is a running total. One pass from the left fills left, and one pass from the right fills right. A total that runs from the end is called a postfix total. For [2, -1, 3, 5, 1], position 2 has 1 on its left and 6 on its right.

    for i in range(1, count):
        left[i] = left[i - 1] + nums[i - 1]
    for i in range(count - 2, -1, -1):
        right[i] = right[i + 1] + nums[i + 1]

Note the difference from prefix: here, left[i] leaves out position i, and the array has the same length as the input. The running idea is not limited to sums. It works with any operation that you can apply step by step, such as multiplication, whose "no numbers yet" value is 1 and not 0. Subtraction does not carry over, though. A range product would need division, which fails when a number is 0, and that is one reason why keeping separate left and right totals is useful.

Run totals from both ends

1. Choose the "nothing yet" value. Use 0 for a sum, and 1 for a product.
2. Sweep. Each entry combines the previous entry with the neighbor's number.

Running totals with a dictionary

Now change the question: how many contiguous stretches of the array sum to a target? A plain prefix array does not help directly, because every stretch would have to be tried, which is O(n²). Look at what a stretch's sum is, though. A stretch that ends at the current number has the sum running - earlier, where earlier is a running total from before the stretch. So the sum equals the target exactly when earlier equals running - target. That turns "try every start" into "how many earlier totals had this value?", which is pattern 2 from section 4.

Rectangles in a grid

This last idea is not needed for the nine Arrays & Hashing problems, but NeetCode's lesson on prefix sums suggests a 2D problem, so it is included. The running total becomes a table, where each entry holds the sum of the rectangle from the top-left corner of the grid to that position. The table has an extra row and column of zeros, which play the role of the leading 0.

7Which tool does a problem ask for?

A problem statement rarely names the structure that it needs, so the skill to practice is reading the cue. Each row gives a cue, the tool it suggests, and the case where that tool does not fit.

One problem, several tools

This problem has four parts, and each part uses one skill from an earlier section. Answer them in order.

8Walk through the code, line by line

This section shows the real code of the lesson's dsa_basics package, and traces it with a tiny example for each class. The code window marks each line that ran, and it dims each line that did not. The notes beside the code explain each line for any input first, and an "In our run" box then gives the traced values. A panel titled "Python you need" comes before any code that uses a feature beyond basic Python. Line numbers are the numbers in the package files. Use this section as a reference when you implement these structures yourself.

The steps

9Check yourself without looking back

Try these questions from memory. They cover all the concepts in a mixed order, and a wrong answer links to the section that teaches the idea.

10Review cards

Come back to these after about a day, a week, and a month. To use them with Obsidian's Spaced Repetition plugin, copy the plain lines at the end of this section.

Why is reading an array by index O(1)?::Slots are neighbors of equal size, so the address is start + index × size. That is one calculation for any index.
What is the difference between length and capacity in a dynamic array?::Length counts the stored values, and capacity counts the slots that exist. A resize happens when they are equal.
Why does doubling make append amortized O(1)?::Each resize copies twice as many values as the one before, so n pushes make fewer than 2n copies in total. The average per push is therefore constant.
What does adding one slot per resize cost over n pushes?::About n²/2 copies, because every push copies the whole array.
What does values.insert(0, x) cost, and why?::O(n), because every existing value must shift one slot to the right.
What are the two steps from a key to a slot?::The hash function gives a whole number, and the remainder by the capacity gives a slot.
Why must a hash table compare keys after finding a slot?::Different keys can reach the same slot, so an occupied slot does not prove that the key matches.
Why does a rehash recompute every entry's position?::The slot depends on the capacity through the remainder, so a larger table gives different slots.
Why does linear probing leave a marker when it removes a key?::A search stops at a never-used slot, so an empty slot could cut the path to a later key. A marker keeps the path connected.
Why can a list not be a dictionary key?::A list can change after it is stored. Its hash would change, so a search would start at a different slot and miss the entry.
What is the formula for a range sum with a leading-zero prefix array?::prefix[right + 1] - prefix[left], with both ends of the range included.
When do prefix sums stop being a good fit?::When the array changes between questions, because one update makes every later total wrong and costs O(n) to repair.
When counting stretches that sum to a target, why does the dictionary start with {0: 1}?::A stretch that starts at position 0 needs an earlier total of 0, which only the empty start provides.

Checked on 2 November 2026 with Python 3.13.12: 108 checks passed. They cover the page's data, every practice answer, the printed code, the runnable examples, and the walkthrough against a fresh trace.

Sources

• NeetCode, Algorithms and Data Structures for Beginners and Advanced Algorithms. The topic names and suggested problems were read from these pages. The article text is on a paid plan and was not read.
• Python documentation, Design and History FAQ: how lists and dictionaries are implemented, and why keys must not change.
• Python documentation, Glossary ("hashable", "immutable") and Data model (object.__hash__ and the salting of string hashes).
• Python documentation, Built-in types: the insertion order of a dictionary, and the rule for its keys and for the elements of a set.
• CPython source, Objects/listobject.c (the growth formula in the list resize) and Objects/dictobject.c (open addressing, and the limit of two-thirds on the load factor).
• Python wiki, TimeComplexity, and the same table in a draft of the CPython documentation.
• Wikipedia, Dynamic array, Hash table, and Prefix sum.
• Code on this page: the lesson's own dsa_basics package, written for this lesson. Practice answers and figure data were computed by running it.