3
\$\begingroup\$

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]
]

My 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?

\$\endgroup\$
  • \$\begingroup\$ Binary search is good at O(log n), but hash search is better at O(1). \$\endgroup\$ – Lawnmower Man Mar 23 at 0:40
8
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.