1
$\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!

$\endgroup$
  • $\begingroup$ How would you sandwich with two pointers without sorting? $\endgroup$ – Navjot Waraich Sep 12 '18 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 Waraich Sep 12 '18 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 Waraich Sep 12 '18 at 19:13
  • $\begingroup$ @JotWaraich $O(n^2 \log(n^2))=O(n^2 2\log(n))=O(n^2 \log(n))$ $\endgroup$ – Kaa1el Sep 12 '18 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 Sep 12 '18 at 20:13
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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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