Opposing two pointers

When to use it

Use it when the answer is about a pair of positions, and looking at both ends tells you which end to leave behind: they start apart and move toward each other.

It belongs to the search & scan group: Move one or two positions across the input so that nothing is looked at more than a few times.

Watch it work

A boat carries at most two people and at most 130 kilos. The weights of the people are sorted from lightest to heaviest, and nobody is over the limit alone. Return the smallest number of boats that carries everyone.

Input
weights = [30, 50, 60, 70, 90, 100]
limit = 130

Output
4

The method

1. Put left on the lightest person and right on the heaviest
2. Add the two weights that left and right stand on
3. If the pair fits, the lightest goes too: move left inward
4. The heaviest always leaves in this boat: move right inward
5. A person left in the middle takes one more boat alone

The run, one moment at a time

1. Step 1. Left stands on the lightest person, 30 kilos. Right stands on the heaviest, 100 kilos. No boat has left yet.

   weights: 30 50 60 70 90 100  (left at 0, right at 5)
   boats: 0
   

2. Step 2. 30 + 100 = 130. The limit is 130.

   weights: 30 50 60 70 90 100  (left at 0, right at 5)
   boats: 0
   

3. Step 3. 130 is within the limit, so 30 shares the boat with 100. 30 gets in, and left moves inward.

   weights: 30 50 60 70 90 100  (left at 1, right at 5)
   boats: 0
   

4. Step 4. 100 leaves in the same boat, so right moves inward. That is boat 1.

   weights: 30 50 60 70 90 100  (left at 1, right at 4)
   boats: 1
   

5. Step 2. 50 + 90 = 140. The limit is 130.

   weights: 30 50 60 70 90 100  (left at 1, right at 4)
   boats: 1
   

6. Step 4. 140 is over the limit. 50 is the lightest person left, so 90 can share with nobody. 90 leaves alone in boat 2, and right moves inward.

   weights: 30 50 60 70 90 100  (left at 1, right at 3)
   boats: 2
   

7. Step 2. 50 + 70 = 120. The limit is 130.

   weights: 30 50 60 70 90 100  (left at 1, right at 3)
   boats: 2
   

8. Step 3. 120 is within the limit, so 50 shares the boat with 70. 50 gets in, and left moves inward.

   weights: 30 50 60 70 90 100  (left at 2, right at 3)
   boats: 2
   

9. Step 4. 70 leaves in the same boat, so right moves inward. That is boat 3.

   weights: 30 50 60 70 90 100  (both at 2)
   boats: 3
   

10. Step 5. Left and right stand on the same person, 60 kilos. One person is left, who takes a boat alone. The answer is 4 boats.

    weights: 30 50 60 70 90 100  (both at 2)
    boats: 4
    

The code

The numbered comments are the steps of the method.

function solve(weights, limit) {
  // 1. Put left on the lightest person and right on the heaviest
  let left = 0;
  let right = weights.length - 1;
  let boats = 0;
  while (left < right) {
    // 2. Add the two weights that left and right stand on
    const total = weights[left] + weights[right];
    // 3. If the pair fits, the lightest goes too: move left inward
    if (total <= limit) left += 1;
    // 4. The heaviest always leaves in this boat: move right inward
    right -= 1;
    boats += 1;
  }
  // 5. A person left in the middle takes one more boat alone
  if (left === right) boats += 1;
  return boats;
}

def solve(weights, limit):
    # 1. Put left on the lightest person and right on the heaviest
    left = 0
    right = len(weights) - 1
    boats = 0
    while left < right:
        # 2. Add the two weights that left and right stand on
        total = weights[left] + weights[right]
        # 3. If the pair fits, the lightest goes too: move left inward
        if total <= limit:
            left += 1
        # 4. The heaviest always leaves in this boat: move right inward
        right -= 1
        boats += 1
    # 5. A person left in the middle takes one more boat alone
    if left == right:
        boats += 1
    return boats

How to spot it

Given: A list sorted from smallest to largest, and a pair to find

In sorted order the two ends are the smallest and the largest. Their sum tells you which one is too small or too large to keep.

Asked: Does the whole string read the same forward and backward?

The first item must match the last, the second must match the one before last. Two positions moving inward check exactly those pairs.

Asked: Choose two positions; the score grows with the distance between them

Start with the widest pair. Every move gives up distance, so leave the end that cannot score higher with any other partner.

Limits: Trying every pair is too slow, and extra space must stay constant

A table of values seen would cost memory. Two positions are two numbers, however long the list is, and together they move at most n places.

Looks like it, but is not

• You need two values with a given sum, the list is not sorted, and you must return their positions. Use Hash map lookup. Sorting would lose the positions. A map finds the partner of each value in one step and needs no order.
• You want the longest stretch of neighboring items that keeps a rule. Use Variable sliding window. A stretch has two edges that both move from left to right. Here the two positions start at opposite ends and move toward each other.
• You must find the longest piece of a string that reads the same forward and backward. Use Expand around a center. You do not know where the piece starts or ends, so there are no two ends to begin from. You grow outward from each possible middle instead.

Cost and mistakes

Time grows with the number of values, written O(n): every step moves at least one end inward, so the ends meet after at most n steps. Extra space is constant, written O(1): two positions and a count.

Watch out

• The move must be safe. On an unsorted list a sum that is too large does not tell you which end to drop, so sort first or choose another pattern.
• Decide what happens when the two ends meet. With left < right the loop stops while one value may still stand in the middle. A pair check can ignore it; the boats cannot.

In the 150

5 problems of the 150 use it. Naming them gives their method away, so the list is folded.