Back to Open Book Shelf

Two Pointers: Anchor-Runner

The anchor-runner pointer strategy is a widely-used approach for solving problems that involve manipulating arrays in place. In this assignment, we will explore the anchor-runner pointer strategy, understand how it works, and apply it to solve an example problem.

To effectively use the anchor-runner pointer strategy, just like with the start-end pointer strategy, we need to answer several key questions:

  1. Where does my anchor pointer start?
  2. Where does my runner pointer start?
  3. Under which condition do I move the anchor pointer?
  4. Under which condition do I move the runner pointer?
  5. Does the anchor pointer do something besides moving?
  6. Does the runner pointer do something besides moving?
  7. Under which conditions do we stop the iteration?

By answering these questions, we can establish a clear algorithmic approach that utilizes anchor-runner pointers. This strategy often allows us to mutate the array in place, removing the need for nested loops and improving the efficiency of our solution.

Example Problem

Let's consider a specific problem scenario to illustrate the anchor-runner pointer strategy.

// Given an array of positive integers, our task is
// to move all ones to the end of the array while preserving
// the relative order of non-one elements. The goal is to solve
// this problem in linear time complexity.

// If no ones are present in the array, no changes are needed.

// Example:
// Input: nums = [1, 2, 1, 4, 8]
// Output: [2, 4, 8, 1, 1]

Brute-force Approach

Before applying the anchor-runner pointer strategy, let's consider a naive approach to solving the problem scenario:

  1. Iterate through the array.
  2. If the current element is one, delete it from the array using the splice method.
  3. Push the deleted one to the end of the array using the push method.
  4. Repeat steps 2 and 3 until all ones have been moved to the end of the array.
  5. Return the modified array.

The time complexity of the naive solution is O(N^2) since in each iteration through the array, we perform a deletion operation, which has a time complexity of O(N). This deletion operation is repeated for each element in the array, resulting in a quadratic overall time complexity.

Here is a coded solution for the naive approach. Note that we must use the counter variable to avoid the problem of an infinite loop. After we move a one, we don't want to increment our index, because a new number will now be at the current index. This means that we must either move a number or move our index for each element in our array, but the index can't be relied upon to break out of our loop.

function moveOnes(nums) {
  let idx = 0;
  let counter = 0;

  while (counter < nums.length) {
    if (nums[idx] === 1) {
      nums.splice(idx, 1);
      nums.push(1);
    } else {
      idx++;
    }
    counter++;
  }
  return nums;
}

Anchor-runner Pointer Approach

Now, let's discuss how we can use the anchor-runner (start-end pointer) strategy to solve this problem more efficiently. We can start by thinking high-level, and then we'll address the key questions mentioned earlier.

High-level Overview

The idea of the solution we're going to work on is to maintain two pointers that move through the array, swapping elements with each other based on some rules. Our anchor will be in charge of pointing to ones that we know need to move to the end. Our runner will be in charge of moving ahead to find the non-ones that we can swap our ones with, moving in such a way that maintains the order of our non-one elements. This isn't very detailed, but it's a good mental model to keep in mind as we look at our more precise rules.

Questions to Answer:

  1. Where does my anchor pointer start? - The anchor pointer is initially set to the beginning of the array (index 0).

  2. Where does my runner pointer start? - The runner pointer is initially set to the beginning of the array (index 0) as well.

  3. Under which condition do I move the anchor pointer? - We move the anchor pointer after we make a swap, where anchor is replaced with a non-one.

  4. Under which condition do I move the runner pointer? - We move the runner pointer on each iteration, regardless of the element. When a swap is made, or not, runner will be incremented.

  5. Does the anchor pointer do something besides moving? - It ensures that non-one elements are moved towards the beginning of the array by swapping the element at its current index with the element at the index pointed to by the runner pointer.

  6. Does the runner pointer do something besides moving? - When the runner pointer encounters a non-one element, it swaps the value at its current index with the value at the index pointed to by the anchor pointer.

  7. Under which condition do we stop the iteration? - When the runner pointer makes it to the end of our array.

You might be wondering why we decided to start the runner pointer at index 0 in this problem and why it couldn't start at the end. Let's consider some examples to understand the reasons behind this choice.

First, let's take the array [2, 1, 1, 3]. If we started the runner pointer at the end, it would be pointing at element 3. Since we perform swaps when the runner encounters a non-one element, this would lead to swapping the values at indices 0 and 3, resulting in the array [3, 1, 1, 2]. As you can see, the relative order of the non-one elements is disturbed, and the solution becomes incorrect.

On the other hand, you might think that starting the runner at index 1 could be a valid strategy. For example, in the array [1, 2, 1, 3], if the runner starts at index 1, we would obtain the correct solution. However, consider a scenario where the first element is a non-one element, such as [2, 3, 1, 4]. In this case, starting the runner at index 1 would result in swapping the values at indices 0 and 1, leading to the array [3, 2, 1, 4]. Once again, the relative order of the non-one elements is disturbed, and the solution becomes incorrect.

To avoid these issues and ensure the preservation of the relative order of non-one elements, it is crucial to start the runner pointer at index 0. This ensures that the swapping process occurs correctly, leading to the desired outcome. This can be a bit confusing to think about, so let's see our strategy in action.

Walkthrough

Let's walk through the solution step-by-step using an example with the array [1, 2, 1, 4, 8]:

Step 1: In the first step, we are initializing two pointers anchor (a) and runner (r) at index 0.

Step 2: We check the element at the runner pointer. We make swaps when runner is non-one. Since here it's one, we'll just increment the runner by 1.

Step 3: The element at runner is now 2. It is a non-one element so we swap it with the element at anchor pointer. Then, we move both pointers by 1.

Step 4: We check the element at the runner pointer. It is one, so we increment the runner by 1.

Step 5: The element at runner is now 4. It's not one, so we swap it with the element at the anchor pointer. We then move both pointers by 1.

Step 6: In the final step, the element at runner is 8. It's not one, so we swap it with the element at the anchor pointer. We then move both pointers by 1. The runner pointer has reached the end of the array. The iteration is complete.

After the iteration, the array [1, 2, 1, 4, 8] is modified to [2, 4, 8, 1, 1], with all ones moved to the end while preserving the relative order of non-one elements.

Solution Code

Here's a coded solution in JavaScript:

function moveOnes(arr) {
  let anchor = 0;
  let runner = 0;

  while (runner < arr.length) {
    if (arr[runner] !== 1) {
      // Swap the elements at `anchor` and `runner`
      [arr[anchor], arr[runner]] = [arr[runner], arr[anchor]];
      // Increment `anchor` only when a swap is made
      anchor++;
    }
    // Increment `runner` every iteration
    runner++;
  }

  return arr;
}

const nums1 = [1, 2, 1, 4, 8];
const transformedNums1 = moveOnes(nums1);
console.log(nums1 === transformedNums1); // true
console.log(transformedNums1); // [2, 4, 8, 1, 1]

const nums2 = [3, 1, 5, 1, 1, 4, 8, 1];
const transformedNums2 = moveOnes(nums2);
console.log(nums2 === transformedNums2); // true
console.log(transformedNums2); // [3, 5, 4, 8, 1, 1, 1, 1]

Reader-Writer Variant

High-level Overview

This approach moves through the array in a very similar way to our anchor-runner pointer approach. The difference in this algorithm is that instead of swapping elements, we'll 'write' over ones with non-ones. As our reader comes across non-ones, our writer will overwrite its current element with this non-one given to us by reader. Once reader has read the whole array, we'll need to overwrite the end of the array with the number of ones that we overwrote. Let's look at our questions to get a better understanding.

Questions to Answer:

Now let's explore the reader-writer variant on the same problem. We will address the key questions mentioned earlier. You might notice that the answers to the first 4 questions are the same, however, the final two questions have different answers.

  1. Where does my anchor pointer start? - The anchor pointer (writer) is initially set to the beginning of the array (index 0).

  2. Where does my runner pointer start? - The runner pointer (reader) is initially set to the beginning of the array (index 0) as well.

  3. Under which condition do I move the anchor pointer? - We move the anchor pointer (writer) after we make a modification to our array, where the value at writer is overridden with a non-one.

  4. Under which condition do I move the runner pointer? - We move the runner pointer (reader) on each iteration, regardless of the element. When a modification is made, or not, reader will be incremented.

  5. Does the anchor pointer do something besides moving? - The anchor pointer (writer) indicates the position where the next non-one element should be written.

  6. Does the runner pointer do something besides moving? - The runner pointer (reader) iterates through the array, reading each element, and its goal is to find non-one elements that will be written.

  7. Under which condition do we stop the iteration? - After reader has read our whole array, and we've filled in the rest of our array with the ones that we wrote over.

Walkthrough

Here's the step-by-step explanation of the solution using the reader-writer variant:

Step 1: In the first step, we are initializing two pointers writer (w) and reader (r) at index 0.

Step 2: We check the element at the reader pointer. It's one, so we increment the reader by 1.

Step 3: The element at the reader pointer is now 2. Since it's not one we write it at the writer pointer position. We then move both pointers by 1.

Step 4: We check the element at the reader pointer. It is one, so we increment the reader by 1.

Step 5: The element at the reader pointer is now 4. It's not one so we write it at the writer pointer position. We then move both pointers by 1.

Step 6: In the final step, the element at reader is 8. It's not one, so we write it at the writer pointer position. We then move both pointers by 1.

Step 7: The reader pointer has reached the end of the array. All non-one elements have been written, and all that is left to do is to fill the remaining positions from the writer position onwards with ones.

Step 7.1: We start by writing one at the writer position, and then we move the writer pointer by 1.

Step 7.2: Once again, we write one at the writer position, and then we move the writer pointer by 1. The writer has reached the end of the array after this iteration.

After the iteration, the array [1, 2, 1, 4, 8] is modified to [2, 4, 8, 1, 1], with all ones moved to the end while preserving the relative order of non-one elements.

Now, let's write the coded solution for this reader-writer variant in JavaScript:

function moveOnes(nums) {
  let writer = 0;
  let reader = 0;

  while (reader < nums.length) {
    if (nums[reader] !== 1) {
      // Overwrite the index at `writer` with the value at `reader`
      nums[writer] = nums[reader];
      // Increment `writer` when a modification is made
      writer++;
    }
    // Increment `reader` every iteration
    reader++;
  }

  while (writer < nums.length) {
    nums[writer] = 1;
    writer++;
  }

  return nums;
}

const nums1 = [1, 2, 1, 4, 8];
const transformedNums1 = moveOnes(nums1);
console.log(nums1 === transformedNums1); // true
console.log(transformedNums1); // [2, 4, 8, 1, 1]

const nums2 = [3, 1, 5, 1, 1, 4, 8, 1];
const transformedNums2 = moveOnes(nums2);
console.log(nums2 === transformedNums2); // true
console.log(transformedNums2); // [3, 5, 4, 8, 1, 1, 1, 1]

Summary

Both of these variants allow us to solve the problem in a linear O(N) time complexity. The space complexity is O(1) since we modify the array in-place without using any extra space.

You might be wondering when and why we would use the reader-writer variant instead of the anchor-runner one with swapping. The fact is that when dealing with arrays, in the majority of cases, this is just a matter of stylistic preference, and wherever you can use the reader-writer variant, you can also use the anchor-runner. The situation becomes different when dealing with linked lists (which we will cover in a future lesson), as the option to swap elements of the list is no longer available to us, so, to perform mutation of node values in place, we would have to use the reader-writer variant.

In conclusion, the anchor-runner pointer strategy provides an effective and efficient method for manipulating arrays in place. By utilizing two pointers, the anchor and runner, we can traverse the array and perform specific operations based on certain conditions. This strategy allows us to solve problems with improved time and space efficiency, often avoiding the need for additional data structures.

It's important to note that the specific implementation of the anchor-runner approach may vary depending on the problem requirements. Whether it involves swapping elements, writing values, or any other operation, the underlying principle remains the same: efficiently process the array by iteratively manipulating elements using the anchor and runner pointers.

Previous:  Two Pointers: Start/End
Next:  Practice: Reverse Consonants