Two Pointer Technique
Top companies typically would hire you for your demonstrated problem-solving abilities. A less experienced engineer is chosen over one who is more experienced. What skill makes one stand out? How well you can solve a problem and not how many problems you have solved. Algorithms are what big tech companies like Google use to test problem-solving proficiency. You can show your world-class abilities by learning about the Two Pointer Technique, the first in a series of algorithm fundamentals. We discuss saving time and space using an optimized algorithm with the best performant big-O notation.
Two pointer technique involves using two array indexes in a sorted array. The aim is to save time and space. Typically placed at the two ends of an array, it finds pairings in optimized time. A typical question would look like this:
Example: In an unsorted array, find if a pair exists with a given sum targetSum.
A typical brute force approach would be to create a function and have a nested for loop where we compare pairs:
pairExists(array, targetSum) {
for(let i = 0; i < array.length -1; i++){
let firstNumber = array[i];
for(let j = i + 1; j < array.length; j++){
let secondNumber = array[j];
if(firstNumber + secondNumber === targetSum){
return [firstNumber, secondNumber];
}
}
}
}
The above nested for loop approach would lead to an O(n^2) time complexity because we iterate twice in our algorithm. And while this might work, it is not optimal when we increase the size of the array to a million.
Two Pointer Technique examples
Two Number Sum:
Write a function that takes an unsorted array of distinct integers and an integer representing a target sum. If any two numbers sum up to the target sum, they are returned in an array. If no two integers sum up to the target sum, an empty array is returned.
Key points:
- unsorted array
- distinct integer
- target sum
// o(nlog(n)) | o(1) space
function twoNumberSum(array, targetSum) {
array.sort((a, b) => a - b);
let left = 0;
let right = array.length - 1;
while(array[left] < array[right]){
const currentValue = array[left] + array[right];
if (currentValue === targetSum ){
return [array[left], array[right]]
}
else if (currentValue < targetSum){
left++;
}
else if (currentValue > targetSum){
right--;
}
}
return [];
}
First, we sort the array in O(N*log(N)), which is far better than O(n^2) in the brute force approach. Refer to this article for more information.
Then we set our pointer variables and call them left and right. We iterate from the beginning of the array at index 0 and the end of the array at array.length -1 and move the left pointer forward if we get a value lesser than the target sum and the right pointer if we get a value greater than the target sum.
Two pointer algorithm typically uses just a loop to iterate and compare values! Compared to the brute force approach of nested loops, this is quite optimal.
The while loop iterates in an O(n) time and O(1) space complexity (it doesn't create another array to check values).
Complexity
Finally, we can say our two number sum algorithm runs in O(N*log(N)) time and O(1) space algorithm because the array sort function is the highest time complexity our algorithm performs.
Three-Number Sum:
Write a function that takes an unsorted array of distinct integers and an integer representing a target sum. The function should find three numbers in the array whose sum equals the target sum. It should return a two-dimensional array sorted in ascending order per array. It should return an empty array if no three numbers that equal the target sum is found.
Key points:
- unsorted array
- distinct integer
- target sum
- return two-dimensional arrays sorted in ascending order
- return empty numbers do not sum up to the target sum
// o(n^2) time | o(n) space
function threeNumberSum(array, targetSum) {
array.sort((a,b) => a - b);
let tripleValueArray = [];
for (let i = 0; i < array.length - 2; i++) {
let leftNumber = i + 1;
let rightNumber = array.length - 1;
while (leftNumber < rightNumber) {
let currentNumber = array[i] + array[leftNumber] + array[rightNumber];
if (currentNumber === targetSum) {
tripleValueArray.push([ array[i], array[leftNumber], array[rightNumber] ]);
leftNumber++;
rightNumber--;
} else if (currentNumber < targetSum) {
leftNumber++;
} else if (currentNumber > targetSum) {
rightNumber--;
}
}
}
return tripleValueArray;
}
First, we sort the array in O(N*log(N)), which is far better than O(n^3) in a brute force approach of three for loops nested in themselves.
Next, we use for (let i=0; i < array.length - 2; i++) in our loop because we always want two extra values to check with and not iterate over. Remember pointer position for a three number sum would look like this:
[-8, -6, 1, 2, 3, 5, 6, 12]
Where -8 would be the starting current number, -6 the starting left number and 12 the starting right number. We move the left pointer if the addition of all three values is less than the target sum and the right pointer to the right if it is greater than the target sum.
Remember, the array is sorted so moving from left to right or right to left increases or decreases sum value respectively. The sum of -8+(-6)+12 = -2. But if we move the left pointer from -6 to 1 and sum -8+1+12 = 5. A bigger number! Similarly, moving the right pointer from -12 would result in -8+(-6)+6 = -8. A much smaller number.
The only condition when we move both pointers towards the middle is if the sum of all three values equals the target sum if (currentNumber === targetSum). We use the conditions:
leftNumber++; and rightNumber--; to break out of the while loop. We then return whatever is pushed into tripleValueArray. If nothing is pushed, we return it because it is declared as an empty array.
Complexity
The time complexity for our three number sum is O(N^2) because we have two loops, an outer for loop and inner while loop in the algorithm.
The space complexity is O(N) because it is created in constant time. Although, we cannot tell the size of our tripleValueArray.
Four-Number Sum
Write a function that takes an unsorted array of distinct integers and an integer representing a target sum. The function should find four numbers in the array whose sum equals the target sum. It should return a two-dimensional array in no particular order. It should return an empty array if no four numbers that equal the target sum is found.
// o(n^2) time | o(n^2) space
function fourNumberSum(array, targetSum) {
const temporaryPairSum = {};
const quadruplet = [];
for (let i=1; i < array.length - 1; i++){
for(let j = i+1; j < array.length; j++){
let currentSum = array[i] + array[j];
let difference = targetSum - currentSum;
if ( difference in temporaryPairSum){
for (const arrayPair of temporaryPairSum[difference]){
quadruplet.push(arrayPair.concat([array[i], array[j]]))
}
}
}
for (let k=0; k < i; k++){
let currentSum = array[k] + array[i];
if(!(currentSum in temporaryPairSum)){
temporaryPairSum[currentSum] = [[array[k], array[i]]];
} else {
temporaryPairSum[currentSum].push([array[k], array[i]]);
}
}
}
return quadruplet;
}
We use a hash table to store pair values. For this algorithm, we start our outer for loop from index 1 and iterate to array.length - 1 index. The inner for loop of the equation also start from index 1 + 1 position. But why do we do this?
We want to prevent duplication of values so we skip saving anything in our hash table temporaryPairSum during the first iteration. We only save values when we iterate the second time from index 0 while comparing the values with whatever is currently in the array index "i" as shown in this part of the equation
for (let k=0; k < i; k++).
Remember we skipped the first value in our outer for loop by starting at array index 1 here for (let i=1; i < array.length - 1; i++).
Next, we solve for the additional two arrays in the multidimensional array and subtract them from the target sum. We then check if the difference already exists in the hash table
const difference = targetSum - currentSum;
if ( difference in temporaryPairSum)
If it does, then congratulation! We push the two array values, add them to our quadruplet multidimensional array.
The second part of the inner for loop is where the "difference" referred to is added. Pay close attention here!
We iterate starting from index 0 to where the iteration of the outer for loop is currently for (let k =0; k < i; k++). Then we check if we have initialized the sum of two array pairs (referred to as difference in the outer for loop. If it is not initialized, we do so here:
allPairSum[currentSum] = [[array[k], array[i]]];
Please note that our hash table uses the sum of two array pairs as key and a multidimensional array as value. This helps to track duplicates that can be found in the iteration. For example, our hash table with duplicates would look like this assuming 17 is the target sum difference:
{
17: "[ [array[k], array[i]], [array[k], array[i]] ]"
}
Where duplicates would be a different arrangement of the same values.
7 + 10 = 17 and 10 + 7 = 17:
{
17: "[ [10, 7], [7, 10] ]"
}
We push the duplicate to the hash table using this line
allPairSum[currentSum].push([array[k], array[i]]);
The quadruplet multidimensional array is returned at the end of the algorithm. It can also be an empty array if no quadruplet is found.
Complexity
The average time complexity analysis for this is O(2N^2) which then evaluates to O(N^2). This is because, in big-O scaling, the constant of N which in this is 2 is irrelevant. The major complexity comes from the unknown size of N. The worst-case scenario for the algorithm is O(N^3).
You might also be wondering why we have just O(N^2) complexity after having about 4 for loops? This is because 2 of the inner for loops, starts just before or after the starting index of the outer for loop. If you look closely, the first inner for loop starts an index next to the outer for loop for(let j = i+1; j < array.length; j++) and the last for loop of the equation for (let k=0; k < i; k++) starts just before the outer for loop. These types of for loops evaluates to O(2N). We get O(2N^2) = O(N^2) by adding the time complexity of the outer for loop. For the worst-case scenario O(N^3), it is the time complexity used to iterate through pair duplicates in the hash table for (const arrayPair of temporaryPairSum[difference]).
The space complexity is O(n^2) as you never really know the space the hash table or the quadruplet multidimensional array might take.
To read up on Big-O notation check out this article. For further reading, please visit this link.
Top comments (2)
Thank you very much for this article.
Do we really need to sort the array can't we search for targetSum-arr[I] ?