Arithmetic sequence in a list of numbers

Question

For a given set of numbers

3 5 3 6 3 4 10 4 5 2 

I want to find all **triplets** that form an arithmetic progression.

 like (3,3,3) (3,4,5) (6,4,2) (3,4,5) 

I have a trivial solution O (n ^ 3). I was wondering if this time can be made O (n ^ 2) or less.

Any help is greatly appreciated.

Answer 1

O(n^2 * logn) can be achieved by:

• Array Sort - O (nlogn)
• repeat all pairs (O (n ^ 2) of them) - and for each pair (x, y) perform a binary search to see if you have: max{x,y} + abs(xy) or min{x,y} - abs(xy) as an element.
  Particular attention should be paid to pairs where x==y - but it can be easily solved with the same complexity in time.

Please note that this solution will give you 1 view of each triplet (no duplicates).

( EDIT: using a hash table ( histogram if you care about the number of triplets) and look in it instead of sorting the array and using binary search - you can reduce the time to O(n^2) on average, at a cost of O(n) extra space).

---

Without 1 minus failures - this cannot be done better than O(n^3) , because there can be O(n^3) such triplets, for example, in an array [1,1,1,...,1] - you have chose(3,n) such triplets.

Answer 2

You can use hashing to solve it in O(n^2) by selecting the middle element and then selecting the first and last element in O(n) .

This is a simple question about finding two numbers in an array whose sum is fixed. Here a+c should be 2b .

Therefore, all that I was looking for a and c in such a way that a+c=2i .