1171. Remove Zero Sum Consecutive Nodes from Linked List
Problem Description
In this problem, we are provided with the head node of a singly linked list, which is a data structure where each node contains a value and a reference to the next node. Our task is to remove all consecutive sequences of nodes from this linked list that, when their values are added together, sum up to 0
.
The challenge lies in the possibility of such sequences being spread across the linked list and not necessarily being adjacent immediately. Furthermore, after removing a sequence that sums to 0
, new sequences can form, also leading to a sum of 0
, which should be removed as well. This process must be repeated until there are no more sequences with a sum of 0
remaining.
For example, if we have a linked list 1 -> 2 -> -3 -> 3 -> 1
, we can see that the nodes 2 -> -3 -> 3
sum up to 2 + (-3) + 3 = 0
. If we remove these nodes, the linked list becomes 1 -> 1
. The requirement is to keep removing such sequences until no such sequence exists, and in this case, we would finally end up with an empty linked list as 1 -> 1
also sums up to 0
.
Intuition
To solve this problem, we use a two-pass approach leveraging the concept of a prefix sum and a hash table. The prefix sum for a node in the linked list is the sum of all node values from the head up to and including that node. If at any point, we find two nodes with the same prefix sum, the nodes between them sum to 0
, and thus that sequence can be removed.
For example, suppose that for a linked list 1 -> 2 -> -3 -> 3 -> 1
, the prefix sum at the first 1
is 1
, then 3
at 2
, back to 0
after -3
, up to 3
at the second 3
, and finally 4
at the last 1
. The appearance of 0
as a prefix sum implies that the subsequence from the beginning up to that point sums to 0
.
Here's our approach step by step:
-
We create a dummy node that we'll use as a new head, which helps us deal with edge cases where the beginning of the linked list might sum to
0
and be removed. -
We iterate through the list, calculating the prefix sum for each node. We keep a track of the last seen node for each prefix sum in a hash table. If the same prefix sum is encountered again, we update it in the hash map with the most recent node. This is because any node sequences between the two nodes with the same sum can be removed, so we only care about the latest position for that prefix sum.
-
After populating the hash table, we make a second pass through the list, again calculating the prefix sum. Using our hash table, we can now update the
next
pointer of the current node to skip over any nodes that are part of a zero-sum sequence by setting it to thenext
of the last node remembered for the current prefix sum.
With this approach, we effectively go over the list, find all sequences summing to 0
, and remove them, then return the list with all those sequences gone.
Learn more about Linked List patterns.
Solution Approach
The provided solution makes use of the prefix sum concept and a hash table to efficiently find and remove zero-sum consecutive sequences in the linked list. Here's how the implementation unfolds:
- We initialize a
dummy
node that acts as a pre-head, ensuring we can handle cases where the head itself might be part of a zero-sum sequence. Thisdummy
node points to the originalhead
of the list.
dummy = ListNode(next=head)
-
We declare a hash table
last
to record the last node for each unique prefix sum observed. The hash table is indexed by the prefix sum and contains the corresponding node as its value. -
Starting from the
dummy
node (pre-head), we iterate through the linked list to calculate the prefix sums
for each node. As we compute the prefix sum, we update thelast
hash table with the current node. If the same sum occurs again later, it overwrites the previous node, since we only need the latest one.
s, cur = 0, dummy
while cur:
s += cur.val
last[s] = cur
cur = cur.next
- After populating the
last
table, we iterate the list again, starting from thedummy
node, to update thenext
pointers. For each node, as we calculate the prefix sums
, we find the node corresponding to this sum in thelast
table, and we set the current nodeāsnext
pointer tolast[s].next
. This effectively skips over and removes any nodes part of a zero-sum sequence found between the two nodes with equal prefix sums.
s, cur = 0, dummy
while cur:
s += cur.val
cur.next = last[s].next
cur = cur.next
- Finally, we return
dummy.next
ā the head of the modified list, which no longer contains any sequence of nodes that sum up to0
.
The two primary components used in the solution are:
- Prefix Sum: This technique is critical to discover sequences that total to
0
. By keeping track of the cumulative sum at each node, we can swiftly identify regions of the list that cancel each other out. - Hash Table: By storing the last occurrence of a node for a given prefix sum, we have the ability to quickly jump over sequences that sum to
0
. This is because if a prefix sum repeats, the sum of the nodes between those repetitions is necessarily0
.
Together, these structures allow the algorithm to achieve its goal with a linear time complexity relative to the number of nodes in the list, since each node is processed directly without the need for nested loops or recursion.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's consider a simple linked list to illustrate the solution approach: 3 -> 4 -> -7 -> 5 -> -6 -> 6
. The goal is to remove sublists that sum to 0
.
-
Initialize a
dummy
node and alast
hash tableWe create a
dummy
node and initialize ourlast
hash table to store the last node associated with each unique prefix sum. Initially, thedummy
node points to the head of our list (3
). -
First pass: Compute prefix sums and populate the
last
tableStarting from the
dummy
node, theprefix sum (s)
andlast
table will be updated as follows:s: 0 -> dummy node (There's always a dummy node associated with prefix sum 0) s: 3 -> 3 (First node with value 3) s: 7 -> 4 (Node with value 4) s: 0 -> -7 (Node with value -7, this gives us a prefix sum of 0, meaning everything from the dummy to this node sums to 0) s: 5 -> 5 (We continue the process from the node with value 5) s: -1 -> -6 s: 5 -> 6 (The last node, summing up to 5)
Notice how the prefix sum returned to
0
when we included the-7
node, implying the sublist3 -> 4 -> -7
sums to0
and should be removed. -
Second pass: Update the
next
pointers using thelast
tableWe iterate through the list again, using the
last
table to updatenext
pointers. We perform the following updates, recalculating the prefix sums
:s: 0, dummy.next -> last[0].next (skipping to node with value 5) s: 5, 5.next -> last[5].next (skipping to node with value 6)
After the second pass, the list becomes
5 -> 6
, since the first part3 -> 4 -> -7
has been skipped. We then continue and find that5 -> -6 -> 6
also sum to0
and should be removed. -
Final list
After all updates, the prefix sums that led to a non-zero result have been removed, and we are left with an empty list, as the entire list was a combination of zero-sum sublists. The
dummy.next
now points toNone
.
By using the prefix sum and a hash table to keep track of the last occurrence of each prefix sum, we have efficiently removed consecutive sequences that sum to 0
. The resulting list would be returned as the modified list without these zero-sum sequences.
Solution Implementation
1# Definition for singly-linked list.
2class ListNode:
3 def __init__(self, value=0, next_node=None):
4 self.value = value
5 self.next = next_node
6
7class Solution:
8 def removeZeroSumSublists(self, head: Optional[ListNode]) -> Optional[ListNode]:
9 # Create a dummy node which points to the head of the list. This helps with edge cases.
10 dummy_node = ListNode(next_node=head)
11
12 # Dictionary to keep track of the prefix sums and their corresponding nodes.
13 prefix_sums = {}
14
15 # Calculate the prefix sums and store the most recent node that resulted in each sum.
16 current_sum, current_node = 0, dummy_node
17 while current_node:
18 current_sum += current_node.value
19 prefix_sums[current_sum] = current_node
20 current_node = current_node.next
21
22 # Reset the sum and traverse the list again to remove zero-sum sublists.
23 current_sum, current_node = 0, dummy_node
24 while current_node:
25 current_sum += current_node.value
26 # Set the next node to be the node that follows the last occurrence of the current sum.
27 current_node.next = prefix_sums[current_sum].next
28 current_node = current_node.next
29
30 # The dummy node's next now points to the head of the adjusted list.
31 return dummy_node.next
32
1class Solution {
2 public ListNode removeZeroSumSublists(ListNode head) {
3 // Dummy node to serve as a new starting point for the linked list
4 ListNode dummyHead = new ListNode(0, head);
5 // HashMap to store the cumulative sum and corresponding node
6 Map<Integer, ListNode> cumulativeSumMap = new HashMap<>();
7
8 int sum = 0; // Variable to hold the cumulative sum of node values
9 ListNode current = dummyHead; // Current node, starting from the dummy head
10
11 // First pass: Calculate cumulative sums and save the last occurrence
12 // of each sum in the HashMap
13 while (current != null) {
14 sum += current.val;
15 cumulativeSumMap.put(sum, current);
16 current = current.next;
17 }
18
19 sum = 0; // Reset the sum for the second pass
20 current = dummyHead; // Reset current node to the dummy head
21
22 // Second pass: Remove zero-sum sublists
23 while (current != null) {
24 sum += current.val; // Update the cumulative sum
25
26 // If we have seen this sum before, it means the sublist between the
27 // previous occurrence and this one sums to zero
28 current.next = cumulativeSumMap.get(sum).next;
29
30 current = current.next; // Move to the next node
31 }
32
33 return dummyHead.next; // Return the updated list without the dummy head
34 }
35}
36
1#include <unordered_map>
2
3// Definition for singly-linked list.
4struct ListNode {
5 int val;
6 ListNode *next;
7 ListNode() : val(0), next(nullptr) {}
8 ListNode(int x) : val(x), next(nullptr) {}
9 ListNode(int x, ListNode *next) : val(x), next(next) {}
10};
11
12class Solution {
13public:
14 ListNode* removeZeroSumSublists(ListNode* head) {
15 // Create a dummy head node to handle edge cases seamlessly
16 ListNode* dummyHead = new ListNode(0, head);
17 std::unordered_map<int, ListNode*> lastSeenPrefixSum;
18 ListNode* current = dummyHead;
19 int prefixSum = 0;
20
21 // First pass to record the last occurrence of each prefix sum
22 while (current) {
23 prefixSum += current->val;
24 lastSeenPrefixSum[prefixSum] = current;
25 current = current->next;
26 }
27
28 // Reset the prefix sum and re-iterate from the dummy head
29 prefixSum = 0;
30 current = dummyHead;
31
32 // Second pass to connect nodes bypassing the zero-sum sublists
33 while (current) {
34 prefixSum += current->val;
35 // Link the current node to the node following the last occurrence of the same prefix sum
36 // This effectively removes the zero-sum sublists
37 current->next = lastSeenPrefixSum[prefixSum]->next;
38 current = current->next;
39 }
40
41 // Return the next element of the dummy head which would be the new list head
42 return dummyHead->next;
43 }
44};
45
1// Type definition for a ListNode.
2type ListNode = {
3 val: number;
4 next: ListNode | null;
5};
6
7/**
8 * Removes all contiguous sublists with sum zero from a linked list.
9 * @param head The head of the singly linked list.
10 * @return The head of the modified linked list, with zero-sum sublists removed.
11 */
12function removeZeroSumSublists(head: ListNode | null): ListNode | null {
13 // Dummy node at the start of the list to simplify edge cases.
14 const dummy: ListNode = { val: 0, next: head };
15 // A map to store the cumulative sum of nodes and their last occurrences.
16 const lastOccurrenceOfSum: Map<number, ListNode> = new Map();
17 let sum = 0;
18
19 // First pass: Compute the cumulative sum and track the last occurrence of each sum.
20 for (let currentNode: ListNode | null = dummy; currentNode; currentNode = currentNode.next) {
21 sum += currentNode.val;
22 lastOccurrenceOfSum.set(sum, currentNode);
23 }
24
25 sum = 0; // Reset sum for the second pass.
26
27 // Second pass: Use the last occurrence map to skip over zero-sum sublists.
28 for (let currentNode: ListNode | null = dummy; currentNode; currentNode = currentNode.next) {
29 sum += currentNode.val;
30 // The next node will be the one after the last occurrence of the current sum.
31 // As we have removed zero-sum sublists, the sums will not repeat in the new list.
32 currentNode.next = lastOccurrenceOfSum.get(sum)!.next;
33 }
34
35 // Return the modified list, sans the dummy node.
36 return dummy.next;
37}
38
Time and Space Complexity
The provided code has a time complexity of O(n)
where n
is the length of the linked list. This is because the code consists of two separate while loops that each iterate through the list once. The first while loop constructs a dictionary (last) mapping the cumulative sums of the nodes up to that point to the corresponding node. The second while loop uses the dictionary to skip over nodes that are part of a zero-sum sublist by setting the next
pointer of previous non-zero-sum nodes to the next node in the last occurrence of that sum.
The space complexity of the code is O(n)
as well. The primary factor contributing to the space complexity is the dictionary (last
) which stores a value for each unique cumulative sum encountered while iterating through the list. In the worst-case scenario, there could be as many unique sums as there are nodes in the list (when no sublists sum to zero), which would require storing each node in the dictionary, hence O(n)
space is needed.
Learn more about how to find time and space complexity quickly using problem constraints.
Which type of traversal does breadth first search do?
Recommended Readings
Linked List Cycle Given a linked list with potentially a loop determine whether the linked list from the first node contains a cycle in it For bonus points do this with constant space Parameters nodes The first node of a linked list with potentially a loop Result Whether there is a loop contained
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Want a Structured Path to Master System Design Too? Donāt Miss This!