MULTIPLE POINTERS PATTERN - rs-hash/Senior GitHub Wiki

2. MULTIPLE POINTERS PATTERN

• Direction: The pointers can move towards each other (e.g., one starts at the beginning, the other at the end) or independently in any direction based on conditions.
• Two Pointers: Often used in sorted arrays or when comparing elements in a non-overlapping manner.

• The multiple pointers pattern in programming involves using multiple pointers or indices to solve problems efficiently, typically in arrays or strings.
• This approach is particularly useful for solving problems that involve searching, finding pairs, or determining a specific sequence within a data structure.
• The main idea is to have two or more pointers (indices) that traverse the data structure in different directions or at different speeds, allowing for a more optimized solution.

Here's a general approach to handle problems using the multiple pointers pattern:

• Initialize Pointers: Determine the number of pointers needed based on the problem's requirements. Initialize these pointers to different positions within the data structure.

• Move Pointers: Based on the problem's logic, move the pointers in a specific way. This could involve advancing one pointer while keeping the other(s) stationary, moving pointers towards each other, or moving them independently based on certain conditions.

• Process Data: At each step, analyze the data or elements pointed to by the pointers. Perform comparisons, calculations, or other operations based on the problem's requirements.

• Adjust Pointers: Update the pointers based on the current state of the data or the results of processing. Continue moving and processing until the desired result is achieved or the traversal is complete.

Problem 1: Sum Zero

Description: Given a sorted array of integers, find the first pair where the sum is zero.

Input: [-4, -3, -2, -1, 0, 1, 2, 3, 10]

Output: [-3, 3]

const sumZero = (arr) => {
    let left = 0;
    let right = arr.length - 1;

    while (left < right) {
        let sum = arr[left] + arr[right];
        if (sum === 0) {
            return [arr[left], arr[right]];
        } else if (sum > 0) {
            right--;
        } else {
            left++;
        }
    }
    return false; // Return false if no pair is found
}

const input1 = [-4, -3, -2, -1, 0, 1, 2, 3, 10];
console.log(sumZero(input1)); // Output: [-3, 3]

Problem 2: Count Unique Values

Description: Count the number of unique values in a sorted array.

Input: [1, 1, 1, 2, 3, 3, 4, 5, 5, 6]

Output: 6 (unique values: 1, 2, 3, 4, 5, 6)

function countUniqueValues(arr) {
    if (arr.length === 0) return 0;

    let uniqueCount = 1; // Start with the first element being unique
    let i = 0;

    for (let j = 1; j < arr.length; j++) {
        if (arr[i] !== arr[j]) {
            uniqueCount++;
            i = j; // Move the pointer `i` to the new unique element
        }
    }

    return uniqueCount;
}

const input2 = [1, 1, 1, 2, 3, 3, 4, 5, 5, 6];
console.log(countUniqueValues(input2)); // Output: 6

Problem 3: Average Pair

Description: Given a sorted array of integers and a target average, determine if there is a pair of values that averages to the target.

Input: [1, 2, 3, 4, 5, 6], 3.5

Output: true (pair: [2, 5])

const findAvg = (arr, avg) => {
    let left = 0;
    let right = arr.length - 1;

    while (left < right) {
        let average = (arr[left] + arr[right]) / 2;
        if (average === avg) return true;

        if (average < avg) {
            left++;
        } else {
            right--;
        }
    }

    return false;
}

const input3 = [1, 2, 3, 4, 5, 6];
const targetAvg = 3.5;
console.log(findAvg(input3, targetAvg)); // Output: true (pair: [2, 5])

Problem 4: Merge Sorted Array

To merge the two sorted arrays nums1 and nums2 into nums1 in non-decreasing order, we can utilize a two-pointer technique that runs in O(m + n) time complexity. The idea is to start from the end of both arrays and fill nums1 from the end to the beginning. This approach ensures that we don't overwrite any elements in nums1 that we haven't yet processed.

function merge(nums1, m, nums2, n) {
    // Pointers for nums1 and nums2
    let p1 = m - 1;
    let p2 = n - 1;
    // Pointer for the end of nums1
    let p = m + n - 1;

    // Iterate while there are elements to be compared in nums1 and nums2
    while (p1 >= 0 && p2 >= 0) {
        if (nums1[p1] > nums2[p2]) {
            nums1[p] = nums1[p1];
            p1--;
        } else {
            nums1[p] = nums2[p2];
            p2--;
        }
        p--;
    }

    // If there are remaining elements in nums2, copy them
    while (p2 >= 0) {
        nums1[p] = nums2[p2];
        p--;
        p2--;
    }
}

5. Finding two numbers that add up to a target sum.

function twoSum(arr, target) {
    let left = 0;
    let right = arr.length - 1;

    while (left < right) {
        let sum = arr[left] + arr[right];
        if (sum === target) {
            return [arr[left], arr[right]];
        } else if (sum < target) {
            left++;
        } else {
            right--;
        }
    }

    return false;
}

console.log(twoSum([1, 2, 3, 4, 5], 7)); // Output: [2, 5]

• Checking if a list is a palindrome.
• Container With Most Water: Find the two lines that together with the x-axis form a container that holds the most water.