Eliminating consecutive numbers that sum up to zero

Today, I was re-introduced to the concept of prefix-sum. It was a concept that I probably learnt in the second year of college. It has of course been pretty much useless to me in my career ever since. Nevertheless, it was the subject - or rather the solution to today's Daily coding problem.

Given a linked list, remove all consecutive nodes that sum to zero. Print out the remaining nodes.

For example, suppose you are given the input 3 -> 4 -> -7 -> 5 -> -6 -> 6. In this case, you should first remove 3 -> 4 -> -7, then -6 -> 6, leaving only 5.

and here is the problem presented in leetcode -

https://leetcode.com/problems/remove-zero-sum-consecutive-nodes-from-linked-list/

Understanding the problem

I'll admit I totally misread the problem. I assumed that the problem asked to eliminate TWO consecutive numbers that summed to zero, rather than any arbitrary numbers in sequence.

First thoughts at a solution

My first thought was to keep a running sum, along with a set of pointers that adjusted when the sum was zero and elements that summed to zero were eliminated

While this was a workable solution, it proved more complicated that it needed to be, especially when requiring to jump over elements that were not part of the zero sum

Prefix sum

According to Wikipedia -

In computer science, the prefix sum, cumulative sum, inclusive scan, or simply scan of a sequence of numbers x0, x1, x2, ... is a second sequence of numbers y0, y1, y2, ..., the sums of prefixes (running totals) of the input sequence:

    y0 = x0y1 = x0 + x1y2 = x0 + x1+ x2

A feature

One feature of a prefix sum is that, if we encounter two elements with the same prefix sum, it implies that the numbers in between these two numbers including the last number can be summed up to zero

With this information, it is possible to refine the earlier solution and keep track of ALL the prefix sums as we traverse the linked list. We can remove the necessary nodes when we have already encountered a prefix sum before.

Here is the code in Java from a discussion in leetcode -

    public ListNode removeZeroSumSublists(ListNode head) {
        ListNode dummy = new ListNode(0), cur = dummy;
        dummy.next = head;
        int prefix = 0;
        Map<Integer, ListNode> m = new HashMap<>();
        while (cur != null) {
            prefix += cur.val;
            if (m.containsKey(prefix)) {
                cur =  m.get(prefix).next;
                int p = prefix + cur.val;
                while (p != prefix) {
                    m.remove(p);
                    cur = cur.next;
                    p += cur.val;
                }
                m.get(prefix).next = cur.next;
            } else {
                m.put(prefix, cur);
            }
            cur = cur.next;
        }
        return dummy.next;
    }

and a comparable solution from geeks for geeks -

https://www.geeksforgeeks.org/delete-continuous-nodes-with-sum-k-from-a-given-linked-list/