1
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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.)
$\endgroup$
1
$\begingroup$

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:
Answer to the updated question:

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)$.

Comment if you have doubts on implementation. You can also see https://cs.stackexchange.com/a/13586/81272

$\endgroup$
  • $\begingroup$ What about space complexity ? $\endgroup$ – Complexity Dec 20 '17 at 8:05
  • 2
    $\begingroup$ are you sure? This seems to be 3sum problem. $\endgroup$ – noman pouigt Dec 20 '17 at 8:38

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.