Multiple Pointers

March 29, 2022

Another powerful software design pattern is that of the Multiple Pointers pattern.

The Multiple Pointers pattern is defined by creating pointers or values that correspond to an index or position and move towards the beginning, end, or middle based on certain criteria. This pattern is most commonly used over a linear data structure (e.g. array, string, linked list, ... ). Utilizing this pattern can drastically reduce the space complexity of your solution!

Implementation

To understand the multiple pointers pattern implementation, lets first look at the problem Are There Duplicates,

            
/**
 * Implement a function called, areThereDuplicates which accepts a variable
 * number of arguments, and checks whether there are any duplicates among the
 * arguments passed in.
 *
 * Solution must be O(n)
 *
 * areThereDuplicates(1,2,3) // false
 * areThereDuplicates(1,2,2) // true
 */

This is a perfect problem to solve using multiple pointers! We will define pointers l = 0 and r = arguments.length-1 which point to the start and end of the arguments array respectfully. Then we can loop while l < r checking at each iteration if arguments[l] === arguments[r] in which case we would return true. Else if arguments[l] < arguments[r] we add 1 to pointer l, else subtract 1 from pointer r. Here is an implementation of a solution using this design pattern, our time complexity is O(n), space complexity is O(1),

                
                  function areThereDuplicates() {
                    let l = 0;
                    let r = arguments.length;
                    while (l < r) {
                      if (arguments[l] === arguments[r]) {
                        return true;
                      } else if (arguments[l] < arguments[r]) {
                        l++;
                      } else {
                        r--;
                      }
                    }
                    return false;
                  }

Use Cases

When you need to search for values in a linear data structure under a certain condition
When space complexity for a solution must be minimized

Code Challenges

Listed below are some of the coding challenges that can be solved using the multiple pointers pattern. Linked are solutions to each problem on my GitHub. I recommend trying to solve each problem with out looking at the solution first. Good luck!

Developer Blog

💻💡🧠⚙️