Be the first user to complete this post

  • 1
 Add to List
Beginner

236. Find three elements in an array that sum to a given value

Objec­tive:  Given an array of integers write an algorithm to find 3 elements that sum to a given number k. In short a+b+c = k.

Example:

int a [] = { 3,1,7,4,5,9,10} , k = 21;Output: Elements are 7 4 10 

int a [] = { 3,1,7,4,5,9,10} , k = 55;Output:

Did not find 3 elements whose sum is 55 

Approach: Brute Force

Use 3 nested loops and find the 3 elements which sum to k.

Time Complexity: O(n^3)

Approach: Sorting

  • Sort the array.
  • Use the other loop to fix one element at a time
  • Now the problem is reduced to “Find a pair of numbers from an array whose sum equals k”

Time Complexity: O(n^2)

Approach: Use Hashing

  • Use the other loop to fix one element at a time.
  • Now required_sum is (with two elements) = k-fixed element.
  • Create a HashSet, and Iterate through the rest of the array.
  • For current_element, remain_value = required_sum – current_element.
  • Check if remain_value in the HashSet, we have found our triplets else add current_element to the hashset.

Time Complexity: O(n^2)

Output:

Found 3 elements whose sum is = 22
Elements are 3 10 9

Related Problems: