CODEWITHSUNDEEP
algorithm
Aman Jain
Aman Jain

Reputation: 11317

Which numbers in an unordered list can be represented as a sum of 3 other numbers in the list?

I encountered the following interview question online, and came up with O(N^2) solution.
I want to know if there is a better way to solve this problem?

Problem: Which numbers in an unordered list can be represented as a sum of 3 other numbers in the list?

My O(N^2) solution:

  1. Create a hashmap that stores sum of all 2 element pairs.
    e.g. hashmap.insert(a[i] + a[j]), 0 <= i,j <= N-1

  2. Once hashmap is built in step 1 (takes O(N^2) time,
    I will pick a pair from nC2 pairs and see if this pair contains
    the third element and the sum.
    i.e. For all pairs of two elements(a[p], a[q]) where 0 <= p,q <= N-1
    Find if hashmap contains (a[q] - a[p])

Upvotes: 4

Views: 399

Answers (1)

Vikram Bhat
Vikram Bhat

Reputation: 6246

Cannot do better than O(N^2) because if you then you would have solved one of the most difficult problems in computer science that is to solve 3-sum problem in less than O(N^2). It is still an open question whether 3-sum can be solved less than O(N^2).

3-Sum

Upvotes: 4

Related Questions