CODEWITHSUNDEEP
algorithmmathsequence
LAP
LAP

Reputation: 132

Arithmetic sequence in a list of numbers

For a given set of numbers

3 5 3 6 3 4 10 4 5 2

I wish to find all the **triplets** which form a arithmetic progression.

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

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

Any help is highly appreciated.

Upvotes: 4

Views: 2403

Answers (2)

xhunter
xhunter

Reputation: 21

One can use hashing to solve it in O(n^2) by choosing a middle element and then choosing first and last element in O(n).

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

Therefore, all I look for a & c such that a+c=2i.

Upvotes: 1

amit
amit

Reputation: 178431

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

  1. Sort the array - O(nlogn)
  2. iterate all pairs (O(n^2) of those) - and for each pair (x,y) do a binary search to see if you have: max{x,y} + abs(x-y) or min{x,y} - abs(x-y) as an element.
    Special care should be taken for pairs where x==y - but it can be easily solved within the same time complexity.

Note that this solution will give you 1 occurance of each triplet (no duplicates).

(EDIT: by using a hash table (histogram if you care for 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, with the cost of O(n) additional space).

Without the 1 occurance drawback - it cannot be done better then O(n^3), because there could be O(n^3) such triplets, for example in the array [1,1,1,...,1] - you have chose(3,n) such triplets.

Upvotes: 5

Related Questions