1171.remove-zero-sum-consecutive-nodes-from-linked-list.md

1171. Remove Zero Sum Consecutive Nodes from Linked List

Hints

• Think about how to efficiently track the sum of sublists.
• Consider using a hash table to store prefix sums.
• What happens when you encounter the same prefix sum twice?

Prefix Sum + Hash Table (One Pass)

pre[j] - pre[i] = sum of list from i + 1 to j. If pre[j] == pre[i], then sum of list from i + 1 to j = 0.

The key idea is to use prefix sums to track cumulative sums and a hash table to store the first occurrence of each prefix sum. When we encounter the same prefix sum again, we can remove the sublist between these points.

There are a few things to note:

• Using a sentinel node makes it easier to handle edge cases where we need to remove nodes from the beginning.
• We need to clean up the hash table when removing nodes to maintain correctness. (See below) When we iterate the last -1, the prefix sum is 3 which exists in the map. So we relink the node and have to clean up the key between previous 3 and current 3, that are 6, 5, 4, the intermediate nodes are removed, so we have to remove themy from the map as well.

1 -> 2 -> 3 -> -1 -> -1 -> -1 -> -2
1 -> 3 -> 6 ->  5 ->  4 ->  3
     |----------------------|
                            * 3 exists in map
1 -> 2 -> ___________________ -> -2

fun removeZeroSumSublists(head: ListNode?): ListNode? {
    val sentinel = ListNode(-1)
    sentinel.next = head
    val map = HashMap<Int, ListNode>()
    var prefixSum = 0
    var current = head
    map[0] = sentinel
    while (current != null) {
        prefixSum += current.`val`
        val next = current.next
        if (prefixSum in map) {
            // Found a zero-sum sublist
            val previous = map[prefixSum]!!
            
            // Clean up all intermediate prefix sums from the map
            // to avoid incorrect references in future iterations
            var tempNode = previous.next
            var tempSum = prefixSum
            while (tempNode != current) {
                tempSum += tempNode!!.`val`
                map.remove(tempSum)
                tempNode = tempNode.next
            }
            
            // Skip the zero-sum sublist
            previous.next = next
        } else {
            map[prefixSum] = current
        }
        current = next
    }
    return sentinel.next
}

• Time Complexity: O(N), where N is the number of nodes. Each node is visited and processed once.
• Space Complexity: O(N) for the hash table to store prefix sums.

Prefix Sum + Hash Table (Two Pass)

An alternative approach is to first calculate all prefix sums and store them in a hash table, then make a second pass to remove the zero-sum sublists. This approach is more straightforward but requires two passes through the list.

fun removeZeroSumSublists(head: ListNode?): ListNode? {
    // Create a sentinel node to handle edge cases like removing the head
    val sentinel = ListNode(-1)
    sentinel.next = head
    // Map to store prefix sums and their corresponding nodes
    val map = HashMap<Int, ListNode>()
    var prefixSum = 0
    var current = sentinel
    
    /**
     * First pass: Calculate prefix sums and store the last occurrence of each sum.
     * If we encounter the same prefix sum multiple times, we overwrite the previous entry.
     * This effectively remembers only the last node with each prefix sum.
     * 
     * Why do we remember only the last occurrence of each prefix sum?
     * This is crucial because when we find a prefix sum that we've seen before,
     * it means all nodes between the previous occurrence and current node sum to zero.
     * By keeping only the last occurrence, we can later connect nodes to skip all
     * zero-sum sublists in a single operation during the second pass.
     * 
     * For example, if we have: 1->2->-3->3->1 with prefix sums [0,1,3,0,3,4]
     * When we see prefix sum 3 again at node(3), we overwrite the entry for 3,
     * allowing us to later skip the zero-sum segment 2->-3 in the second pass.
     */
    while (current != null) {
        prefixSum += current.`val`
        map[prefixSum] = current
        current = current.next
    }
    
    // Second pass: Remove zero-sum sublists
    prefixSum = 0
    // We start from the sentinel, so that we can handle the case where the entire list sums to 0
    current = sentinel
    while (current != null) {
        prefixSum += current.`val`
        // The key insight: if we've seen this prefix sum before (stored in the map),
        // then all nodes between the current position and the stored position sum to zero
        // We can skip directly to the node after the last occurrence of this prefix sum
        val nextNode = map[prefixSum]?.next
        current.next = nextNode
        current = current.next
    }
    // Return the head of the modified list (skip the sentinel)
    return sentinel.next
}

• Time Complexity: O(N), where N is the number of nodes. We make two passes through the list.
• Space Complexity: O(N) for the hash table to store prefix sums.

Dry Run

For the list: 1 -> 2 -> -3 -> 3 -> 1:

• First pass: Build prefixSum → node map. | Step | Node Value | Prefix Sum | Map Entry Updated To | |------|------------|-------------|-----------------------------------| | 2 | 1 | 1 | 1 → node(1) | | 3 | 2 | 3 | 3 → node(2) | | 4 | -3 | 0 | 0 → node(-3) (overwrites 0) | | 5 | 3 | 3 | 3 → node(3) (overwrites 3) | | 6 | 1 | 4 | 4 → node(1) |

• Final prefixMap after first pass:

{
    0 → node(-3),
    1 → node(1),
    3 → node(3),
    4 → node(1)
}

• Second pass: Remove zero-sum sublists | Step | Prefix Sum | Found in Map? | node.next Becomes | |------|------------|---------------|------------------------------------| | 1 | 0 | Yes → node(-3) | dummy.next = node(-3).next = node(3) | | 2 | 3 | Yes → node(3) | node(3).next = node(3).next (no change) | | 3 | 4 | Yes → node(1) | node(1).next = null |

• Final list after second pass: 3 -> 1

Edge Cases

1. Empty list
2. Single node with value 0
3. Multiple consecutive zero-sum sublists
4. Zero-sum sublist at the beginning or end
5. All nodes sum to zero

Pitfalls

1. Forgetting to use a sentinel node can make handling edge cases more complex
2. Not cleaning up the hash table when removing nodes can lead to incorrect results
3. Not handling the case where the entire list sums to zero
4. Off-by-one errors when removing nodes from the list

Similar or Follow-up Problems

• 209. Minimum Size Subarray Sum
• 560. Subarray Sum Equals K
• 325. Maximum Size Subarray Sum Equals k