Multiple Pointers Pattern Algorithm in TypeScript

The Multiple Pointers pattern is a technique used in solving problems by maintaining multiple pointers or references to elements in a data structure and manipulating those pointers to solve the problem more efficiently. This pattern is particularly useful for optimizing time complexity, especially in scenarios where brute-force solutions might be less efficient.

Understanding the Multiple Pointers Pattern

In the Multiple Pointers pattern, you typically use two or more pointers that traverse through the data structure, moving towards each other, or in some cases, moving in the same direction but at different speeds. The goal is to efficiently search for a pair, sequence, or pattern within the data.

Let's explore a simple example of the Multiple Pointers pattern in TypeScript. Consider a problem where you need to find a pair of numbers in a sorted array that adds up to a specific sum:

In this example, the findPairWithSum function uses two pointers, leftPointer and rightPointer, to efficiently search for a pair with the target sum in a sorted array.

function findPairWithSum(arr: number[], targetSum: number): [number, number] | null {
    let leftPointer = 0;
    let rightPointer = arr.length - 1;

    while (leftPointer < rightPointer) {
      const currentSum = arr[leftPointer] + arr[rightPointer];

      if (currentSum === targetSum) {
        return [arr[leftPointer], arr[rightPointer]];
      } else if (currentSum < targetSum) {
        leftPointer++;
      } else {
        rightPointer--;
      }
    }

    return null; // Pair not found
  }

Benefits of the Multiple Pointers Pattern

Improved Time Complexity

The Multiple Pointers pattern often leads to more efficient algorithms, especially when compared to brute-force solutions with nested loops.

Reduced Space Complexity

By manipulating pointers in-place, this pattern can also lead to algorithms with lower space complexity.

Simplified Logic

The pattern often results in cleaner and more readable code by breaking down complex problems into simpler steps.

Conclusion

The Multiple Pointers pattern is a powerful technique for optimizing algorithms in TypeScript. It is particularly useful for solving problems involving arrays, strings, or linked lists where maintaining multiple pointers can lead to more efficient solutions. Understanding and applying this pattern can significantly enhance your problem-solving skills in the realm of data structures and algorithms.

Alternate Method

function countUniqueValues(arr: number[]): number {
  if (arr.length === 0) return 0;

  let uniquePointer = 0;
  let scoutPointer = 1;

  while (scoutPointer < arr.length) {
    if (arr[uniquePointer] !== arr[scoutPointer]) {
      uniquePointer++;
      arr[uniquePointer] = arr[scoutPointer];
    }
    scoutPointer++;
  }
  return uniquePointer + 1;
}