Package org.drip.graph.subarray

Class ThreeSumVariantBuilder

java.lang.Object

org.drip.graph.subarray.ThreeSumVariantBuilder

public class ThreeSumVariantBuilder
extends java.lang.Object

ThreeSumVariantBuilder converts the specified 3SUM Variant into a Standard 3SUM Problem. The References are:

• Chan, T. M. (2018): More Logarithmic Factor Speedups for 3SUM, (median+) Convolution, and some Geometric 3SUM-Hard Problems Proceedings of the 29^th Annual ACM SIAM Symposium on Discrete Algorithms 881-897
• Gajentaan, A., and M. H. Overmars (1995): On a Class of O(n²) Problems in Computational Geometry Computational Geometry: Theory and Applications 5 (3) 165-185
• Kopelowitz, T., S. Pettie, and E. Porat (2014): Higher Lower Bounds from the 3SUM Conjecture https://arxiv.org/abs/1407.6756 arXiV
• Patrascu, M. (2010): Towards Polynomial Lower Bounds for Dynamic Problems Proceedings of the 42^nd ACM Symposium on Theory of Computing 603-610
• Wikipedia (2020): 3Sum https://en.wikipedia.org/wiki/3SUM

• Module = Computational Core Module
• Library = Graph Algorithm Library
• Project = Graph Optimization and Tree Construction Algorithms
• Package = Sub-set Sum, k-Sum, and Maximum Sub-array Problems

Author:

Lakshmi Krishnamurthy

Field Summary

Fields

Modifier and Type	Field	Description
static int	COMPARATOR	Comparator Based 3SUM Check
static int	HASH_TABLE	Hash-Table Based 3SUM Check

Constructor Summary

Constructors

Constructor	Description
ThreeSumVariantBuilder()

Method Summary

Modifier and Type	Method	Description
static ThreeSum	Convolution3SUM(double[] numberArray, int type)	Construct a 3SUM Check for ith element and jth element add up to (i + j)th for some i, j
static ThreeSum	NonZeroSum(double[] numberArray, double target, int type)	Construct a 3SUM Check where the Target is non-zero
static ThreeSum	ThreeDistinctArrays(double[] numberArrayA, double[] numberArrayB, double[] numberArrayC, int type)	Construct a 3SUM Check where the Target Sum across the Three Arrays is non-zero.

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Details

COMPARATOR

public static final int COMPARATOR

Comparator Based 3SUM Check

See Also:

Constant Field Values

HASH_TABLE

public static final int HASH_TABLE

Hash-Table Based 3SUM Check

See Also:

Constant Field Values

Constructor Details

ThreeSumVariantBuilder

public ThreeSumVariantBuilder()

Method Details

NonZeroSum

public static final ThreeSum NonZeroSum(double[] numberArray,
double target,
int type)

Construct a 3SUM Check where the Target is non-zero

Parameters:

numberArray - Number Array

target - The Non-zero Target

type - 3SUM Check Type

Returns:

The 3SUM Check

ThreeDistinctArrays

public static final ThreeSum ThreeDistinctArrays(double[] numberArrayA,
double[] numberArrayB,
double[] numberArrayC,
int type)

Construct a 3SUM Check where the Target Sum across the Three Arrays is non-zero.

Parameters:

numberArrayA - Number Array A

numberArrayB - Number Array B

numberArrayC - Number Array C

type - 3SUM Check Type

Returns:

The 3SUM Check

Convolution3SUM

public static final ThreeSum Convolution3SUM(double[] numberArray,
int type)

Construct a 3SUM Check for i^th element and j^th element add up to (i + j)^th for some i, j

Parameters:

numberArray - Number Array

type - 3SUM Check Type

Returns:

The 3SUM Check