Author: Theodore Odeluga
The source files for this project can be downloaded from here
This is a Node command line project and Node.js can be downloaded from here
Instructions for running a command line program with Node.js can be found here
In this type of pattern, two or more pointers check through a series of values to find a solution.
Pointers, to all intents and purposes, are really just iterators that traverse data structures to find specific values or positions in the structure.
For instance, a pointer could be used to find a specified node in a linked list or a selected element in a two-dimensional or one-dimensional array.
In the two-pointer sum problem and the palindrome validity test for example, two pointers would start at different positions in a data structure and move through the data to “seek out” multiple values or a single value.
Problem 1: Find two numbers in a sorted array that add up to a target
Here, an arbitrary amount is the sum of a pair of presently unknown numbers.
These numbers reside somewhere inside the array.
The numbers are to be found by the two iterators, j and k, moving through the array from opposite ends.
J is initialized with the value of the array’s size and iterates “backward” through its elements from right to left, decrementing its array index value with each step, while I starts out at zero and increments the index value of its position as it moves in the opposite direction.
Both iterators will eventually converge and each find one of the two numbers required for the sum total in the target.
//Problem: Find two numbers in a sorted array that add up to a target
let sample = [20,31,42,53,64,75]; //Target: 95
let target = 95;
let i;
let j = sample.length;
let k = -1; //Traverse (all) array elements
for(i=0; i < sample.length; i++){
--j;
sample[j];
k++;
sample[k];
}
if(sample[j] + sample[k] == target){
console.log(sample[j] + " , " + sample[k]);
}
Problem 2: Test if a word is a palindrome
Here, the task of the two pointers is to ascertain if a string is a palindrome.
By following a similar algorithm to the one described above, j and k test for the “symmetrical” characteristic of a word-based palindrome.
If the left to right reading of the word “mirrors” the reading from right to left, the word can be considered palindromic. The code below (along with comments) describes the process.
let righttoleft = [];
let lefttoright = [];
let sample = ['racecar'];
let capture_original_string = sample.toString();
let splitit = capture_original_string.split("");
//Capture length of original string
let j = splitit.length; //Iterate right-left
let k = -1; //Iterate left-right
/* Read length of string
from right to left
and left to right.
Push results
into the arrays
righttoleft and
lefttoright.*/
for(i=0; i < capture_original_string.length; i++){
--j;
righttoleft.push(capture_original_string[j]);
k++;
lefttoright.push(capture_original_string[k]);
}
/*Set both arrays to strings ('strings as
as strings' rather than arrays as strings)*/
leftstring = lefttoright.toString();
rightstring = righttoleft.toString();
/*Remove commas from both strings (characteristic
left over from when they were treated as arrays).*/
let nocommasleft = leftstring.replace(/,/g,'');
let nocommasright = rightstring.replace(/,/g,'');
if(nocommasleft == nocommasright){
console.log(sample + " is a palindrome. ");
} else {
console.log(sample + " is not a palindrome. ");
}
Problem 3: Create a new sorted array containing squares of all the numbers from a previously inputted array
In this example, count and i are the pointers and each work separately before being brought together.
First i iterates through the elements of the inputarray object, multiplying each contained value with itself before placing the results in the previously empty ‘squares’ array (while also keeping track of each updated value of ‘square’ created by each cycle of the loop).
In the sortit function, every value of every element in the ‘squares’ array is compared (for equality) to each instance of the count variable which is also increased by one at every iteration of a container loop, to ensure all elements from the ‘squares’ array move into the ‘sorted’ array in correct order.
/* Problem: Given a sorted array, create a new array containing squares of all the numbers
of the input array in the sorted order.*/
let inputarray = [6,90,75,2,10,30,11];
let squares = [];
let sorted = [];
let count = 0;
let square;
let i;
for(i=0; i < inputarray.length; i++){
square = inputarray[i] * inputarray[i];
squares.push(square);
}
function sortit() {
while(sorted.length != squares.length){
count++;
for(i=0; i < squares.length; i++){
if(count == squares[i]){
sorted.push(squares[i]);
}
}
}
}
sortit();
console.log(sorted);
Problem 4: Find a target based on a triple sum
In this problem, a third pointer (l) is used to find the difference between the target and the sum of j and k while their sum remains less than the target. Through the iteration generated by each cycle of the loop, both j and k increase by 1 at each repetition. As a result, eventually both j and k will reach their correct respective values where L can then be added as the missing (third) value to complete the sum and reach the target value.
let target = 231;
let container = [];
container = [10,11,22,33,44,55,66,77,88,99];
let i;
let j = container.length;
let k = -1;
let l;
for(i=0; i < container.length; i++){
--j;
container[j];
k++;
container[k];
}
container[l] = target - (container[j] + container[k]);
if(container[j] + container[k] + container[l] == target){
console.log(container[j] + " , " + container[k] + " , " + container[l]);
}
Problem 5: Find a target based on a two integer sum without using a loop
And to conclude, this version of the pattern simply achieves what was done with problem 1 but uses conditions rather than a loop (arguably loops are less efficient as they demand more of the CPU’s resources).
//Problem: Find two numbers in a sorted array that add up to a target
let sample = [20,31,42,53,64,75]; //Target: 95
let target = 95;
let i;
let j = sample.length;
let k = -1; //Traverse (all) array elements
if(j > sample.length || j == sample.length){
--j;
sample[j];
}
if(k < sample.length && k != k > sample.length){
k++;
sample[k];
}
if(sample[j] + sample[k] == target){
console.log(sample[j] + " , " + sample[k]);
}
Conclusion
Pointers are useful and fun to play around with. Explore this topic further with other problems; a simple Google search should find a whole list of additional challenges. I hope this has been an interesting exercise and happy coding.