0
$\begingroup$

I have a problem where I have to find all the pairs of a list of People where the sum of their age is equal to a given number under time complexity less than

O(N²)

Eg:

Input:

 {(Jhon, 10),(mary,20),(paul,10),(joseph,15)} 
 Sum:30

Expected results:

{(John, Mary), (Mary, Paul) }

The worst scenario i can imagine is where every person has the same age and the target sum is 2*age. What i think is in this scenario you would need to do the combination nC2 which is O(n²). I dont know if my approach is wrong or there is any algorithm to solve this scenario in less than O(n²).

$\endgroup$
1
  • 1
    $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$
    – D.W.
    Jul 16, 2022 at 17:42

2 Answers 2

1
$\begingroup$

There are cases where the output has size $\Omega(n^2)$, showing that the problem cannot be solved in time $o(n^2)$ in general.

An example is the one you propose. E.g., the age of every person is $0$ and the target age is $0$.

$\endgroup$
1
$\begingroup$

Agreed that worst case is $O(n^2)$, so you cannot find an algorithm in general that works better.

If you modify the output to instead say a person followed by the corresponding people that would add up to the desired age, then you can do this in $O(n)$ with a modified 2-sum solution.

Basically you would create a dictionary $D$ of $\text{age} \to \text{set(names)}$, as a preprocessing step, and you would output for each person $p_i$ with age $a_i$, the tuple

$$(p_i, D[S-a_i])$$

where $S$ is the desired sum. Notice there are duplications of $p_i$ in the set retrieved, so you could run a set remove of $p_i$ in that set, but you still run into "pairs" that are duplicated, since if $a_i + a_j = S$, then you will output $(p_i, S \text{ containing } p_j)$ and $(p_j, S \text{ containing } p_i)$.

Just wanted to add this answer here, since the original problem sounds very close to 2-sum.

$\endgroup$
1
  • $\begingroup$ How do you keep the dictionary? I don't think you can support access in constant worst case time without spending $\Omega(max_i a_i)$ time and space. You can do it in time $O(\log \log \max_i a_i)$ in the worst case though, using Van Emde Boas trees, or in $O(1)$ expected time with hashing. $\endgroup$
    – Steven
    Jul 17, 2022 at 10:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.