We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Triple sum
  2. Discussions

Triple sum

  • nleo575
     + 0 comments

    Python3 soltuion. Time: O(nlogn). Similar to the previous comment but I implimted by own binary search algorithm and included an optimization to reduce searching once q is greater than all elements in p and r. 

    def triplets(a, b, c):
    # Use binary search to find where q is, or should be in the array
    def binary_search(arr, target):
        high, low = len(arr) - 1, 0
        mid = (high + low) // 2
        sample = arr[mid]
        l_arr = len(arr)
        while low <= high:
            if target < sample:
                high = mid - 1
            elif target > sample:
                low = mid + 1
            else:
                # Add 1 since we want count of elements q is >=
                return mid + 1
            
            mid = (high + low ) // 2
            sample = arr[mid]
        
        # Add 1 since we want count of elements q is >=
        return high + 1  # Will be 0 or len(arr)
    
    a, b, c = list(set(a)), list(set(b)), list(set(c))
    a.sort()
    b.sort()
    c.sort()

    a_len, c_len = len(a), len(c)
    max_pr = product = result = 0
    for q in b:
        if max_pr:
            result += max_pr
        else:   
            p = binary_search(a, q)
            r = binary_search(c, q)
            if p and r:
                product = p * r
                if p == a_len and r == c_len:
                    # Once q is > all elements in p and r, simply resuse
                    # this max product.
                    max_pr = product

                result += product
    
    return result