DEV Community

Jacob Pelletier for Yankeedom.io

Posted on • Updated on

Two Pointers - Sum of Three Values

Two Pointers Pattern | Sum of Three Values | For Beginners

by Jacob Pelletier


Image description

Follow me as I document my journey as I (quickly) work through the 24 patterns of Leet Code Questions in Javascript as a nice refresher for myself. This resource, in addition to Leet Code, is excellent preparation for any interview!

I am no Ph.D. in C.S. (just with a lowly B.S.) and this isn't meant to be an authoritative or heavily theoretical guide. This is guide is meant to be fun, fast, and casual.

Each article in this series will seek to plainly explain:

  1. The pattern
  2. The problem
  3. The solution in JS
  • If anyone at all ends up reading these things I will post solutions in TS in the future! 😜

Additional problems common of the two pointer pattern, in addition to sum of three values, are:

  1. Two Pointers
  2. Reverse Words in a String

Explaining The Sum of Three Values Problem.

The Sum of Three Values Problem is a classic computer science problem. It involves finding three numbers from an array of numbers such that the sum of these three numbers is equal to a given value. We consider solving this problem using the Two Pointer method as discussed in the course the 24 patterns.

Given an array of integers, nums, and an integer value, target, determine if there are any three integers in nums whose sum equals the target. Return TRUE if three such integers are found in the array. Otherwise, return FALSE.

Image description

Steps to solve:

  1. Sort the array in ascending order.
  2. Loop through the entire array and set up two pointers (low and high) on every iteration.
  3. Low is set to the current loop index + 1, and high is set to the last index of the array.
  4. In an inner loop, look for values that, along with the current element, sum up to target.
  5. Calculate the sum of array elements pointed to by the current loop index, and the low and high pointers.
  6. If the sum is equal to target, return TRUE.
  7. Else if the sum is greater than target, move the high pointer backwards.
  8. Else if the sum is less than target, move the low pointer forwards.
  9. Terminate the inner loop when low reaches r crosses high. Reset low to the current loop element +1, and reset high to the last index.
  10. If, after processing the entire array, we don't find a triple that matches our requirement, we return FALSE.

Problem #1 With Solution

Problem #1:

Solution:

My Solution:


Enter fullscreen mode Exit fullscreen mode

Output:


Enter fullscreen mode Exit fullscreen mode

Analysis

Space: O(n)
Time: O(1)

Thanks for tuning in, more algo content on the way as I move through it myself!

Top comments (0)