Hashing & Prefix Sums on Lists

Pointer tricks keep linked-list solutions at $O(1)$ space. Some questions, though, are about values or identities seen earlier: "has this running sum appeared before?", "is this value in the set?", "which new node is the copy of this old one?" For those, you trade memory for speed: a hash map or set answers each lookup in $O(1)$ , and it combines well with a dummy node.

The idea#

Some linked-list problems need memory of what you have already seen. A hash map or set gives you that, and it shows up in two forms.

Prefix sums#

The prefix-sum idea from arrays works on lists too. Walk the list and keep a running sum. If the same prefix sum appears at node p and later at node q, the nodes strictly after p up to and including q add up to zero.

Finding one zero-sum run is easy. To delete every zero-sum run, take two passes:

Walk from a dummy (prefix sum 0) and record, for each prefix sum, the latest node that produced it. Overwriting keeps the last occurrence.
Walk again from the dummy. At each node, set node.next = seen[prefix].next: jump straight past everything up to the last node with the same sum.

Keeping the latest node is what makes one jump enough. It skips the longest zero-sum stretch that starts after this node, which may contain several smaller zero-sum runs.

Membership and identity#

Prefix sums are one use of a map. The other common uses are about whether you've seen a value or a node before.

A set of allowed values turns "count runs of nodes whose values are in a set" into one pass with a flag.
A map from old node to new node lets you copy a list whose nodes have extra pointers. Create every copy first, then wire the pointers through the map.
A set of visited nodes detects a cycle or an intersection in $O(n)$ space. It is the simple alternative to fast/slow pointers.

How to spot it#

These signals point to a hash map or set on a list.

"Remove consecutive nodes that sum to 0" or any "sum of a contiguous run" on a list.
"How many connected components / runs of values from a given set?"
"Deep copy" or "clone" a list with random or extra pointers.
You need to recognize a node you have already seen.

Template#

This is the two-pass prefix-sum shape. The first pass fills the map; the second pass uses it to jump.

dummy = new node with value 0 whose next is head
seen = empty map                     # prefix sum -> node
prefix = 0
for each node from dummy to the end:
    prefix += node.val
    seen[prefix] = node              # overwrite: keep the LATEST node
prefix = 0
for each node from dummy, following the new links:
    prefix += node.val
    node.next = seen[prefix].next    # skip past the last repeat
return dummy.next

Both passes are $O(n)$ time, and the map is $O(n)$ space.

A trace#

To see why keeping the latest node matters, here is the prefix sum at each node of 1 -> 2 -> -3 -> 3 -> 1.

Node	0 (dummy)	1	2	-3	3	1
Prefix sum	0	1	3	0	3	4

Prefix 0 appears at the dummy and at -3, so the dummy jumps to the node after -3. Prefix 3 last appears at the 3, so the result is 3 -> 1.

Pitfalls#

These mistakes leave runs behind or miss a count.

Keeping the first node per sum instead of the latest. Then one jump may only skip a short zero-sum run and leave a longer one behind.
Forgetting prefix sum 0. Without the dummy at sum 0, a zero-sum run that starts at the head can't be removed.
Missing the last run. When you count runs, a run that reaches the end of the list has no non-member after it. Count it after the loop.
Space. These approaches use $O(n)$ extra space. If the problem asks for $O(1)$ , look for a pointer technique instead.

Problems in this pattern#

These problems use this pattern. Solve them before you open the hints below. Start with the first one.

Hints#

Open a hint only after you have tried the problem for a while.

Hint: Remove Zero Sum Consecutive Nodes from Linked List

Use the two-pass template from a dummy with prefix 0. Store the latest node per prefix sum, so a single jump removes the whole stretch.

Hint: Linked List Components

Put nums in a set and walk the list with a flag in_run. Set the flag when a node's value is in the set. When it is not and the flag was set, a run just ended: count it and clear the flag. Count once more after the loop if the flag is still set.

Hint: Copy List with Random Pointer

Build a map from each old node to its new copy in a first pass. In a second pass, wire each copy's next and random by looking up the old node's targets in the map.

Hint: Linked List Cycle II

Store visited nodes in a set. The first node you see twice is the cycle entry. This uses $O(n)$ space; Floyd's method does it in $O(1)$ .

Hint: Intersection of Two Linked Lists

Put every node of list A in a set, then walk list B until a node is in the set. For O(1) space, walk both lists and switch each pointer to the other head at the end; they meet at the intersection.

Key takeaways#

A repeated prefix sum on a list marks a zero-sum run between the two nodes.
Store the latest node per prefix sum, then jump with node.next = seen[prefix].next.
Start from a dummy with prefix 0 so runs at the head can be removed.
Hash sets give $O(n)$ -space answers to cycle and membership questions; old-to-new maps handle deep copies.

Core idea#

Some list questions are about values or nodes seen earlier. A hash map or set answers them in $O(1)$ each, at the cost of $O(n)$ space. It combines well with a dummy node.

Key points#

If the same prefix sum appears at node p and later at node q, the nodes after p up to q sum to zero.
Remove every zero-sum run in two passes from a dummy with prefix sum 0.
Pass 1: store the latest node for each prefix sum. Overwrite on repeats.
Pass 2: at each node, set node.next = seen[prefix].next.
The latest node makes one jump enough. It skips the longest zero-sum stretch, which can hold smaller runs.
A set of allowed values counts runs in one pass with an in_run flag.
A map from old node to new node deep-copies a list with random pointers. Create all copies, then wire next and random.
A set of visited nodes finds a cycle or intersection in $O(n)$ space.

Template#

dummy = new node with value 0 whose next is head
seen = empty map; prefix = 0
for each node from dummy to the end:
    prefix += node.val
    seen[prefix] = node              # keep the LATEST node
prefix = 0
for each node from dummy, following the new links:
    prefix += node.val
    node.next = seen[prefix].next    # skip past the last repeat
return dummy.next

Pitfalls#

Keeping the first node per sum. One jump can then leave a longer zero-sum run behind.
No prefix sum 0. A zero-sum run at the head cannot be removed without the dummy.
Missing the last run in component counting. Count once more after the loop if the flag is set.
$O(n)$ space. If the problem asks for $O(1)$ , use a pointer technique.

Say it in an interview#

"A repeated prefix sum means the nodes between the two repeats sum to zero."
"Keep the latest node per sum, so one jump removes the whole stretch."