Algorithm

Besides using one pointer to loop through all elements, you can use two pointers to walk inward from both ends of a linear collection, such as array or string, to check a condition

Apart from that, you can also hash collection elements into a hash table to improve the lookup time

Let walk through this article to explore them in more details

The 2Sum problem

  • Given an array of integers a[n] and an integer number k as a target sum
  • Determine whether there is a pair of elements a[i] and a[j] that sums exactly to k

Example

  • Given an array a [1, 3, 7] and k = 8 then the answer is true, but given k=5 then the answer is false
  • Given an array a [4, -9, 0, 11, 6, -20, 1, 7] and k = -14 then the answer is true, but given k = -15 then the answer is false

Approach 1: Brute force

  • Try all pairs in array a to see if any of them add up to k
  • Output
true  
false  
true  
false
  • Time complexity: O(n2) as with each element, the algorithm loops through the array which takes O(n) time
  • Space complexity: O(1)

Approach 2: Two pointers

  • Sort the array
  • Walk two pointers inward from both ends of the array, at each point looking at their sum
  • Output
true  
false  
true  
false
  • Time complexity: O(nlogn) due to the cost of sorting
  • Space complexity: O(1)

Approach 3: Hash table

  • Add array elements into a hash table
  • For each array element a[i], check if existing an element a[j] that a[j] = k - a[i]
  • Output
true  
false  
true  
false
  • Time complexity: O(n) as with each element, the algorithm looks up in the hash table which takes O(1) time
  • Space complexity: O(n) as the algorithm adds elements into a hash table

Learn more about Hash table

Algorithm