Multiple Pointers Examples
Some examples that make use of the “multiple pointers pattern” or “multiple pointers approach.”
sumToZero(xs)
Write a function which accepts a sorted array of integers and returns the first pair where the sum is 0.
Return the pair in an array (like a tuple) or undefined if such a pair is not found.
Unit Tests
Unresolved include directive in modules/ROOT/pages/problem-solving-patterns/multiple-pointers-examples.adoc - include::example$src/05-problem-solving-patterns/sumToZero.test.ts[]v1 nested loops
This is a naive solution where we perform a loop inside a loop, therefore \(O(n^2)\). Start at the first element and check with all remaining elements. Then, start with the second element and again check with all remaining elements. And so on and so forth.
TIME COMPLEXITY: \(O(n²)\) because we have a nested loop.
SPACE COMPLEXITY: \(O(1)\) because we don’t use extra space besides
the i and j variables.
Unresolved include directive in modules/ROOT/pages/problem-solving-patterns/multiple-pointers-examples.adoc - include::example$src/05-problem-solving-patterns/sumToZero-v1.ts[]v2 multiple pointers
This solution relies on the fact that the input array is sorted. Using multiple pointers is more performant because it will do a single loop (\(O(n)\)) instead of a two/nested loops (\(O(n^2)\)).
TIME COMPLEXITY: \(O(n)\) because we iterate over the array a single time.
SPACE COMPLEXITY: \(O(1)\) because we don’t use extra space besides the i, j and sum variables.
Unresolved include directive in modules/ROOT/pages/problem-solving-patterns/multiple-pointers-examples.adoc - include::example$src/05-problem-solving-patterns/sumToZero-v2.ts[]| 1 | Handles the case where the logic inadvertently compares the sum of 0 + 0 === 0.
It could happen if no other pair matches a sum of 0 but we have a 0 in the array, and the indexes in loop are the same for the left and right pointers.
So, if for example we have the list We may have a pair |
| 2 | Return the pair here if found.
Also note that there is an implicit return undefined at the end of the function in case it doesn’t return because of some other condition. |
Do note the else if and else conditions.
If we get a sum less then 0, we increment the left pointer, and if the sum is greater than 0, then we decrement the right pointer.
That is the clever part of this solution which enables it to loop only once (linear time complexity).
Count Unique Values
Implement a function called countUniqVals, which accepts a sorted array of integers and counts the unique values in the array.
|
The solutions below rely on the fact that the input is sorted. |
Unit Tests
Unresolved include directive in modules/ROOT/pages/problem-solving-patterns/multiple-pointers-examples.adoc - include::example$src/05-problem-solving-patterns/countUniqVals.test.ts[]v1 loop with single pointer and counter
TIME COMPLEXITY: \(O(n)\). The entire input is iterated once.
SPACE COMPLEXITY: \(O(1)\). No new array is necessary to hold processed information. Just a few control variables are necessary.
Unresolved include directive in modules/ROOT/pages/problem-solving-patterns/multiple-pointers-examples.adoc - include::example$src/05-problem-solving-patterns/countUniqVals-v1.ts[]| 1 | This solutions uses only one pointer i explicitly.
The other pointer is computed from the pointer i.
Since the array of numbers is sorted, we know for sure that if [i] !== [i + 1] then we have a new different value, and that equal values are always siblings (given the fact that the input is sorted). |
| 2 | Also, this solution compares [i] with undefined if the input contains only a single number because then [i + 1] will be undefined. |
We could return 1 if nums.length was 1, so we would only enter the loop in case we are sure to have at least two values in the array and that comparison with undefined would not happen.
v2 single loop and two pointers
TIME COMPLEXITY: \(O(n)\). We have to iterate once through the entire input.
SPACE COMPLEXITY: \(O(1)\). We do not create a new array that grows as the input grows. Just a few control variables are necessary.
Unresolved include directive in modules/ROOT/pages/problem-solving-patterns/multiple-pointers-examples.adoc - include::example$src/05-problem-solving-patterns/countUniqVals-v2.ts[]This solution involves changing the array and moving all the different
unique values one after the other to the beginning (left side) of the
array.
When the loop stops, i is at the position of the largest and last unique value found.
| 1 | This solution doesn’t attempt to compare with undefined because we
are looping and checking j, which already starts at 1.
If the input has length 1, then j (which starts at 1) is not less than nums.length and we don’t compare numbers against undefined. |
| 2 | We do not need to swap the elements.
In this case, we don’t care about the state of the array after the computation is performed.
We just want the number of unique values.
It is enough to move [j] to the place of updated [i]. |
| 3 | Because arrays start at index 0, and i stops at the last element that was different, we have to add 1 to it to return the correct result. |
Basically what we return is the length of the portion of elements that were moved to the beginning of the array.
In short, this solution involves turning something like this:
[1, 1, 2, 3, 3, 3, 4, 4, 5, 5, 5]into:
[1, 2, 3, 4, 5, n, n, n, n, n, n]
↑The index of the last unique element after the rearranging. We return that index (the index 4, not the value at that index) plus 1.
|
Remember that simply overriding an element at a given index is \(O(1)\) (linear time) as no shifting of elements is necessary. |
areThereDups()
Implement a function called areThereDups which accepts a variable number of arguments, and checks whether there are any duplicates among the arguments passed in.
Unit Tests
Unresolved include directive in modules/ROOT/pages/problem-solving-patterns/multiple-pointers-examples.adoc - include::example$src/06-challenges/areThereDups.test.ts[]v1
TIME COMPLEXITY: \(O(n)\). The algorithm potentially iterates over the whole input.
SPACE COMPLEXITY: \(O(1)\). Just a few numeric variables are used to control the flow.
Unresolved include directive in modules/ROOT/pages/problem-solving-patterns/multiple-pointers-examples.adoc - include::example$src/06-challenges/areThereDups-v2.ts[]v2
|
This solution doesn’t work well with Node because of some Looks like if we change the to |
Unresolved include directive in modules/ROOT/pages/problem-solving-patterns/multiple-pointers-examples.adoc - include::example$src/06-challenges/areThereDups-v3.ts[]avgPair()
Given a sorted array of integers and a target average, write a function avgPair to determine if there is a pair of values in the array where the average of the pair equals the target average.
There may be more than one pair that matches the average target.
Unit Tests
Unresolved include directive in modules/ROOT/pages/problem-solving-patterns/multiple-pointers-examples.adoc - include::example$src/05-problem-solving-patterns/avgPair.test.ts[]v1
TIME COMPLEXITY: \(O(n)\). The input is iterated once.
SPACE COMPLEXITY: \(O(1)\). Only two primitive-valued variables are created.
If the average on the current iteration is less than the target average, the left pointer is incremented, otherwise, the right pointer is decremented.
Unresolved include directive in modules/ROOT/pages/problem-solving-patterns/multiple-pointers-examples.adoc - include::example$src/05-problem-solving-patterns/avgPair-v1.ts[]isSubSeq()
Write a function called isSubSeq which takes in two strings and checks whether the characters in the first string form a subsequence of the characters in the second string.
In other words, the function should check whether the characters in the first string appear somewhere in the second string, without their order changing.
Unit Tests
Unresolved include directive in modules/ROOT/pages/problem-solving-patterns/multiple-pointers-examples.adoc - include::example$src/05-problem-solving-patterns/isSubSeq.test.ts[]v1
TIME COMPLEXITY: \(O(n + m)\).
Only a single while loop is used, but there are updates to l and r that may cause one to stop and the other to keep going and vice-versa.
SPACE COMPLEXITY: \(O(1)\). No extra copies to store strings are required. Only a few control variables.
Unresolved include directive in modules/ROOT/pages/problem-solving-patterns/multiple-pointers-examples.adoc - include::example$src/05-problem-solving-patterns/isSubSeq-v1.ts[]| 1 | If the end of sub is reached it means a subsequence has successfully been found. |
| 2 | If a matching pair of chars has been found, increment both pointers so the next pair of characters can be checked next. |
| 3 | If a match is not found during this iteration, it means a char in str which matches the current char in seq is yet to be found.
Therefore, only r is increment so str is kept being searched further ahead. |
v2
This solution is the one from the instructor. I just renamed some variables in a more meaningful, self-documenting way.
TIME COMPLEXITY: \(O(n + m)\).
SPACE COMPLEXITY: \(O(1)\).
Unresolved include directive in modules/ROOT/pages/problem-solving-patterns/multiple-pointers-examples.adoc - include::example$src/05-problem-solving-patterns/isSubSeq-v2.ts[]This algorithm is cleverer than my previous one because it increments the pointers at more specific locations, requiring less code (making it more concise and elegant) and also the checks are performed in a more natural order.
For instance, my previous solution returns true as the first thing
inside the loop and then increments stuff.
This solution is more natural — it first checks, increments idxSub and then checks if we got the end of sub.
Also, it does not need an else clause.
Very well designed solution indeed!