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!
-
$\begingroup$ How would you sandwich with two pointers without sorting? $\endgroup$Navjot Singh– Navjot Singh2018年09月12日 19:09:28 +00:00Commented 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– Navjot Singh2018年09月12日 19:11:35 +00:00Commented 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– Navjot Singh2018年09月12日 19:13:33 +00:00Commented 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– Kaa1el2018年09月12日 20:11:17 +00:00Commented 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– Kaa1el2018年09月12日 20:13:40 +00:00Commented Sep 12, 2018 at 20:13
1 Answer 1
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.
Explore related questions
See similar questions with these tags.