Two Pointer 1

Overview

This is the technique which uses 2 pointers, the first one is located at beginning of the array, the second one is located at the end of the array. 2 pointer will move toward together to resolve the problem

Example: Given a sorted array [1, 3, 8, 9, 10], check if exist the pair that sum is given target (12). For the bruth force, we can use 2 pointer i and j which j = i+1 then each element arr[i] check any arr[j] which sum to targe. By this way we took 2 for loop so that the time complexity is O(n^2). For the optimize solution, we can use the 2 pointer technique which still use 2 pointer but now the location of 2 pointer is at the end of the array. The first pointer is at arr[0] and the secodn pointer is at arr[n-1]. Because the array is sorted in increase order so that we will have the rule to move the pointer. If the sum of current 2 element is < target we will move the first pointer (left pointer) otherwise we move the second pointer. If the left pointer equal or lesser than right pointer we stop moving. By this way the time complexity just O(n).