hey everyone today we're going to cover the two-pointer technique the two-pointer technique is a near necessity in any software developer's tool kit especially when it comes to technical interviews and the reason for this is because of how omnipresent the use of two variables pointing to different things is so we'll cover the basics so you can know when and how to use this very valuable technique and what is the two two-pointer technique well it's a technical interview pattern that you can use it is exactly as it sounds which is using two different pointers so two different variables or references to keep track of usually arrays or string indexes and the reason we keep track of these indexes using two pointers is because it saves time and space a lot of problems with strings and arrays involve the comparison of two different elements and so by referencing two at a time and iterating while referencing two at a time we're able to cut down dramatically on the number of operations that needs to occur let's take a step back what exactly are pointers well in computer science a pointer is a reference to an object in many programming languages that object stores a memory address of another value located in computer memory so that's a fancy way of saying that it's something that references something else in many cases it's as simple as a variable referencing an index but it could also be a variable that points to a node of some sort as we'll cover later or another kind of object to keep it simple just think of this visual if this were an array with elements 1 3 4 8 and 9 and we had one pointer and a second pointer imagine that these are just variables storing index zero and storing index four so when do we use two pointers well a lot of times when you have to analyze each element of a collection compared to its other elements you'll find use in having two pointers for example let's say we have an array and we want to start from the first index of the array and iterate through the data structure one or more times having another pointer gives us something to keep track of each level of the loop and it's so common because it allows us to process two elements per loop instead of just one so what we're going to explore today is two different versions two pointers each starting at the beginning and moving inwards until they meet and two pointers one slow and one fast and these patterns can be used for string or array questions or as we'll see some linked list questions as well so let's run through an example many of you will have heard of the two sum problem the twosome problem is this assume you have a sorted array r so let's give ourselves a visual and you're tasked with figuring out the pair of elements where r p so the element p in r and r q element q in r where they add up to a certain number so let's say here they add up to six so from a quick glance we can see that two and four add up to 6. if we were to get the machine to do this though one way is to iterate through each element and then at each element iterate through each other element and then compare the two but that gives you a time complexity of o of n squared because at each iteration we have to iterate through the entire array again but we can optimize we can use two pointers instead so here on line four we assign a variable called pointer one to 0 which is the first index and pointer 2 to the length of r minus 1 which is the final index so length r minus one gets us the last possible index in that array and when we first start pointer one points to the first element in the array and pointer two points to the last element so we have the setup where we have a function for two sum and we have zero and then the end and our iteration starts wild 0.01 is less than 0.2 so since the array is sorted we can use two pointers to process them faster so that's what we've been doing one pointer starts from the beginning one pointer starts at the end and we just add the values at these pointers and move them correspondingly as we iterate and discover more about the elements so how do we discover more about the elements we can use a check like this we'll get their sum and if their sum equals the target value then we'll return true so what if it's not the target value it likely won't be because we need to have this discovery phase and so as we're as we're moving we need to tell it to move inwards so starting at the beginning and starting at the end what we want to do is go in so we'll move pointer one which starts at zero inwards and we'll move pointer two which starts at the end inwards as well by adding one and then by subtracting one so fleshed out together here's what we have two sum pointer one point or two while one is less than two we find the sum and then if it's not what we want if the combination is not what we want we move them inwards depending on which will get us closer so another example of using two pointers is this notion of slow and fast pointers in linked lists so let's say we have a linked list that looks like this and we want to find out if there's a cycle in the linked list so nodes one two three there's no cycle but we can see that there's a cycle between nodes 3 and 4. so how would we detect the cycle what's interesting is we can also use two pointers here the idea is to move the fast pointer so there's a slow and a fast pointer the idea is to move the fast pointer twice as fast as the first pointer and what will happen is the distance between them increases by one at each step and so this is how it's expressed in code while there's still room to go increment slow by one and an increment fast by two at some point if both pointers meet then we'll have found a cycle in the linked list if we reach the end of the list and no cycle has been found that means no cycle is present and so this runs in linear time and it might be a little confusing as to why it works so let's think about this let's do 0.01 is the slow pointer so iteration 1 it'll move here iteration 2 it'll move here and then at iteration three it'll move here and then at iteration four it'll move here so that's the slow pointer with the fast pointer iteration one it'll move to three and then at iteration two it'll move from three back to three and notice that it's iteration two and the slow point is iteration two remember slow is one two end up at the same spot and so here's the full code for using two pointers to detect the cycle the theory behind slow and fast pointers can be found on another tutorial on and and in other places on algodaily.com but for now this is a introduction to the use of two pointers and i hope you learned