Foundations · pattern 4 of 10

Prefix and suffix passes

A prefix is everything before a position; a suffix is everything after it. Walk the list once from the left and once from the right, each time carrying a running result such as the total so far. Then every position knows both sides.

Watch it run in the app

When to use it

Use it when the answer at each position needs a total or a best of everything before it and of everything after it.

It belongs to the foundations group: Remember what you have seen, in a shape that makes the next question take one step.

Watch it work

Books stand in a row, each with a number of pages. Two friends share them: one takes all books before a chosen book, the other all books after it. Return the position of the chosen book that gives both the same number of pages, or -1 if none does.

Input
pages = [2, 1, 3, 5, 4, 2]

Output
3

The method

Make a list for the pages before each book
Going right, store the running total, then add the book to it
Going left, keep a running total of the pages after the book
Where both totals are equal, that book is the answer
Otherwise add the book to the pages after and move left

The run, one moment at a time

Step 1. No book has been looked at. The list of the pages before each book is empty, and the running total is 0.
```
pages: 2 1 3 5 4 2
before: empty
total: 0
```
Step 2. Nothing stands before book 0, so store 0. Then add its 2 pages: the running total is 2.
```
pages: 2 1 3 5 4 2
before: 0
total: 2
```
Step 2. The running total is 2, so book 1 has 2 pages before it. Store 2, then add its 1 page: the total is 3.
```
pages: 2 1 3 5 4 2
before: 0 2
total: 3
```
Step 2. The running total is 3, so book 2 has 3 pages before it. Store 3, then add its 3 pages: the total is 6.
```
pages: 2 1 3 5 4 2
before: 0 2 3
total: 6
```
Step 2. The running total is 6, so book 3 has 6 pages before it. Store 6, then add its 5 pages: the total is 11.
```
pages: 2 1 3 5 4 2
before: 0 2 3 6
total: 11
```
Step 2. The running total is 11, so book 4 has 11 pages before it. Store 11, then add its 4 pages: the total is 15.
```
pages: 2 1 3 5 4 2
before: 0 2 3 6 11
total: 15
```
Step 2. The running total is 15, so book 5 has 15 pages before it. Store 15, then add its 2 pages: the total is 17.
```
pages: 2 1 3 5 4 2
before: 0 2 3 6 11 15
total: 17
```
Step 3. Every book now knows the pages before it. Turn around and go left, starting with 0 pages after, because nothing stands after book 5.
```
pages: 2 1 3 5 4 2
before: 0 2 3 6 11 15
after: 0
```
Step 5. Book 5 has 15 pages before it and 0 after it: not equal. Add its 2 pages, so book 4 has 2 pages after it.
```
pages: 2 1 3 5 4 2
before: 0 2 3 6 11 15
after: 2
```
Step 5. Book 4 has 11 pages before it and 2 after it: not equal. Add its 4 pages, so book 3 has 6 pages after it.
```
pages: 2 1 3 5 4 2
before: 0 2 3 6 11 15
after: 6
```
Step 4. Book 3 has 6 pages before it and 6 after it. The two sides are equal, so the answer is position 3.
```
pages: 2 1 3 5 4 2
before: 0 2 3 6 11 15
after: 6
```

The code

The numbered comments are the steps of the method.

JavaScript

function solve(pages) {
  // 1. Make a list for the pages before each book
  const before = [];
  // 2. Going right, store the running total, then add the book to it
  let total = 0;
  for (let i = 0; i < pages.length; i++) {
    before.push(total);
    total += pages[i];
  }
  // 3. Going left, keep a running total of the pages after the book
  let after = 0;
  for (let i = pages.length - 1; i >= 0; i--) {
    // 4. Where both totals are equal, that book is the answer
    if (before[i] === after) return i;
    // 5. Otherwise add the book to the pages after and move left
    after += pages[i];
  }
  // No book gives both friends the same.
  return -1;
}

Python

def solve(pages):
    # 1. Make a list for the pages before each book
    before = []
    # 2. Going right, store the running total, then add the book to it
    total = 0
    for i in range(len(pages)):
        before.append(total)
        total += pages[i]
    # 3. Going left, keep a running total of the pages after the book
    after = 0
    for i in reversed(range(len(pages))):
        # 4. Where both totals are equal, that book is the answer
        if before[i] == after:
            return i
        # 5. Otherwise add the book to the pages after and move left
        after += pages[i]
    # No book gives both friends the same.
    return -1

How to spot it

Asked: Compare what is left of a position with what is right of it: Each side is a running result. One pass from the left and one from the right give both sides to every position.
Asked: For each position, a result from all the items except that one: All except one is everything before it together with everything after it. Each side is carried along in its own pass.
Limits: You may not use division: Dividing the product of all the items by one item would take that item out. Without division, the two sides have to be built separately.
Limits: Up to 100,000 items, so adding up each side again is too slow: Building both sides again for every position is about 10 billion steps. Two passes are 200,000.

Looks like it, but is not

For each item you need the next larger item to its right. Use Monotonic stack. That is one particular item, not a total of the whole side. A stack that holds the items still waiting finds it.
You need the sum of every stretch of k items in a row. Use Fixed-size sliding window. A stretch has two ends that both move. Add the item that enters and take off the item that leaves.
The answer at each position depends only on the answers before it. Use One-dimensional dynamic programming. One pass from the left is enough then. There is no right side to bring in.

Cost and mistakes

Time is two passes, about 2n steps, written O(n), because each pass does one small step for each item. Extra space is one stored value for each position, also O(n), for the side built first.

Watch out

Store the running total before you add the current item. If you add first, the item is counted as part of its own left side.
Start the second pass from a fresh value that changes nothing: 0 for a sum, 1 for a product. Do not reuse the total of the first pass.
Sums have a shortcut: the total minus the left side minus the item is the right side. A product without division, or a largest value, cannot be split that way, so it needs its own pass from the right.

In the 150

One problem of the 150 uses it. Naming them gives their method away, so the list is folded.

Show it

Product of Array Except SelfMedium · Arrays & Hashing