CODEWITHSUNDEEP
algorithm
atprra
atprra

Reputation: 114

Given a circular linked list, find a suitable head such that the running sum of the values is never negative

I have a linked list with integers. For example:

-2 → 2
 ↑   ↓ 
 1 ← 5

How do I find a suitable starting point such that the running sum always stays non-negative?

For example:

If I pick -2 as starting point, my sum at the first node will be -2. So that is an invalid selection.

If I pick 2 as the starting point, the running sums are 2, 7, 8, 6 which are all positive numbers. This is a valid selection.

The brute force algorithm is to pick every node as head and do the calculation and return the node which satisfies the condition, but that is O(𝑛²).

Can this be done with O(𝑛) time complexity or better?

Upvotes: 3

Views: 127

Answers (2)

trincot
trincot

Reputation: 350961

The idea is to use a window, i.e. two node references, where one runs ahead of the other, and the sum of the nodes within that window is kept in sync with any (forward) movement of either references. As long as the sum is non-negative, enlarge the window by adding the front node's value and moving the front reference ahead. When the sum turns negative, collapse the window, as all suffix sums in that window will now be negative. The window becomes empty, with back and front referencing the same node, and the running sum (necessarily) becomes zero, but then the forward reference will move ahead again, widening the window.

The algorithm ends when all nodes are in the window, i.e. when the front node reference meets the back node reference. We should also end the algorithm when the back reference hits or overtakes the list's head node, since that would mean we looked at all possibilities, but found no solution.

Here is an implementation of that algorithm in JavaScript. It first defines a class for Node and one for CircularList. The latter has a method getStartingNode which returns the node from where the sum can start and can accumulate without getting negative:

class Node {
    constructor(value, next=null) {
        this.value = value;
        this.next = next;
    }
}

class CircularList {
    constructor(values) {
        // Build a circular list for the given values
        let node = new Node(values[0]);
        this.head = node;
        for (let i = values.length - 1; i > 0; i--) {
            node = new Node(values[i], node);
        }
        this.head.next = node; // close the cycle
    }
    getStartingNode() {
        let looped = false;
        let back = this.head;
        let front = this.head;
        let sum = 0;
        while (true) {
            // As long as the sum is not negative (or window is empty),
            // ...widen the window
            if (front === back || sum >= 0) {
                sum += front.value;
                front = front.next;
                if (front === back) break; // we added all values!
                if (front === this.head) looped = true;
            } else if (looped) {
                // avoid endless looping when there is no solution
                return null; 
            } else { // reset window
                sum = 0;
                back = front;
            }
        }
        if (sum < 0) return null; // no solution
        return back;
    }
}

// Run the algorithm for the example given in question
let list = new CircularList([-2, 2, 5, 1]);
console.log("start at", list.getStartingNode()?.value);

As the algorithm is guaranteed to end when the back reference has visited all nodes, and the front reference will never overtake the back reference, this is has a linear time complexity. It cannot be less as all node values need to be read to know their sum.

I have assumed that the value 0 is allowed as a running sum, since the title says it should never be negative. If zero is not allowed, then just change the comparison operators used to compare the sum with 0. In that case the comparison back === front is explicitly needed in the first if statement, otherwise you may actually drop it, since that implies the sum is 0, and the second test in that if condition does the job.

Upvotes: 2

Matt Timmermans
Matt Timmermans

Reputation: 59303

Let's say you start doing a running sum at some head node, and you eventually reach a point where the sum goes negative.

Obviously, you know that the head node you started at is invalid as an answer to the question.

But also, you know that all of nodes contributing to that sum are invalid. You've already checked all the prefixes of that sublist, and you know that all the prefixes have nonnegative sums, so removing any prefix from the total sum can only make it smaller. Also, of course, the last node you added must be negative, you can't start their either.

This leads to a simple algorithm:

  • Start a cumulative sum at the head node.
  • If it becomes negative, discard all the nodes you've looked at and start at the next one
  • Stop when the sum includes the whole list (success), or when you've discarded all the nodes in the list (no answer exsits)

Upvotes: 3

Related Questions