Two Pointers: Start-End

The start-end pointer strategy is a powerful optimization technique commonly used for solving problems on sorted arrays. By utilizing two pointers, one starting at the beginning (start pointer) and the other starting at the end (end pointer), we can efficiently navigate the array and optimize our solution. In this assignment, we will explore the start-end pointer strategy, understand how it works, and apply it to solve a specific problem.

To effectively use the start-end pointer strategy, we need to answer several key questions:

1. When should I move the start pointer?
2. When should I move the end pointer?
3. Does the start pointer do something besides moving?
4. Does the end pointer do something besides moving?
5. Under which condition do we stop the iteration?

Understanding the answers to these questions will provide a solid framework for using the start-end pointer strategy. This technique frequently allows us to achieve linear time complexity O(N).

Example Problem

Let's use the "Two Sum" problem to demonstrate how the start-end pointer strategy works in practice.

// Given a sorted array in ascending order, our task is to find two numbers
// in the array that sum up to a target number, and return them.

// If you don't find a pair that adds up to the target, return null.

// The order of the output array matters, and the number that appears first
// should be the first one in the output array.

// The problem guarantees that there will be either one
// unique pair that matches the target sum or no pairs at all.

// Test Cases:

const nums1 = [1, 3, 6, 7, 8, 12];
const target1 = 14;
console.log(findPair(nums1, target1)); // Output: [6, 8]

const nums2 = [2, 6, 8, 10];
const target2 = 17;
console.log(findPair(nums2, target2)); // null

Brute-force Approach

Before diving into the start-end pointer approach, let's first examine a naive (brute-force) solution to the problem. One possible solution is to use nested loops to check all possible pairs of numbers in the array and find the desired sum. However, this approach would result in a time complexity of O(N^2), which is not efficient.

function findPair(nums, target) {
  const length = nums.length;

  for (let firstIdx = 0; firstIdx < length - 1; firstIdx++) {
    for (let secondIdx = firstIdx + 1; secondIdx < length; secondIdx++) {
      let currentSum = nums[firstIdx] + nums[secondIdx];
      if (currentSum === target) {
        return [nums[firstIdx], nums[secondIdx]];
      }
    }
  }

  return null;
}

// Test cases
const nums1 = [1, 3, 6, 7, 8, 12];
const target1 = 14;
console.log(findPair(nums1, target1)); // Output: [6, 8]

const nums2 = [2, 6, 8, 10];
const target2 = 17;
console.log(findPair(nums2, target2)); // null

Start-end Pointer Approach

Now, let's see how we can use the start-end pointer strategy to solve this problem more efficiently. We will follow a step-by-step process, considering the questions mentioned earlier. Keep in mind that this approach works for this problem because the array we're given is sorted.

Questions to Answer:

1. When should I move the start pointer? - We move the start pointer to the right (increment it) when the sum of the numbers at the start and end pointers is less than the target.

2. When should I move the end pointer? - We move the end pointer to the left (decrement it) when the sum of the numbers at the start and end pointers is greater than the target.

3. Does the start pointer do something besides moving? - After we move the start pointer we use the value at its position to calculate the new pair sum.

4. Does the end pointer do something besides moving? - After we move the end pointer we use the value at its position to calculate the new pair sum.

5. Under which condition do we stop the iteration? - We stop the iteration when we find our target number, or when the start and end pointers meet, indicating that there is no valid solution.

Walkthroughs

Walkthrough I

Let's do a detailed walkthrough of the solution using the first test case from above, the array [1, 3, 6, 7, 8, 12], and the target 14.

Step 1: First, we initialize two pointers, start (s) at index 0 and end (e) at index 5. Next, we calculate the current sum of elements at the start and end pointers. Since this sum is less than the target sum, we advance the start pointer (s).

Step 2: In this step, the sum of numbers at start and end indices is 15. This is greater than the target. Since the sum is greater than the target sum, we decrement the end pointer (e).

Step 3: Once again, we calculate the sum of numbers, finding it to be 11. This is less than the target of 14. As before, we increment the start pointer (s).

Step 4: In the final step, the sum of elements at the start and end pointers is 14, equal to the target number. We've found the correct pair and we can return it.

Walkthrough II

Next, we'll do another walkthrough using the second test case with the array [2, 6, 8, 10] and the target 17.

Step 1: Firstly, we initialize two pointers, start (s) at index 0 and end (e) at index 3. Next, we calculate the current sum of elements at the start and end pointers. Since this sum is less than the target sum, we advance the start pointer (s).

Step 2: In this step, the sum of numbers at start and end indices is 16. This is still less than the target. Since the sum is less than the target sum, once again, we increment the start pointer (s).

Step 3: Once again, we calculate the sum of numbers, finding it to be 18. This is greater than the target of 17. In this case, we decrement the end pointer (e).

Step 4: In the final step, we've reached the case where the start pointer is equal to the end pointer. This means that we haven't found a valid pair and that we'll return null.

Solution Code

You can find the final solution code below.

function findPair(array, target) {
  let start = 0;
  let end = array.length - 1;

  while (start < end) {
    const currentSum = array[start] + array[end];
    if (currentSum === target) {
      return [array[start], array[end]];
    } else if (currentSum < target) {
      start++;
    } else {
      end--;
    }
  }
  return null;
}

// Test cases
const nums1 = [1, 3, 6, 7, 8, 12];
const target1 = 14;
console.log(findPair(nums1, target1)); // Output: [6, 8]

const nums2 = [2, 6, 8, 10];
const target2 = 17;
console.log(findPair(nums2, target2)); // null