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

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


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 the one element at a time
  • Now 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 the one element at a time.
  • Now required_sum is (with two elements) = k-fixed element.
  • Create a HashSet, Iterate through 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)



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

Top Companies Interview Questions..-

Google Microsoft Amazon Facebook more..

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.

You may also like...

%d bloggers like this: