Given an array of numbers, find triplets i,j,k such that a[i] + a[j] = a[k]

Question

You are given an array of numbers a[1..n]

Give an algorithm to find triplets i,j,k such that a[i] + a[j] = a[k].

The time complexity of your algorithm should be better than n^3, that is o(n^3) // small oh notation.

Answer 1

This Problem can be solved in O(n^2) using sorting and two pointer approach .

1) First sort the array -> nlogn

2) In the outer loop we iterate for the RHS (a[k]) and in the inner loop we find the LHS using two pointer approach.

3) outer loop takes O(n) and the inner loop also takes linear time

So the overall time complexity is nlogn+n^2 which is O(n^2)

Code:

sort(a,a+n) --> //sorting the array initially

for(int k=n;k>=1;k—)     // Outer loop
{
int i =1, int j=k-1 : // 2 pointers
While(i<j)
{                                   // inner loop
int Sum=a[i]+a[j];
If(Sum==a[k])
Found a pair, i++;
Else if(sum<a[k])
i++;  // increment i pointer so that sum approaches a[k]
Else
j—; // reduce j pointer so that sum approaches a[k]

}

}

Comments

Can you provide code for the inner loop?  Can you provide pseudocode?

---

Yes professor , wrote it