Timeline for Can we do 4-sum algorithm in O(n^2)?
Current License: CC BY-SA 4.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 12, 2018 at 21:22 | answer | added | hqztrue | timeline score: 4 | |
| Sep 12, 2018 at 20:14 | comment | added | Kaa1el | @JotWaraich please read the question more carefully, sandwich REQUIRES sorting, hashmap does not need sorting. | |
| Sep 12, 2018 at 20:13 | comment | added | Kaa1el | @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. | |
| Sep 12, 2018 at 20:11 | comment | added | Kaa1el | @JotWaraich $O(n^2 \log(n^2))=O(n^2 2\log(n))=O(n^2 \log(n))$ | |
| Sep 12, 2018 at 19:13 | comment | added | Navjot Singh | 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). | |
| Sep 12, 2018 at 19:11 | comment | added | Navjot Singh | Let s = $n^2$, then time needed to sort is $O(slogs)$ which is not equal to $O(n^2logn)$. | |
| Sep 12, 2018 at 19:09 | comment | added | Navjot Singh | How would you sandwich with two pointers without sorting? | |
| Sep 12, 2018 at 18:37 | history | asked | Kaa1el | CC BY-SA 4.0 |