# Is it possible to solve 3SUM in $O(n^2)$ time?

Problem: 3SUM

Input: Three lists A, B and C of integers and an integer k. Each list contain $n$ numbers. Task: Decide whether there exists a tuple (a, b, c) ∈ A × B × C such that a + b + c = k.

Question : Is it possible to solve 3SUM in $O(n^2)$ time using constant space ? Prove or disprove it

A $O(n^2)$ algorithm (with $O(1)$ space) is as follows:

• Sort $A$, $B$, and $C$ individually in $O(n \log n)$.
• For each $a \in A$:
• Search a pair of $b \in B$ and $c \in C$ such that $b + c = k - a$. This can be done in $O(n)$ by traversing $B$ from the smallest to the largest and $C$ from the largest to the smallest. (Tip: Comparing $b + c$ with $k-a$ each time.)

This question is not a 3sum problem. The question can be solved with hash tables. For each element in C traverse A and see if the corresponding element exists in B. Time complexity would be $O(|C|*|A|*1) = O(|C||A|)$

Edit:
This problem can be treated as 2SUM problem for each element in C (or any other list as they are symmetrical). That is for each $c \in C$ we find solutions for the sum $k - c$ using elements from A and B.
For a $O(1)$ auxiliary space algorithm one can first sort A and B. Then use 2-pointer algorithm (Tutorial) to solve the 2SUM problem in $O(n)$.