2
$\begingroup$

this is related to the following question:

Generalised 3SUM (k-SUM) problem?

Without loss of generality, let's only consider even $k$, or just $k=4$.

My question is, after summing all pairs of numbers, is it necessary to sort the list of sums? I understand we could use two pointers from left and right to sandwich the two pairs in $O(n^2)$ time, but the sorting requires $O(n^2\log(n))$ time.

If we use a hashmap to store the sums as key and their corresponding index pairs as value, then all operations can run in $O(n^2)$ time.

Am I missing something in that post or is it true for even $k$, $k$-sum can run in $O(n^{k/2})$ time?

Thanks!

Improve this question
$\endgroup$
6
  • $\begingroup$ How would you sandwich with two pointers without sorting? $\endgroup$
    – Navjot Singh
    Commented Sep 12, 2018 at 19:09
  • $\begingroup$ Let s = $n^2$, then time needed to sort is $O(slogs)$ which is not equal to $O(n^2logn)$. $\endgroup$
    – Navjot Singh
    Commented Sep 12, 2018 at 19:11
  • $\begingroup$ Hashmap cannot store duplicates. So two pairs having same sum cannot be placed in the hashmap if sum is used as a key. Consider (1,3) and (2,2). $\endgroup$
    – Navjot Singh
    Commented Sep 12, 2018 at 19:13
  • $\begingroup$ @JotWaraich $O(n^2 \log(n^2))=O(n^2 2\log(n))=O(n^2 \log(n))$ $\endgroup$
    – Kaa1el
    Commented Sep 12, 2018 at 20:11
  • $\begingroup$ @JotWaraich in this case, either you don't need to store the duplicates (decision problem or return one such sum), or you can store in the value a list which consists of all such pairs (return all different sums). Either way, the complexity is not affected. $\endgroup$
    – Kaa1el
    Commented Sep 12, 2018 at 20:13

1 Answer 1

Reset to default
4
$\begingroup$

You are right, but Jeff's answer in the link you provided works in the "linear decision tree model". You cannot use hashing in that model.

Improve this answer
$\endgroup$

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.