Two-pointer algorithm

The two-pointer technique is a popular algorithmic strategy that involves using two pointers to traverse a data structure, such as an array.

By sorting the array and using two pointers, one starting at the beginning and the other at the end, we can efficiently find pairs of numbers that meet a specific condition, in this case, summing to a target value.

The two pointer method has a time complexity of O(n)

---

Arrays are used to store multiple values in a single variable.

Each value is called an element, and each element has a numeric position in the array, known as its index.

Arrays are zero-indexed, meaning the first element is at index 0, the second at index 1, and so on.

Arrays can contain any data type, including numbers, strings, and objects.

const arr1 = [2, 4, 6]; array

arr1[0]; element at index 0 → 2

arr1[1]; element at index 1 → 4

arr1[2]; element at index 2 → 6

arr1[3]; element at index 3 → undefined index not found

---

Numbers are used to represent both integer and floating-point values.

Numbers are most commonly expressed in literal forms like 255 or 3.14159 ↴

let num1 = 5; → number

let num2 = 2.5; → number

let num3 = num1 + num2;

console.log(num3); returns ↴

7.5 → number

---

Check whether any two numbers will sum up to a given number using ↴

---

map() method → creates a new array from calling a function for every array element.

sort() method → sorts the elements of an array in place and returns the reference to the same array, now sorted.

while loop → repeatedly executes a block of code as long as a specified condition evaluates to true.

length property → set or return the number of elements in an array.

---

map() method creates a new array populated with the results of calling a provided function on every element in the calling array. The original array is unchanged.

const arr2 = [5, 10, 15, 20];

arr2.map((x) => x + 10); returns ↴

[15, 20, 25, 30] → 10 added to each element

---

sort() method sorts the elements of an array as strings.

By default, the elements of the array are converted to strings and sorted in ascending order by comparing their sequences based on their UTF-16 code unit values.

sort() method returns a reference to the original array, so mutating the returned array will mutate the original array as well.

sort() method is stable, it preserves the order of items in an array when their values are the same.

sort() method can sort an array of numbers, strings, or objects with custom functions.

syntax

array.sort()

By default the sort() method sorts the array in ascending order with the elements converted to strings.

This can lead to unexpected results when sorting arrays of numbers.

const arr2 = [2, 11, 1, 22, 33, 3];

arr2.sort(); returns ↴

[1, 11, 2, 22, 3, 33] NOT sorted accurately

To solve this limitation, a comparison callback function can be used to define the desired sorting order.

callback function a function passed into another function as an argument, which is then invoked within the outer function.

When sorting numbers, always use a compare function to ensure numerical comparison.

---

For sorting an array of numbers in ascending order, the comparison function should subtract the second number from the first number.

syntax

array.sort(compareFunction)

comparison function

(a, b) => a - b compares two elements ↴

a and b

a - b calculates the difference between the two numeric values ↴

If the result is ↴

negative → a sorted before b

positive → a sorted after b

zero → order remains unchanged

const arr3 = [2, 11, 1, 22, 33, 3];

arr3.sort((a, b) => a - b); returns ↴

[1, 2, 3, 11, 22, 33] → ascending order

The comparison function can be changed to sort in descending order by swapping the elements for comparison to b - a

const arr4 = [2, 11, 1, 22, 33, 3];

arr4.sort((a, b) => b - a); returns ↴

[33, 22, 11, 3, 2, 1] → descending order

---

while loop repeatedly executes a block of code as long as a specified condition evaluates to true.

while (condition) {

// execute code as long as condition is true

}

let x = 0; → counter

while (x < 4) {

console.log(x);

x++;

}

Initialize a counter variable x outside of the loop.

Condition x < 4 is checked before each iteration.

The loop will continue to run as long as x is less than 4

The loop repeatedly executes a block of code 4 times, from 0 to 3

For each iteration of the loop, the current value of x is printed to the console.

After each iteration, x is incremented by 1 x++

When x reaches 4 the condition evaluates to false, terminating the loop.

0

1

2

3 → printed to console

---

length property returns the number of elements in an array.

const arr = [1, 2, 3, 4, 5, 6];

arr.length; returns ↴

6 → there are 6 elements in the array

Arrays are zero indexed, the first element will be index 0

The last element will be at index length -1

To find the last index in an array.

const arr2 = [1, 2, 3, 4, 5, 6];

arr2.length - 1; returns ↴

5 → end index of array

---

Initialize an array to check if any two elements will sum up to a given number.

const array1 = [5, 10, 2, 6, 4, 3, 8]; → user input

Initialize a variable to hold the target sum to check against.

const number1 = 9; → user input

---

Define a function twoSumTwoPointer to check whether any two numbers will sum up to a given number.

The function takes an array nums and a number target as input and returns the indices any two numbers in the array sum up to the given number, otherwise returns null.

Inside the function, the array is transformed into a sorted array of pairs, where each pair contains the number and its original index.

Two pointers (left and right) are initialized to traverse the sorted array.

A while loop checks the sum of the elements at the two pointers, adjusting the pointers based on the comparison with the target

Create an array of pairs [number, index] and sort it by number.

Initialize two pointers.

Loop until the two pointers meet.

while (left < right)

Calculate the sum of the values at the two pointers.

const sum = sortedIndices[left][0] + sortedIndices[right][0]

Check if the sum matches the target.

if (sum === target) {}

If true, return the original indices of the two numbers.

If false, check if sum is still less than target.

else if (sum < target)

If the sum is less than the target, move the left pointer to the right.

left++ Increment by 1

else if the sum is greater than the target, move the right pointer to the left.

right-- Decrement by 1

Return null if no valid pair is found

return null

If the function returns an array then two numbers have been found that sum up to a given number ✔

If the function returns null then two numbers were not found that sum up to a given number ✖

---

Check whether any two numbers will sum up to a given number.

const arr = [5, 10, 2, 6, 4, 3, 8] → array

const target = 9 → number to sum up to

Map each number to an array containing the number and its index.

returns ↴

[2, 2] → element 2 at index 2

[3, 5] → element 3 at index 5

[4, 4] → element 4 at index 4

[5, 0] → element 5 at index 0

[6, 3] → element 6 at index 3

[8, 6] → element 8 at index 6

[10, 1] → element 10 at index 1

map() function iterates over arr, creating a new array where each element is an array itself, containing the number and its index.

For example, the number 3 at index 5 becomes [3, 5]

sort() function takes two parameters, a and b which represent the elements being compared.

The expression a[0] - b[0] sorts the pairs based on the first element (the number) in ascending order.

The array is now sorted.

[2, 3, 4, 5, 6, 8, 10]

let left = 0

let right = sortedIndices.length - 1

sortedIndices[left][0] → 2

sortedIndices[right][0] → 10

Calculate the sum of the values at the two pointers.

const sum = sortedIndices[left][0] + sortedIndices[right][0];

if (sum === target) check if sum of the elements is the target value

First iteration ↴

2 + 10 === 9 → evaluates to false ✖

if (sum < target)

(2 + 10) < 9 → evaluates to false ✖

If the sum is greater than the target, move the right pointer to the left

Decrement right by 1

Second iteration ↴

2 + 8 === 9 → evaluates to false ✖

if (sum < target)

(2 + 8) < 9 → evaluates to false ✖

If the sum is greater than the target, move the right pointer to the left

Decrement right by 1

Third iteration ↴

2 + 6 === 9 → evaluates to false ✖

if (sum < target)

(2 + 6) < 9 → evaluates to true ✔

If the sum is less than the target, move the left pointer to the right

Increment left by 1

Fourth iteration ↴

3 + 6 === 9 → evaluates to true ✔

Return the original indices of the two numbers.

The function returns the array [5, 3]

---

Call the function with ↴

twoSumTwoPointer(array1, number1);

---

Check whether any two numbers will sum up to a given number.