A binary search solution to 3Sum

Question

I tried a binary solution to 3Sum problem in LeetCode:

Given an array nums of \$n\$ integers, are there elements \$a\$, \$b\$, \$c\$ in nums such that \$a + b + c = 0\$? Find all unique triplets in the array which gives the sum of zero.

Note:

The solution set must not contain duplicate triplets.

Example:

Given array nums = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

Ｍy plan: divide and conquer threeSum to

1. an iteration
2. and a two_Sum problem.
3. break two_Sum problem to
   1. a loop
   2. binary search

The complexity is: \$O(n^2\log{n})\$.

 class Solution:
    """
    Solve the problem by three module funtion
    threeSum
    two_sum
    bi_search 
    """
    def __init__(self):
        self.triplets: List[List[int]] = []

    def threeSum(self, nums, target=0) -> List[List[int]]:
        """
        :type nums: List[int]
        :type target: int 
        """
        nums.sort() #sort for skip duplicate and binary search 

        if len(nums) < 3:
            return []

        i = 0
        while i < len(nums) - 2:
            complement = target - nums[i]

            self.two_sum(nums[i+1:], complement)
            i += 1 #increment the index 
            while i < len(nums) -2 and nums[i] == nums[i-1]: #skip the duplicates, pass unique complement to next level.
                i += 1 

        return self.triplets


    def two_sum(self, nums, target):
        """
        :type nums: List[int]
        :tppe target: int
        :rtype: List[List[int]]
        """
        # nums = sorted(nums) #temporarily for testing.
        if len(nums) < 2:
            return [] 

        i = 0
        while i < len(nums) -1:
            complement = target - nums[i]

            if self.bi_search(nums[i+1:], complement) != None:

                # 0 - target = threeSum's fixer 
                self.triplets.append([0-target, nums[i], complement]) 
            i += 1

            while i < len(nums) and nums[i] == nums[i-1]:
                i += 1 

    def bi_search(self, L, find) -> int:
        """
        :type L: List[int]
        :type find: int 
        """
        if len(L) < 1: #terninating case 
            return None 
        else:
            mid = len(L) // 2
            if find == L[mid]:
                return find 

            if find > L[mid]:
                upper_half = L[mid+1:]
                return self.bi_search(upper_half, find)
            if find < L[mid]:
                lower_half = L[:mid] #mid not mid-1
                return self.bi_search(lower_half, find)

I ran it but get the report

Status: Time Limit Exceeded

Could you please give any hints to refactor?

Is binary search is an appropriate strategy?

Answer 1

Your bi_search() method is recursive. It doesn’t have to be. Python does not do tail-call-optimization: it won’t automatically turn the recursion into a loop. Instead of if len(L) < 1:, use a while len(L) > 0: loop, and assign to (eg, L = L[:mid]) instead of doing a recursive call.

Better: don’t modify L at all, which involves copying a list of many numbers multiple times, a time consuming operation. Instead, maintain a lo and hi index, and just update the indexes as you search.

Even better: use a built in binary search from import bisect.