Two Pointers Pattern | Sum of Three Values | For Beginners
by Jacob Pelletier
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:
- The pattern
- The problem
- 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:
- Two Pointers
- 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.
Steps to solve:
- Sort the array in ascending order.
- Loop through the entire array and set up two pointers (low and high) on every iteration.
- Low is set to the current loop index + 1, and high is set to the last index of the array.
- In an inner loop, look for values that, along with the current element, sum up to target.
- Calculate the sum of array elements pointed to by the current loop index, and the low and high pointers.
- If the sum is equal to target, return TRUE.
- Else if the sum is greater than target, move the high pointer backwards.
- Else if the sum is less than target, move the low pointer forwards.
- 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.
- If, after processing the entire array, we don't find a triple that matches our requirement, we return FALSE.
Problem #1 With Solution
Thanks for tuning in, more algo content on the way as I move through it myself!
Top comments (0)