Package org.drip.graph.subarray

Class ThreeSumQuadraticComparator

java.lang.Object
org.drip.graph.subarray.ThreeSum
org.drip.graph.subarray.ThreeSumQuadraticComparator
public class ThreeSumQuadraticComparator
extends ThreeSum
ThreeSumQuadraticComparator implements the Check that indicates if the Set of Numbers contains 3 that Sum to Zero using a Binary Search Comparator, leading to a Quadratic Time Algorithm. The References are:

  • Chan, T. M. (2018): More Logarithmic Factor Speedups for 3SUM, (median+) Convolution, and some Geometric 3SUM-Hard Problems Proceedings of the 29th Annual ACM SIAM Symposium on Discrete Algorithms 881-897
  • Gajentaan, A., and M. H. Overmars (1995): On a Class of O(n2) 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 42nd ACM Symposium on Theory of Computing 603-610
  • Wikipedia (2020): 3Sum https://en.wikipedia.org/wiki/3SUM




Author:
Lakshmi Krishnamurthy

  • Constructor Summary

    Constructors
    Constructor Description
    ThreeSumQuadraticComparator​(double[] numberArray)
    ThreeSumQuadraticComparator Constructor

  • Method Summary

    Modifier and Type Method Description
    boolean zeroSumExists()
    Indicate if the Zero Sum Match exists

    Methods inherited from class org.drip.graph.subarray.ThreeSum

    numberArray

    Methods inherited from class java.lang.Object

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

  • Constructor Details

    • ThreeSumQuadraticComparator

      public ThreeSumQuadraticComparator​(double[] numberArray) throws java.lang.Exception
      ThreeSumQuadraticComparator Constructor
      Parameters:
      numberArray - The Number Array
      Throws:
      java.lang.Exception - Thrown if the Inputs are Invalid

  • Method Details

    • zeroSumExists

      public boolean zeroSumExists()
      Description copied from class: ThreeSum
      Indicate if the Zero Sum Match exists
      Specified by:
      zeroSumExists in class ThreeSum
      Returns:
      TRUE - The Zero Sum Match exists