The Art Gallery Guardian

A common 3SUM-hard reduction


I'm writing this to address a problem I often hear from friends. They usually get it from some technical interview.

Problem1

Let \(A\) be an array of \(n\) numbers, decide if there exist index \(i,j,k\), such that \(A[i]+A[j]=A[k]\).

The problem is 3SUM-hard. We reduce the problem 3SUM to the above problem in linear time.

Problem23SUM

Does there exist \(a,b,c\in S\), such that \(a+b+c=0\)?

Consider a instance of 3SUM. Let \(m=3 \max(S \cup -S)+1\). Store \(\{m\}+S\) and \(\{2m\}-S\) as elements in the array \(A\).

Claim: There exist i,j,k such that \(A[i]+A[j]=A[k]\) iff there exist \(a,b,c\in S\) such that \(a+b+c=0\).

If there exist \(i,j,k\) such that \(A[i]+A[j]=A[k]\), this implies \(A[i]=a+m,A[j]=b+m,A[k]=2m+(-c)\) for some \(a,b,c\in S\). The other direction is similar.

Posted by Chao Xu on 2014-04-05.
Tags: .