Jobs

Interviews

Discussions

Remove Zero Sum Consecutive Nodes from Linked List

Medium

Asked by:

More companies

43 views

Topics:

Linked ListsHash Table

Given the head of a linked list, we repeatedly delete consecutive sequences of nodes that sum to 0 until there are no such sequences.

After doing so, return the head of the final linked list. You may return any such answer.

(Note that in the examples below, all sequences are serializations of ListNode objects.)

Example 1:

Input: head = [1,2,-3,3,1]
Output: [3,1]
Note: The answer [1,2,1] would also be accepted.

Example 2:

Input: head = [1,2,3,-3,4]
Output: [1,2,4]

Example 3:

Input: head = [1,2,3,-3,-2]
Output: [1]

Constraints:

The given linked list will contain between 1 and 1000 nodes.
Each node in the linked list has -1000 <= node.val <= 1000.

Try coding it in LeetCode

Remove Zero Sum Consecutive Nodes from Linked List

Medium

Asked by:

43 views

Topics:

Linked ListsHash Table

Given the head of a linked list, we repeatedly delete consecutive sequences of nodes that sum to 0 until there are no such sequences.

After doing so, return the head of the final linked list. You may return any such answer.

(Note that in the examples below, all sequences are serializations of ListNode objects.)

Example 1:

Input: head = [1,2,-3,3,1]
Output: [3,1]
Note: The answer [1,2,1] would also be accepted.

Example 2:

Input: head = [1,2,3,-3,4]
Output: [1,2,4]

Example 3:

Input: head = [1,2,3,-3,-2]
Output: [1]

Constraints:

The given linked list will contain between 1 and 1000 nodes.
Each node in the linked list has -1000 <= node.val <= 1000.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values that the nodes in the linked list can have? Can they be negative, zero, or floating-point numbers?
If the entire list sums to zero, should I return an empty list or a null/empty head?
Are there any constraints on the length of the linked list that I should be aware of?
If there are multiple sublists that sum to zero, should I remove all of them, including overlapping ones?
Should I modify the existing linked list in-place, or create a new linked list with the zero-sum sublists removed?

Brute Force Solution

Approach

The brute force method for removing zero-sum nodes involves checking every possible sequence of connected nodes. We'll examine each possible sublist to see if its values add up to zero. If a zero-sum sequence is found, we'll remove it and repeat the process until no more zero-sum sequences exist.

Here's how the algorithm would work step-by-step:

Start with the beginning of the list and consider the first node alone.
Then, consider the first two nodes together, then the first three, and so on, each time calculating the sum of the values.
If any of these sequences add up to zero, remove that entire sequence from the list.
After removing a sequence, start the process all over again from the beginning of the modified list.
If you get through the entire list without finding any sequence that adds to zero, move on to the next step.
Now, repeat the entire process, but this time starting from the second node in the original list.
Continue this process, each time starting one node further down the list than before.
Keep repeating these steps until you've checked every possible starting point in the list and no more zero-sum sequences can be found.

Code Implementation

class ListNode:
    def __init__(self, value=0, next_node=None):
        self.value = value
        self.next_node = next_node

def remove_zero_sum_brute_force(head):
    while True:
        is_changed = False
        current_node = head
        previous_node = None

        while current_node:
            sum_nodes = 0
            temp_node = current_node

            while temp_node:
                sum_nodes += temp_node.value

                if sum_nodes == 0:
                    # Zero sum found, remove nodes
                    is_changed = True

                    if previous_node:
                        previous_node.next_node = temp_node.next_node
                        current_node = temp_node.next_node

                    else:
                        head = temp_node.next_node
                        current_node = temp_node.next_node

                    break

                temp_node = temp_node.next_node

            if sum_nodes != 0:
                previous_node = current_node
                current_node = current_node.next_node

        if not is_changed:
            # No changes in this iteration, so exit
            break

    return head

Big(O) Analysis

Time Complexity

O(n^3) – The described brute force approach iterates through the linked list multiple times. The outer loop iterates 'n' times, each time starting from a different node. The inner loop, for each starting node, considers all possible consecutive sequences, up to 'n' in length, to check if they sum to zero, requiring at most n operations. If a zero-sum sequence is found, the entire process restarts, potentially requiring further iterations. In the worst case, where many zero-sum sequences are present, this restarting could lead to an additional factor of n, making the overall time complexity O(n * n * n) or O(n^3).

Space Complexity

O(1) – The brute force approach, as described, does not use any auxiliary data structures like hash maps or additional lists to store intermediate sums or node references. The algorithm operates directly on the linked list, potentially modifying its structure in place. Therefore, the space complexity is dominated by a few pointer variables used for traversing and manipulating the linked list, and the space needed remains constant regardless of the linked list's size, N.

Optimal Solution

Approach

The goal is to efficiently remove sections of a linked list that add up to zero. We achieve this by keeping track of sums we've seen and quickly jumping over sections that cancel out.

Here's how the algorithm would work step-by-step:

Start at the beginning of the linked list.
Keep a running total of the values as you move through the list.
If at any point the running total is something you've seen before, it means the section between the first time you saw that total and now adds up to zero.
Instead of deleting nodes one by one, directly connect the node before the start of the zero-sum section to the node after the end of the zero-sum section. Essentially, you're skipping over the whole zero-sum part.
If the current running total is new, remember it, along with where in the list you were when you saw it.
Continue doing this until you reach the end of the list. This removes all zero-sum sections in a single pass.

Code Implementation

class ListNode:
    def __init__(self, value=0, next_node=None):
        self.value = value
        self.next_node = next_node

def remove_zero_sum_sublists(head):
    dummy_node = ListNode(0)
    dummy_node.next_node = head
    
    cumulative_sum = 0
    sum_to_node = {0: dummy_node}

    current_node = head
    cumulative_sum = 0

    while current_node:
        cumulative_sum += current_node.value

        if cumulative_sum in sum_to_node:
            # Found a zero-sum sublist, adjust pointers

            prefix_node = sum_to_node[cumulative_sum]
            temporary_node = prefix_node.next_node
            prefix_cumulative_sum = cumulative_sum

            # Remove the intermediate sums from the dictionary
            while temporary_node != current_node:
                prefix_cumulative_sum += temporary_node.value
                del sum_to_node[prefix_cumulative_sum]
                temporary_node = temporary_node.next_node
            
            prefix_node.next_node = current_node.next_node

        else:
            # Store current sum and corresponding node

            sum_to_node[cumulative_sum] = current_node

        current_node = current_node.next_node

    return dummy_node.next_node

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the linked list once, performing constant-time operations at each node. It maintains a running sum and uses a hash map (or dictionary) to store previously seen sums and their corresponding nodes. The hash map operations (lookup and insertion) take amortized constant time. The skipping of nodes in zero-sum sublists also occurs in constant time. Therefore, the time complexity is directly proportional to the number of nodes, n, in the linked list.

Space Complexity

O(N) – The algorithm uses a hash map to store the running total (prefix sum) and its corresponding node in the linked list. In the worst-case scenario, where no subarray sums to zero, the hash map will store all N running totals and their corresponding nodes, where N is the number of nodes in the linked list. Thus, the auxiliary space used is proportional to the number of nodes in the linked list. Therefore, the space complexity is O(N).

Edge Cases

Case	How to Handle
Null or empty linked list	Return null immediately, as there are no nodes to process.
Linked list with only one node	Check if the node's value is zero; if so, return null, otherwise return the original list.
Linked list where all node values sum to zero	The algorithm should correctly remove all nodes, resulting in a null list.
Linked list with a very long sequence summing to zero in the middle	The prefix sum hashmap should efficiently identify and remove the zero-sum subsequence.
Integer overflow in prefix sum calculation	Use a data type with a wider range (e.g., long) for prefix sum to prevent overflow, or check for impending overflows and handle the case appropriately.
Multiple non-overlapping zero-sum subsequences	The algorithm should correctly identify and remove all such subsequences in a single pass.
Overlapping zero-sum subsequences	The algorithm should remove the longest possible zero-sum subsequences, handling any overlapping parts correctly because of correct updates to the hashmap index.
Linked list containing only zero values	The algorithm should remove all nodes, resulting in a null list.

Null or empty linked list

How to Handle:

Return null immediately, as there are no nodes to process.

Linked list with only one node

How to Handle:

Check if the node's value is zero; if so, return null, otherwise return the original list.

Linked list where all node values sum to zero

How to Handle:

The algorithm should correctly remove all nodes, resulting in a null list.

Linked list with a very long sequence summing to zero in the middle

How to Handle:

The prefix sum hashmap should efficiently identify and remove the zero-sum subsequence.

Integer overflow in prefix sum calculation

How to Handle:

Use a data type with a wider range (e.g., long) for prefix sum to prevent overflow, or check for impending overflows and handle the case appropriately.

Multiple non-overlapping zero-sum subsequences

How to Handle:

The algorithm should correctly identify and remove all such subsequences in a single pass.

Overlapping zero-sum subsequences

How to Handle:

The algorithm should remove the longest possible zero-sum subsequences, handling any overlapping parts correctly because of correct updates to the hashmap index.

Linked list containing only zero values

How to Handle:

The algorithm should remove all nodes, resulting in a null list.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values that the nodes in the linked list can have? Can they be negative, zero, or floating-point numbers?
If the entire list sums to zero, should I return an empty list or a null/empty head?
Are there any constraints on the length of the linked list that I should be aware of?
If there are multiple sublists that sum to zero, should I remove all of them, including overlapping ones?
Should I modify the existing linked list in-place, or create a new linked list with the zero-sum sublists removed?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start with the beginning of the list and consider the first node alone.
Then, consider the first two nodes together, then the first three, and so on, each time calculating the sum of the values.
If any of these sequences add up to zero, remove that entire sequence from the list.
After removing a sequence, start the process all over again from the beginning of the modified list.
If you get through the entire list without finding any sequence that adds to zero, move on to the next step.
Now, repeat the entire process, but this time starting from the second node in the original list.
Continue this process, each time starting one node further down the list than before.
Keep repeating these steps until you've checked every possible starting point in the list and no more zero-sum sequences can be found.

Code Implementation

class ListNode:
    def __init__(self, value=0, next_node=None):
        self.value = value
        self.next_node = next_node

def remove_zero_sum_brute_force(head):
    while True:
        is_changed = False
        current_node = head
        previous_node = None

        while current_node:
            sum_nodes = 0
            temp_node = current_node

            while temp_node:
                sum_nodes += temp_node.value

                if sum_nodes == 0:
                    # Zero sum found, remove nodes
                    is_changed = True

                    if previous_node:
                        previous_node.next_node = temp_node.next_node
                        current_node = temp_node.next_node

                    else:
                        head = temp_node.next_node
                        current_node = temp_node.next_node

                    break

                temp_node = temp_node.next_node

            if sum_nodes != 0:
                previous_node = current_node
                current_node = current_node.next_node

        if not is_changed:
            # No changes in this iteration, so exit
            break

    return head

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

The goal is to efficiently remove sections of a linked list that add up to zero. We achieve this by keeping track of sums we've seen and quickly jumping over sections that cancel out.

Here's how the algorithm would work step-by-step:

Start at the beginning of the linked list.
Keep a running total of the values as you move through the list.
If at any point the running total is something you've seen before, it means the section between the first time you saw that total and now adds up to zero.
Instead of deleting nodes one by one, directly connect the node before the start of the zero-sum section to the node after the end of the zero-sum section. Essentially, you're skipping over the whole zero-sum part.
If the current running total is new, remember it, along with where in the list you were when you saw it.
Continue doing this until you reach the end of the list. This removes all zero-sum sections in a single pass.

Code Implementation

class ListNode:
    def __init__(self, value=0, next_node=None):
        self.value = value
        self.next_node = next_node

def remove_zero_sum_sublists(head):
    dummy_node = ListNode(0)
    dummy_node.next_node = head
    
    cumulative_sum = 0
    sum_to_node = {0: dummy_node}

    current_node = head
    cumulative_sum = 0

    while current_node:
        cumulative_sum += current_node.value

        if cumulative_sum in sum_to_node:
            # Found a zero-sum sublist, adjust pointers

            prefix_node = sum_to_node[cumulative_sum]
            temporary_node = prefix_node.next_node
            prefix_cumulative_sum = cumulative_sum

            # Remove the intermediate sums from the dictionary
            while temporary_node != current_node:
                prefix_cumulative_sum += temporary_node.value
                del sum_to_node[prefix_cumulative_sum]
                temporary_node = temporary_node.next_node
            
            prefix_node.next_node = current_node.next_node

        else:
            # Store current sum and corresponding node

            sum_to_node[cumulative_sum] = current_node

        current_node = current_node.next_node

    return dummy_node.next_node

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty linked list	Return null immediately, as there are no nodes to process.
Linked list with only one node	Check if the node's value is zero; if so, return null, otherwise return the original list.
Linked list where all node values sum to zero	The algorithm should correctly remove all nodes, resulting in a null list.
Linked list with a very long sequence summing to zero in the middle	The prefix sum hashmap should efficiently identify and remove the zero-sum subsequence.
Integer overflow in prefix sum calculation	Use a data type with a wider range (e.g., long) for prefix sum to prevent overflow, or check for impending overflows and handle the case appropriately.
Multiple non-overlapping zero-sum subsequences	The algorithm should correctly identify and remove all such subsequences in a single pass.
Overlapping zero-sum subsequences	The algorithm should remove the longest possible zero-sum subsequences, handling any overlapping parts correctly because of correct updates to the hashmap index.
Linked list containing only zero values	The algorithm should remove all nodes, resulting in a null list.

Null or empty linked list

How to Handle:

Return null immediately, as there are no nodes to process.

Linked list with only one node

How to Handle:

Check if the node's value is zero; if so, return null, otherwise return the original list.

Linked list where all node values sum to zero

How to Handle:

The algorithm should correctly remove all nodes, resulting in a null list.

Linked list with a very long sequence summing to zero in the middle

How to Handle:

The prefix sum hashmap should efficiently identify and remove the zero-sum subsequence.

Integer overflow in prefix sum calculation

How to Handle:

Use a data type with a wider range (e.g., long) for prefix sum to prevent overflow, or check for impending overflows and handle the case appropriately.

Multiple non-overlapping zero-sum subsequences

How to Handle:

The algorithm should correctly identify and remove all such subsequences in a single pass.

Overlapping zero-sum subsequences

How to Handle:

The algorithm should remove the longest possible zero-sum subsequences, handling any overlapping parts correctly because of correct updates to the hashmap index.

Linked list containing only zero values

How to Handle:

The algorithm should remove all nodes, resulting in a null list.