{"type":"lesson","lesson":{"id":40,"title":"Using the Two Pointer Technique","body":"The **two pointer technique** is a near necessity in any software developer's toolkit, especially when it comes to technical interviews. In this guide, we'll cover the basics so that you know when and how to use this technique. ## What is the pattern? The name `two pointers` does justice in this case, as it is exactly as it sounds. It's the use of two different pointers (usually to keep track of array or string indices) to solve a problem involving said indices with the benefit of saving time and space. ### When do we use it? In many problems involving collections such as arrays or lists, we have to analyze each element of the collection compared to its other elements. There are many approaches to solving problems like these. For example we usually start from the first index and iterate through the data structure one or more times depending on how we implement our code. Sometimes we may even have to create an additional data structure depending on the problem's requirements. This approach might give us the correct result, but it likely won't give us the most space and time efficient result. This is why the two-pointer technique is efficient. We are able to process two elements per loop instead of just one. Common patterns in the two-pointer approach entail: 1. Two pointers, each starting from the beginning and the end until they both meet. 2. One pointer moving at a slow pace, while the other pointer moves at twice the speed. These patterns can be used for string or array questions. They can also be streamlined and made more efficient by iterating through two parts of an object simultaneously. You can see this in the [Two Sum problem](https://algodaily.com/challenges/two-sum) or [Reverse a String](https://algodaily.com/challenges/reverse-a-string) problems. ## Running through an example One usage is while searching for pairs in an array. Let us consider [a practical example](https://algodaily.com/challenges/two-sum): assume that you have a sorted array `arr`. You're tasked with figuring out the pair of elements where `arr[p]` + `arr[q]` add up to a certain number. (To try this problem out, check the [Two Sum](https://algodaily.com/challenges/two-sum) and [Sorted Two Sum](https://algodaily.com/challenges/sorted-two-sum) problems here.) The brute force solution is to compare each element with every other number, but that's a time complexity of `O(n^2)`. We can do better! So let's optimize. You need to identify the indices `pointer_one` and `pointer_two` whose values sum to the integer `target`. Let's initialize two variables, `pointer_one` and `pointer_two`, and consider them as our two pointers. ```py pointer_one = 0 pointer_two = len(arr)-1 ``` Note that `len(arr)-1` helps to get the last index possible in an array. Also observe that when we start, `pointer_one` points to the first element of the array, and `pointer_two` points to the last element. This won't always be the case with this technique (we'll explore the [sliding window concept](https://algodaily.com/lessons/a-birds-eye-view-into-sliding-windows) later, which uses two pointers but have them move in a different direction). For our current purposes, it is more efficient to start wide, and iteratively narrow in (particularly if the array is sorted). ```py def two_sum(arr, target): pointer_one = 0 pointer_two = input.length - 1 while pointer_one < pointer_two: ``` Since the array is already sorted, and we're looking to process an index at each iteration, we can use two pointers to process them faster. One pointer _starts from the beginning of the array_, and the other pointer _begins from the end of the array_, and then we add the values at these pointers. Once we're set up, what we want to do is check if the current pointers already sum up to our target. This might happen if the correct ones are on the exact opposite ends of the array. Here's what the check might look like: ```py if sum == targetValue: return true ``` However, it likely will not be the target immediately. Thus, we apply this logic: if the sum of the values is less than the target value, we increment the left pointer (move your left pointer `pointer_one` one index rightwards). And if the sum is higher than the target value, we decrement the right pointer (correct the position of your pointer `pointer_two` if necessary). ```py elif sum < targetValue: pointer_one += 1 else: pointer_two -= 1 ``` In other words, understand that if `arr[pointer_one]` < `target-arr[pointer_two]`, it means we should move forward on `pointer_one` to get closer to where we want to be in magnitude. This is what it looks like all put together: ```py def two_sum(arr, target): pointer_one = 0 pointer_two = input.length - 1 while pointer_one < pointer_two: sum = input[pointer_one] + input[pointer_two] if sum == targetValue: return true elif sum < targetValue: pointer_one += 1 else: pointer_two -= 1 return false ``` It's crucial to see that how both indices were moving in conjunction, and how they depend on each other. We kept moving the pointers until we got the sum that matches the target value-- or until we reached the middle of the array, and no combinations were found. The time complexity of this solution is `O(n)` and space complexity is `O(1)`, a significant improvement over our first implementation! `Another Example` In addition, to the previous example, the two pointer technique can also involve the pattern of using a fast pointer and a slow pointer. ```java Node fast = head, slow = head ``` One usage is through detecting cycles in a linked list data structure. For example, a cycle (when a node points back to a previous node) begins at the last node of the linked list in the example below. ``` 1 -- > 2 --> 3 --> 4 ^ | | | <- - - ``` The idea is to move the fast pointer twice as quickly as the slow pointer so the distance between them increases by 1 at each step. ```java while(fast!=null && fast.next!=null){ slow = slow.next; fast = fast.next.next; ``` However, if at some point both pointers meet, then we have found a cycle in the linked list. Otherwise we'll have have reached the end of the list and no cycle is present. ```java if (slow==fast) return true; ``` This is what the entire method would look like all together: ```java public static boolean detectCycle(Node head){ Node fast = head, slow = head; while(fast!=null && fast.next!=null){ slow = slow.next; fast = fast.next.next; if(slow==fast) return true; } return false; } ``` The time complexity would be `O(N)` or linear time.","slug":"using-the-two-pointer-technique","created_at":"2019-09-07T02:08:07.731Z","updated_at":"2020-05-29T00:15:05.108Z","image_url":null,"section_id":4,"sequence":2,"locked":false},"screens":[{"id":807,"kind":"info screen","options":[],"content":"The **two pointer technique** is a near necessity in any software developer's toolkit, especially when it comes to technical interviews. In this guide, we'll cover the basics so that you know when and how to use this technique.","code":"","full_screen":true,"solution":"","lesson_id":40,"challenge_id":null,"sequence":1,"title":"Introduction","slug":"introduction","created_at":"2020-05-29T00:14:20.484Z","updated_at":"2020-05-29T00:14:20.484Z"},{"id":808,"kind":"info screen","options":[],"content":"## What is the pattern? The name `two pointers` does justice in this case, as it is exactly as it sounds. It's the use of two different pointers (usually to keep track of array or string indices) to solve a problem involving said indices with the benefit of saving time and space.","code":"","full_screen":true,"solution":"","lesson_id":40,"challenge_id":null,"sequence":2,"title":"What Is The Pattern?","slug":"what-is-the-pattern-2","created_at":"2020-05-29T00:14:20.591Z","updated_at":"2020-05-29T00:14:20.591Z"},{"id":809,"kind":"info screen","options":[],"content":"### When do we use it? In many problems involving collections such as arrays or lists, we have to analyze each element of the collection compared to its other elements. There are many approaches to solving problems like these. For example we usually start from the first index and iterate through the data structure one or more times depending on how we implement our code. Sometimes we may even have to create an additional data structure depending on the problem's requirements. This approach might give us the correct result, but it likely won't give us the most space and time efficient result. This is why the two-pointer technique is efficient. We are able to process two elements per loop instead of just one. Common patterns in the two-pointer approach entail: 1. Two pointers, each starting from the beginning and the end until they both meet. 2. One pointer moving at a slow pace, while the other pointer moves at twice the speed. These patterns can be used for string or array questions. They can also be streamlined and made more efficient by iterating through two parts of an object simultaneously. You can see this in the [Two Sum problem](https://algodaily.com/challenges/two-sum) or [Reverse a String](https://algodaily.com/challenges/reverse-a-string) problems.","code":"","full_screen":true,"solution":"","lesson_id":40,"challenge_id":null,"sequence":3,"title":"When Do We Use It?","slug":"when-do-we-use-it-3","created_at":"2020-05-29T00:14:20.698Z","updated_at":"2020-05-29T00:14:20.698Z"},{"id":810,"kind":"info screen","options":[],"content":"## Running through an example One usage is while searching for pairs in an array. Let us consider [a practical example](https://algodaily.com/challenges/two-sum): assume that you have a sorted array `arr`. You're tasked with figuring out the pair of elements where `arr[p]` + `arr[q]` add up to a certain number. (To try this problem out, check the [Two Sum](https://algodaily.com/challenges/two-sum) and [Sorted Two Sum](https://algodaily.com/challenges/sorted-two-sum) problems here.) The brute force solution is to compare each element with every other number, but that's a time complexity of `O(n^2)`. We can do better! So let's optimize. You need to identify the indices `pointer_one` and `pointer_two` whose values sum to the integer `target`. Let's initialize two variables, `pointer_one` and `pointer_two`, and consider them as our two pointers.","code":"```py pointer_one = 0 pointer_two = len(arr)-1 ```","full_screen":false,"solution":"","lesson_id":40,"challenge_id":null,"sequence":4,"title":"Running Through An Example","slug":"running-through-an-example-4","created_at":"2020-05-29T00:14:20.805Z","updated_at":"2020-05-29T00:14:20.805Z"},{"id":811,"kind":"info screen","options":[],"content":"Note that `len(arr)-1` helps to get the last index possible in an array. Also observe that when we start, `pointer_one` points to the first element of the array, and `pointer_two` points to the last element. This won't always be the case with this technique (we'll explore the [sliding window concept](https://algodaily.com/lessons/a-birds-eye-view-into-sliding-windows) later, which uses two pointers but have them move in a different direction). For our current purposes, it is more efficient to start wide, and iteratively narrow in (particularly if the array is sorted).","code":"```py def two_sum(arr, target): pointer_one = 0 pointer_two = input.length - 1 while pointer_one < pointer_two: ```","full_screen":false,"solution":"","lesson_id":40,"challenge_id":null,"sequence":5,"title":"Step Five","slug":"step-five-5","created_at":"2020-05-29T00:14:20.911Z","updated_at":"2020-05-29T00:14:20.911Z"},{"id":812,"kind":"info screen","options":[],"content":"Since the array is already sorted, and we're looking to process an index at each iteration, we can use two pointers to process them faster. One pointer _starts from the beginning of the array_, and the other pointer _begins from the end of the array_, and then we add the values at these pointers. Once we're set up, what we want to do is check if the current pointers already sum up to our target. This might happen if the correct ones are on the exact opposite ends of the array. Here's what the check might look like:","code":"```py if sum == targetValue: return true ```","full_screen":false,"solution":"","lesson_id":40,"challenge_id":null,"sequence":6,"title":"Step Six","slug":"step-six-6","created_at":"2020-05-29T00:14:21.020Z","updated_at":"2020-05-29T00:14:21.020Z"},{"id":813,"kind":"info screen","options":[],"content":"However, it likely will not be the target immediately. Thus, we apply this logic: if the sum of the values is less than the target value, we increment the left pointer (move your left pointer `pointer_one` one index rightwards). And if the sum is higher than the target value, we decrement the right pointer (correct the position of your pointer `pointer_two` if necessary).","code":"```py elif sum < targetValue: pointer_one += 1 else: pointer_two -= 1 ```","full_screen":false,"solution":"","lesson_id":40,"challenge_id":null,"sequence":7,"title":"Step Seven","slug":"step-seven-7","created_at":"2020-05-29T00:14:21.127Z","updated_at":"2020-05-29T00:14:21.127Z"},{"id":814,"kind":"info screen","options":[],"content":"In other words, understand that if `arr[pointer_one]` < `target-arr[pointer_two]`, it means we should move forward on `pointer_one` to get closer to where we want to be in magnitude. This is what it looks like all put together:","code":"```py def two_sum(arr, target): pointer_one = 0 pointer_two = input.length - 1 while pointer_one < pointer_two: sum = input[pointer_one] + input[pointer_two] if sum == targetValue: return true elif sum < targetValue: pointer_one += 1 else: pointer_two -= 1 return false ```","full_screen":false,"solution":"","lesson_id":40,"challenge_id":null,"sequence":8,"title":"Step Eight","slug":"step-eight-8","created_at":"2020-05-29T00:14:21.233Z","updated_at":"2020-05-29T00:14:21.233Z"},{"id":815,"kind":"info screen","options":[],"content":"It's crucial to see that how both indices were moving in conjunction, and how they depend on each other. We kept moving the pointers until we got the sum that matches the target value-- or until we reached the middle of the array, and no combinations were found. The time complexity of this solution is `O(n)` and space complexity is `O(1)`, a significant improvement over our first implementation! `Another Example` In addition, to the previous example, the two pointer technique can also involve the pattern of using a fast pointer and a slow pointer.","code":"```java Node fast = head, slow = head ```","full_screen":false,"solution":"","lesson_id":40,"challenge_id":null,"sequence":9,"title":"Step Nine","slug":"step-nine-9","created_at":"2020-05-29T00:14:21.340Z","updated_at":"2020-05-29T00:14:21.340Z"},{"id":816,"kind":"info screen","options":[],"content":"One usage is through detecting cycles in a linked list data structure. For example, a cycle (when a node points back to a previous node) begins at the last node of the linked list in the example below.","code":"``` 1 -- > 2 --> 3 --> 4 ^ | | | <- - - ```","full_screen":false,"solution":"","lesson_id":40,"challenge_id":null,"sequence":10,"title":"Step Ten","slug":"step-ten-10","created_at":"2020-05-29T00:14:21.452Z","updated_at":"2020-05-29T00:14:21.452Z"},{"id":817,"kind":"info screen","options":[],"content":"The idea is to move the fast pointer twice as quickly as the slow pointer so the distance between them increases by 1 at each step.","code":"```java while(fast!=null && fast.next!=null){ slow = slow.next; fast = fast.next.next; ```","full_screen":false,"solution":"","lesson_id":40,"challenge_id":null,"sequence":11,"title":"Step Eleven","slug":"step-eleven-11","created_at":"2020-05-29T00:14:21.558Z","updated_at":"2020-05-29T00:14:21.558Z"},{"id":818,"kind":"info screen","options":[],"content":"However, if at some point both pointers meet, then we have found a cycle in the linked list. Otherwise we'll have have reached the end of the list and no cycle is present.","code":"```java if (slow==fast) return true; ```","full_screen":false,"solution":"","lesson_id":40,"challenge_id":null,"sequence":12,"title":"Step Twelve","slug":"step-twelve-12","created_at":"2020-05-29T00:14:21.666Z","updated_at":"2020-05-29T00:14:21.666Z"},{"id":819,"kind":"info screen","options":[],"content":"This is what the entire method would look like all together:","code":"```java public static boolean detectCycle(Node head){ Node fast = head, slow = head; while(fast!=null && fast.next!=null){ slow = slow.next; fast = fast.next.next; if(slow==fast) return true; } return false; } ```","full_screen":false,"solution":"","lesson_id":40,"challenge_id":null,"sequence":13,"title":"Step Thirteen","slug":"step-thirteen-13","created_at":"2020-05-29T00:14:21.772Z","updated_at":"2020-05-29T00:14:21.772Z"},{"id":820,"kind":"info screen","options":[],"content":"The time complexity would be `O(N)` or linear time.","code":"","full_screen":true,"solution":"","lesson_id":40,"challenge_id":null,"sequence":14,"title":"Step Fourteen","slug":"step-fourteen-14","created_at":"2020-05-29T00:14:21.878Z","updated_at":"2020-05-29T00:14:21.878Z"}],"user":null,"completed":null,"language":null,"nextArr":["Lesson","a-birds-eye-view-into-sliding-windows"]}