Problem Solving Patterns

Welcome back to our blog series on problem solving in modern software engineering!

In Part 1, we explored the Frequency Counter Pattern, a powerful technique for optimizing algorithms by efficiently counting the frequency of elements. If you missed it or want a quick refresher, feel free to check it out before continuing.

In this part, we’ll be diving into another essential pattern: the Multipointer Pattern. This pattern is invaluable when dealing with scenarios where multiple elements need to be compared, searched, or traversed simultaneously. Let’s explore how it works and where you can apply it to improve your code’s efficiency.

02. Multipointer Pattern

The Multipointer Pattern is a technique used in algorithm design where multiple pointers (or iterators) are employed to traverse data structures like arrays or linked lists. Instead of relying on a single pointer or loop, this pattern uses two or more pointers that move through the data at different speeds or from different starting points.

Example Problem

Write a function called sumZero that accepts a sorted array of integers. The function should find the first pair where the sum is zero. If such a pair exists, return an array that includes both values; otherwise, return undefined.

sumZero([-3,-2,-1,0,1,2,3]) //output: [-3, 3]
sumZero([-2,0,1,3]) //output: undefined
sumZero([-4, -3, -2, -1, 0, 1, 2, 5]) //output: [-2, 2]

Basic Solution

function sumZero(arr){
    for (let i = 0; i < arr.length; i++) {
        for (let j = i+1; j < arr.length; j++) {
            if (arr[i] + arr[j] === 0) {
                console.log(arr[i] + arr[j])
                return [arr[i], arr[j]]
            }
        }
    }
}

Time Complexity - O(N^2)

Solution using Multipointer Pattern

step 1: Understand the problem
We need to find two numbers in a **sorted array that add up to zero. Since the array is sorted, we can take advantage of this order to find the solution more efficiently.

step 2: Initialize Two Pointers
Set up two pointers: one (left) starting at the beginning of the array, and the other (right) starting at the end.

Example:

Array: [-4, -3, -2, -1, 0, 1, 2, 5]
Left Pointer (L): -4
Right Pointer (R): 5

Step 3: Calculate the Sum of the Values at the Pointers
Add the values at the left and right pointers to get the sum

Sum = -4 + 5 = 1

Step 4: Compare the Sum with Zero

• If the sum is greater than zero: Move the right pointer one step to the left to decrease the sum.

Sum is 1 > 0, so move the right pointer left:

Array: [-4, -3, -2, -1, 0, 1, 2, 5]
Left Pointer (L): -4
Right Pointer (R): 2

• If the sum is less than zero: Move the left pointer one step to the right to increase the sum.

New Sum = -4 + 2 = -2
Sum is -2 < 0, so move the left pointer right:

Array: [-4, -3, -2, -1, 0, 1, 2, 5]
Left Pointer (L): -3
Right Pointer (R): 2

Step 5: Repeat the Process
Continue moving the pointers and calculating the sum until they meet or a pair is found.

New Sum = -3 + 2 = -1
Sum is -1 < 0, so move the left pointer right:

Array: [-4, -3, -2, -1, 0, 1, 2, 5]
Left Pointer (L): -2
Right Pointer (R): 2

The sum is zero, so the function returns [-2, 2].

If the loop completes without finding such a pair, return undefined.

Final Code

function sumZero(arr) {
  let left = 0;                         // Initialize the left pointer at the start of the array
  let right = arr.length - 1;           // Initialize the right pointer at the end of the array

  while (left < right) {                // Continue until the pointers meet
    const sum = arr[left] + arr[right]; // Calculate the sum of the values at the pointers

    if (sum === 0) {                    // If the sum is zero, return the pair
      return [arr[left], arr[right]];
    } else if (sum > 0) {               // If the sum is greater than zero, move the right pointer left
      right--;
    } else {                            // If the sum is less than zero, move the left pointer right
      left++;
    }
  }

  return undefined;                     // If no pair is found, return undefined
}

NOTE:
Time Complexity: O(n) – The function is efficient and scales linearly with the size of the array.
Space Complexity: O(1) – The function uses a minimal amount of additional memory.

Conclusion

The Multipointer Pattern is a powerful technique for solving problems that involve searching, comparing, or manipulating elements in a sorted data structure. By using multiple pointers that move towards each other, we can significantly improve the efficiency of algorithms, reducing time complexity from O(n²) to O(n) in many cases. This pattern is versatile and can be applied to a wide range of problems, making it an essential strategy for optimizing performance in your code.

Stay tuned for our next post, where we’ll dive into the Sliding Window Pattern another essential tool for tackling problems involving dynamic data segments. It’s an incredibly useful pattern that can help you solve even more complex challenges with ease!

The above is the detailed content of Problem Solving Patterns. For more information, please follow other related articles on the PHP Chinese website!