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.
Let be an array of numbers, decide if there exist index , such that .
The problem is 3SUM-hard. We reduce the problem 3SUM to the above problem in linear time.
Does there exist , such that ?
Consider a instance of 3SUM. Let . Store and as elements in the array .
Claim: There exist i,j,k such that iff there exist such that .
If there exist such that , this implies for some . The other direction is similar.