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 AA be an array of nn numbers, decide if there exist index i,j,ki,j,k, such that A[i]+A[j]=A[k]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,cSa,b,c\in S, such that a+b+c=0a+b+c=0?

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

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

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

Posted by Chao Xu on .
Tags: .